Selecting from a table based on relationships that are stored in another table

My position

I am using SQLite on Android to store some data. This data is in the same table, but each row can have one or more relationships with other rows in the same table. This relationship is stored in another table. Think of it this way:

Table 1 can have a row with id 0 that has 2 children with IDs 1 and 2. Both of these children will again be stored in table 1, but in table 2 will be displayed for each of these children from id 0 to their own ID. The tables might look something like this:

+---------------------------+     
|           Table 1         |     
+------+------+------+------+     
|  ID  |   .... Data ....   |     
+------+------+------+------+     
|  0   | ...  | ...  | ...  |   <--- This would be the parent of rows 1 & 2         
|  1   | ...  | ...  | ...  |        as indicated in the other table
|  2   | ...  | ...  | ...  |      
|  3   | ...  | ...  | ...  |     

+----------------------------+
|           Table 2          | 
+-------------+--------------+
|  Parent ID  |   Child ID   |
|      0      |       1      |   <-- This means that row 0 has
|      0      |       2      |   <-- 2 children with the ids 1 and 2  
|      2      |       5      |          
|      3      |       2      |   <-- Each row can have multiple parents and/or children

      

What I want to do essentially is select from table 1 with some arbitrary where clause, and if that where clause, for example, matches row 0, I also need to select the children of row 0 along with it and the children of those children and soon. Since I generally suck at the explanation, let me illustrate it again:

If I were to run select

like this:

SELECT * FROM TABLE1 WHERE ...

      

I would get a result like this:

+------+------+------+------+     
|  ID  |   .... Data ....   |     
+------+------+------+------+     
|  0   | ...  | ...  | ...  |      
|  3   | ...  | ...  | ...  |

      

But I would like to get the following:

+------+---------+------+------+------+     
|  ID  | isChild |   .... Data ....   |     
+------+---------+------+------+------+     
|  0   |    0    | ...  | ...  | ...  |   <--- This row along with row 3 is what actually matches the where clause            
|  1   |    1    | ...  | ...  | ...  |
|  2   |    1    | ...  | ...  | ...  |      
|  5   |    2    | ...  | ...  | ...  |
|  3   |    0    | ...  | ...  | ...  |   <--- This row along with row 0 is what actually matches the where clause            
|  2   |    1    | ...  | ...  | ...  |
|  5   |    2    | ...  | ...  | ...  |

      

Only lines 1 and 3 actually match the where clause. The order of the children is not important, but they must come immediately after the parent, and the "isChild" column will be used to indicate whether the row is a child and what it is.

Notice the third line from the top in the output above, that is, with the ID 2. It is 2

in "isChild" because it is a child of the line above which it is also a child. You can think of all the output above as a tree like this:

- 0 
   - 1      <-- 1 is a child of 0
   - 2      <-- 2 is a child of 0
      - 5   <-- 5 is a child of 2
- 3
   - 2      <-- 2 is a child of 3
      - 5   <-- 5 is a child of 2

      

The isChild column essentially tells you which level you are at.


Problem

So far I have implemented this with several selects

. First I have to select rows from table1, take ids from each row, and then select mappings for each row from table2. With these mappings, I would select the children from table1, and after that, I would look again at the child mappings in table2, etc. It's not ingenious to see that this can cause huge performance issues very quickly, and it was actually quite slow.

I have since tried to improve this by decreasing the amount selects

, but now I hit the wall. I've implemented some improvement I can think of and it works for the most part, but if you're dealing with large datasets things slow down exponentially and I don't see any other way to improve this in code. I started thinking and came to the conclusion that if I could somehow select everything at once, as I described above, it would solve many problems for me.


My attempts to solve the problem so far

Since I cannot improve this in code, I turned my attention to SQL. I have already made many unrelated improvements that have led to great performance gains by implementing triggers for the most common tasks, such as creating and deleting mappings in table2. And I was hoping I could solve this problem in a similar way.

I've tried all sorts of JOIN

or UNION

, but nothing works as I expect. I have a feeling that I could be wrong. I still haven't tried to include the "isChild" column.

This is the link to the SQLFiddle I am using to test my favorites

When I started working on this, I recklessly thought that a simple one JOIN

would solve the problem, but I doubt that at this stage I am also not sure if what I want to do is possibly even (efficiently)).


This problem made me realize how little I know about SQL, and if some SQL wizard can come and tell me how simple the solution really is, I would really appreciate it! (Although I suspect the solution to my problem is actually not that easy)

Please keep in mind that this question is specifically about SQLite on Android. But I have tried to keep this question as general as possible, as it applies to many other SQL implementations or operating systems as well.

If you have a really great answer to this question with a simple solution that will blow my mind and a great explanation to agree with you, I will not hesitate to reward you with a bounty.

+3


source to share


1 answer


To read recursive data, you will need to use a recursive common table expression .

However, this was introduced in SQLite 3.8.3, so your Android device is unlikely to support it.



You should continue to use multiple queries or use your own version of SQLite with the NDK.

+2


source







All Articles