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