sql - 查询以查找在 sqlite 中存储为邻接列表的树中的下一个项目

Question

背景:sqlite应该用于存储可以使用SNMP查询的信息。 SNMP以OID的层次结构组织信息，并支持3种类型的查询:

1. 单个 OID 的值
2. OID 和值是 lexicographically紧邻给定的 OID。
3. 子树的所有 OID 和值

我从下表开始:

PRAGMA foreign_keys = ON;

CREATE TABLE data (
   oid TEXT NOT NULL PRIMARY KEY,
   parent TEXT REFERENCES data(oid) ON DELETE CASCADE CHECK(oid = '1' OR parent IS NOT NULL),
   leaf_id INTEGER NOT NULL,
   value BLOB DEFAULT NULL,
   CHECK(parent IS NULL OR oid = parent || '.' || leaf_id)
);

INSERT INTO data VALUES ('1', NULL, 1, NULL);
INSERT INTO data VALUES ('1.5', '1', 5, NULL);
INSERT INTO data VALUES ('1.5.2', '1.5', 2, 'foo');
INSERT INTO data VALUES ('1.5.11', '1.5', 11, 'foo');
INSERT INTO data VALUES ('1.5.1', '1.5', 1, 'foo');
INSERT INTO data VALUES ('1.3', '1', 3, NULL);
INSERT INTO data VALUES ('1.3.4', '1.3', 4, 'foo');
INSERT INTO data VALUES ('1.3.7', '1.3', 7, 'foo');
INSERT INTO data VALUES ('1.3.5', '1.3', 5, 'foo');
INSERT INTO data VALUES ('1.3.6', '1.3', 6, 'foo');

将 OID 的最后部分存储为 INT 的想法是能够按字典顺序对具有相同父项的所有项目进行排序。

第一个查询类型编写起来很简单。然而，由于我对 SQL 的经验有限，在为第二种和第三种情况编写查询时遇到了困难。我认为使用正确的WITH RECURSIVE ... SELECT 构造应该是可能的。到目前为止，我找不到一种方法来组合这 3 种情况(第一个 child 、下一个 sibling 、下一个 parent )，并且正确的排序也不起作用。另一个复杂性是所有值为 NULL 的 OID 都必须被忽略。

如果有人可以提供这两个问题或帮助我编写它们，我将不胜感激。

如果查询变得太复杂或无法编写，另一个想法是添加另一列“下一个”，并带有指向下一项的“指针”，并使用触发器填充下一个值。

但是，我不喜欢使用嵌套集 - 对于插入/删除来说太复杂且缓慢。

Answer 1

检索子树很简单:

WITH RECURSIVE subtree(oid, value, depth, leaf_id) AS (
    SELECT oid,
           value,
           0 AS depth,
           leaf_id
    FROM data
    WHERE oid = '1'  -- start of subtree
    UNION ALL
    SELECT child.oid,
           child.value,
           parent.depth + 1,
           child.leaf_id
    FROM data AS child
    JOIN subtree AS parent ON child.parent = parent.oid
    ORDER BY depth DESC, leaf_id ASC
)
SELECT oid, value
FROM subtree
WHERE value IS NOT NULL

只有在按字典顺序对结果进行排序时才需要 深度 和 leaf_id 值。

您应该在 parent 列上有一个索引。

<小时/>

对于字典顺序的下一项，首先考虑以下 CTE，它只是简单地向上遍历树，但会记住下面最后一层的叶子值:

WITH RECURSIVE parents(oid, parent, previous_leaf, step, leaf_id) AS (
    SELECT oid,
           parent,
           -1,
           0 AS step,
           leaf_id
    FROM data
    WHERE oid = '1.3.4'  -- start point
    UNION ALL
    SELECT parent.oid,
           parent.parent,
           child.leaf_id,
           child.step + 1,
           parent.leaf_id
    FROM data AS parent
    JOIN parents AS child ON parent.oid = child.parent
    ORDER BY step
)
SELECT oid, previous_leaf FROM parents

oid         previous_leaf
----------  -------------
1.3.4       -1             (1.)
1.3         4              (2.)
1           3              (3.)

对于每个结果行，当我们搜索 oid 值下面的子树时会发生什么，并且附加限制是该子树中的顶级叶子必须是大于 previous_leaf 值？

1. 我们搜索 1.3.4 的子级。 (previous_leaf 无效。)
2. 我们搜索 1.3.4 的较大 silbing，例如 1.3.5。
3. 我们搜索 1.3 的较大 silbing，例如 1.5。

所以现在我们只需要做这个子树搜索:

WITH RECURSIVE parents(oid, parent, previous_leaf, step, leaf_id) AS (
    ... see above ...
),
subtree(oid, value, depth, leaf_id, previous_leaf, step) AS (
    SELECT oid,
           NULL,            -- interesting items are only *below* top of subtree 
           0 AS depth,
           leaf_id,
           previous_leaf,
           step
    FROM parents
    UNION ALL
    SELECT child.oid,
           child.value,
           parent.depth + 1,
           child.leaf_id,
           -1,              -- previous_leaf mattered only at the top
           parent.step
    FROM data AS child
    JOIN subtree AS parent ON child.parent = parent.oid
    WHERE child.leaf_id > parent.previous_leaf
    ORDER BY step, depth DESC, leaf_id
)
SELECT oid, value
FROM subtree
WHERE value IS NOT NULL
LIMIT 1                     -- only the first item