SQLite: nested sets (деревья-множества)

Написано мной по мотивам известной статьи Joe Celko 1996 г
с максимальной адаптацией под самый простой SQL на примере SQLite

Данный код не требует хранимых процедур и триггеров, и может быть легко
адаптирован практически для любой современной БД.

Для запуска и проверки достаточно: cat file.sql | sqlite3

/* tree-sets */

CREATE TABLE test (
    id      INTEGER PRIMARY KEY,
    name    VARCHAR(50),
    salary  FLOAT,
    left    INTEGER,
    right   INTEGER,
    CHECK(left <  right)
);


/*
    Jerry
        Bert
            Chuck
                Eddie
                Mary
            Donna
    Fred
        Max
*/

-- new Jerry
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Jerry', 100,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Bert
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Jerry' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Jerry' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Jerry' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Bert', 90,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Jerry' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Jerry' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Chunk
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Bert' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Bert' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Bert' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Chuck', 80,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Bert' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Bert' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Donna
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Bert' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Bert' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Bert' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Donna', 80,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Bert' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Bert' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Fred
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Fred', 100,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Max
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Fred' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Fred' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Fred' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Max', 90,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Fred' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Fred' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Eddie
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Chuck' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Chuck' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Chuck' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Eddie', 90,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Chuck' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Chuck' LIMIT 1)
FROM sqlite_master LIMIT 1;

-- new Mary
UPDATE test SET
    left = CASE WHEN left > (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Chuck' LIMIT 1)
           THEN left + 2 ELSE left END,
    right = CASE WHEN right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right)+1  FROM test),1) FROM test WHERE name='Chuck' LIMIT 1)
           THEN right + 2 ELSE right END
WHERE right >= (SELECT COALESCE(MAX(right),(SELECT MAX(right) FROM test),1) FROM test WHERE name='Chuck' LIMIT 1);
INSERT INTO test (name, salary, left, right)
SELECT 'Mary', 20,
   (SELECT COALESCE(MAX(right)-2,(SELECT MAX(right)+1 FROM test),1) FROM test WHERE name='Chuck' LIMIT 1),
   (SELECT COALESCE(MAX(right)-1,(SELECT MAX(right)+2 FROM test),2) FROM test WHERE name='Chuck' LIMIT 1)
FROM sqlite_master LIMIT 1;

.mode column
.headers on

.print
.print "=============="
.print "=== SOURCE ==="
.print "=============="
.print

SELECT test.*, right-left as size FROM test ORDER BY id;

.print
.print "======================"
.print "=== RECURSIVE VIEW ==="
.print "======================"
.print

WITH RECURSIVE V (lv, id, name, salary, left, right) AS (
    SELECT 1,A.id,A.name,A.salary,A.left,A.right FROM test A
        WHERE NOT EXISTS (
            SELECT id FROM test B WHERE A.left BETWEEN B.left+1 AND B.right-1
        )
    UNION
    SELECT V.lv+1, T.id, T.name, T.salary, T.left, T.right FROM test T
        INNER JOIN V ON (T.left BETWEEN V.left+1 AND V.right-1)
        LEFT JOIN test P
            ON (P.left BETWEEN V.left+1 AND V.right-1)
            AND (T.left BETWEEN P.left+1 AND P.right-1)
        WHERE P.id IS NULL
    ORDER BY 1 DESC
)
SELECT lv, REPLACE(HEX(ZEROBLOB(lv*2)),0x00,' ') || name FROM V;

.print
.print "===================="
.print "=== ALL CHILDREN ==="
.print "===================="
.print

SELECT * FROM test WHERE left = (right - 1);

.print
.print "========================================"
.print "=== ALL PARENTS OF 'EDDIE' FROM ROOT ==="
.print "========================================"
.print

SELECT T2.name, T1.name AS parent, (T1.right - T1.left) AS size
    FROM test AS T1, test AS T2
    WHERE (T2.left BETWEEN T1.left AND T1.right)
        AND (T2.right BETWEEN T1.left AND T1.right)
        AND (T2.name = 'Eddie')
    ORDER BY 3 DESC;

.print
.print "========================================="
.print "=== LEVEL (1..N) OF 'EDDIE' FROM ROOT ==="
.print "========================================="
.print

SELECT T2.name, T1.name as parent, COUNT(*) AS level
    FROM test AS T1, test AS T2
    WHERE (T2.left BETWEEN T1.left AND T1.right)
        AND (T2.right BETWEEN T1.left AND T1.right)
        AND T2.name = 'Eddie'
    ORDER BY 3 DESC;

.print
.print "============================"
.print "=== LEVELS FOR ALL NODES ==="
.print "============================"
.print

SELECT T2.name, COUNT(*) AS level
        FROM test AS T1, test AS T2
        WHERE (T2.left BETWEEN T1.left AND T1.right)
        GROUP BY 1 ORDER BY 2;

.print
.print "==========================="
.print "=== CALC SALARY FOR ALL ==="
.print "==========================="
.print

SELECT T1.name, SUM(T2.salary) AS salary
    FROM test AS T1, test AS T2
    WHERE T2.left BETWEEN T1.left AND T1.right
    GROUP BY 1;


.print
.print "=============================="
.print "=== DELETE SUBTREE 'CHUCK' ==="
.print "=============================="
.print

DELETE FROM test WHERE left BETWEEN 3 and 8;

UPDATE test SET
    left = CASE
        WHEN left > 3 THEN left - (8 - 3 + 1)
        ELSE left
    END,
    right = CASE
        WHEN right > 3 THEN right - (8 - 3 + 1)
        ELSE right
    END;
SELECT test.*, right-left as size FROM test ORDER BY id;



.print
.print "==========================="
.print "=== DELETE NODE 'CHUCK' ==="
.print "==========================="
.print

DELETE FROM test WHERE name='Chuck';
UPDATE test SET
    left = CASE
        WHEN (left BETWEEN 3 AND 8) THEN left - 1
        WHEN (left > 8) THEN left - 2 ELSE left
    END,
    right = CASE
        WHEN (right BETWEEN 3 AND 8) THEN right - 1
        WHEN (right > 8) THEN right - 2 ELSE right
    END
WHERE left >= 3 or right >= 3;

SELECT test.*, right-left as size FROM test ORDER BY id;

-- eof