/ Check-in [83b0b291]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add test cases showing the use of ORDER BY on a recursive query to control depth-first versus breath-first search of a tree.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 83b0b2916589db0184435dbd4c304387f393ed60
User & Date: drh 2014-01-24 11:16:01
Context
2014-01-24
14:37
Add test cases that compare the performance of the transitive_closure virtual table again common table expressions for walking a tree. check-in: 9a23f020 user: drh tags: trunk
14:05
Bring in all the latest trunk changes, including the Common Table Expressions implementation. check-in: 9b43e559 user: drh tags: sessions
11:16
Add test cases showing the use of ORDER BY on a recursive query to control depth-first versus breath-first search of a tree. check-in: 83b0b291 user: drh tags: trunk
2014-01-23
14:44
Modifications to test files to omit any tests that intentionally access out-of-bounds locations in clang -fsanitize=address builds. check-in: f4a701d5 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to test/with1.test.

   370    370       SELECT i FROM tree, t WHERE p = id
   371    371     ) 
   372    372     SELECT id FROM t;
   373    373   } {1 {circular reference: t}}
   374    374   
   375    375   # Compute the mandelbrot set using a recursive query
   376    376   #
   377         -do_execsql_test 8.1 {
          377  +do_execsql_test 8.1-mandelbrot {
   378    378     WITH RECURSIVE
   379    379       xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
   380    380       yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
   381    381       m(iter, cx, cy, x, y) AS (
   382    382         SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
   383    383         UNION ALL
   384    384         SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m 
................................................................................
   413    413                                    ..+####+.
   414    414                                      ..#*..
   415    415                                       ....#
   416    416                                       +.}}
   417    417   
   418    418   # Solve a sudoku puzzle using a recursive query
   419    419   #
   420         -do_execsql_test 8.2 {
          420  +do_execsql_test 8.2-soduko {
   421    421     WITH RECURSIVE
   422    422       input(sud) AS (
   423    423         VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
   424    424       ),
   425    425     
   426    426       /* A table filled with digits 1..9, inclusive. */
   427    427       digits(z, lp) AS (
................................................................................
   448    448                             + ((ind-1)/27) * 27 + lp
   449    449                             + ((lp-1) / 3) * 6, 1)
   450    450              )
   451    451       )
   452    452     SELECT s FROM x WHERE ind=0;
   453    453   } {534678912672195348198342567859761423426853791713924856961537284287419635345286179}
   454    454   
          455  +
          456  +# Test cases to illustrate on the ORDER BY clause on a recursive query can be
          457  +# used to control depth-first versus breath-first search in a tree.
          458  +#
          459  +do_execsql_test 9.1 {
          460  +  CREATE TABLE org(
          461  +    name TEXT PRIMARY KEY,
          462  +    boss TEXT REFERENCES org
          463  +  ) WITHOUT ROWID;
          464  +  INSERT INTO org VALUES('Alice',NULL);
          465  +  INSERT INTO org VALUES('Bob','Alice');
          466  +  INSERT INTO org VALUES('Cindy','Alice');
          467  +  INSERT INTO org VALUES('Dave','Bob');
          468  +  INSERT INTO org VALUES('Emma','Bob');
          469  +  INSERT INTO org VALUES('Fred','Cindy');
          470  +  INSERT INTO org VALUES('Gail','Cindy');
          471  +  INSERT INTO org VALUES('Harry','Dave');
          472  +  INSERT INTO org VALUES('Ingrid','Dave');
          473  +  INSERT INTO org VALUES('Jim','Emma');
          474  +  INSERT INTO org VALUES('Kate','Emma');
          475  +  INSERT INTO org VALUES('Lanny','Fred');
          476  +  INSERT INTO org VALUES('Mary','Fred');
          477  +  INSERT INTO org VALUES('Noland','Gail');
          478  +  INSERT INTO org VALUES('Olivia','Gail');
          479  +  -- The above are all under Alice.  Add a few more records for people
          480  +  -- not in Alice's group, just to prove that they won't be selected.
          481  +  INSERT INTO org VALUES('Xaviar',NULL);
          482  +  INSERT INTO org VALUES('Xia','Xaviar');
          483  +  INSERT INTO org VALUES('Xerxes','Xaviar');
          484  +  INSERT INTO org VALUES('Xena','Xia');
          485  +  -- Find all members of Alice's group, breath-first order  
          486  +  WITH RECURSIVE
          487  +    under_alice(name,level) AS (
          488  +       VALUES('Alice','0')
          489  +       UNION ALL
          490  +       SELECT org.name, under_alice.level+1
          491  +         FROM org, under_alice
          492  +        WHERE org.boss=under_alice.name
          493  +        ORDER BY 2
          494  +    )
          495  +  SELECT group_concat(substr('...............',1,level*3) || name,x'0a')
          496  +    FROM under_alice;
          497  +} {{Alice
          498  +...Bob
          499  +...Cindy
          500  +......Dave
          501  +......Emma
          502  +......Fred
          503  +......Gail
          504  +.........Harry
          505  +.........Ingrid
          506  +.........Jim
          507  +.........Kate
          508  +.........Lanny
          509  +.........Mary
          510  +.........Noland
          511  +.........Olivia}}
          512  +
          513  +# The previous query used "ORDER BY level" to yield a breath-first search.
          514  +# Change that to "ORDER BY level DESC" for a depth-first search.
          515  +#
          516  +do_execsql_test 9.2 {
          517  +  WITH RECURSIVE
          518  +    under_alice(name,level) AS (
          519  +       VALUES('Alice','0')
          520  +       UNION ALL
          521  +       SELECT org.name, under_alice.level+1
          522  +         FROM org, under_alice
          523  +        WHERE org.boss=under_alice.name
          524  +        ORDER BY 2 DESC
          525  +    )
          526  +  SELECT group_concat(substr('...............',1,level*3) || name,x'0a')
          527  +    FROM under_alice;
          528  +} {{Alice
          529  +...Bob
          530  +......Dave
          531  +.........Harry
          532  +.........Ingrid
          533  +......Emma
          534  +.........Jim
          535  +.........Kate
          536  +...Cindy
          537  +......Fred
          538  +.........Lanny
          539  +.........Mary
          540  +......Gail
          541  +.........Noland
          542  +.........Olivia}}
          543  +
          544  +# Without an ORDER BY clause, the recursive query should use a FIFO,
          545  +# resulting in a breath-first search.
          546  +#
          547  +do_execsql_test 9.3 {
          548  +  WITH RECURSIVE
          549  +    under_alice(name,level) AS (
          550  +       VALUES('Alice','0')
          551  +       UNION ALL
          552  +       SELECT org.name, under_alice.level+1
          553  +         FROM org, under_alice
          554  +        WHERE org.boss=under_alice.name
          555  +    )
          556  +  SELECT group_concat(substr('...............',1,level*3) || name,x'0a')
          557  +    FROM under_alice;
          558  +} {{Alice
          559  +...Bob
          560  +...Cindy
          561  +......Dave
          562  +......Emma
          563  +......Fred
          564  +......Gail
          565  +.........Harry
          566  +.........Ingrid
          567  +.........Jim
          568  +.........Kate
          569  +.........Lanny
          570  +.........Mary
          571  +.........Noland
          572  +.........Olivia}}
          573  +
   455    574   finish_test