高效持久的递归数据结构

发布于 2024-10-18 11:57:50 字数 213 浏览 1 评论 0原文

递归数据结构的常用方法是在每个对象中都有一个父指针。我的问题是,通常的实现无法在一次操作中回答以下问题;相反,我需要多次查询我的数据库。有没有一个解决方案可以在单个查询中给出结果?

  • 获取节点的所有子节点的列表

  • 查找所有父节点(==到根节点的最短路径)

注意:我正处于规划阶段,所以我还没有局限于某个数据库。

The usual approach with recursive data structures is to have a parent pointer in each object. My problem is that the usual implementation can't answer the questions below in a single operation; instead I need to query my database several times. Is there a solution which gives me the result in a single query?

  • Get a list of all children of a node

  • Find all parent nodes (== shortest path to the root node)

Note: I'm in the planning stage, so I'm not yet limited to a certain database.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

笑着哭最痛 2024-10-25 11:57:50

至少Oracle可以进行分层查询。考虑数据库用户角色的示例:

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

现在选择用户“CM_MARY”的所有角色:

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;   

结果:
商业_DEP
创建_订单
客户
SELECT_ORDERS

选择拥有角色“CLIENT”的所有角色和用户

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;   

结果:
CL_约翰
CL_MATT
商业_DEP
CM_MARY

更新:
既然你提到,树将是相当静态的,尝试 Joe Celko 的树(大约需要阅读 180 行)。
它根本不需要自我加入!因此,我希望它的执行速度比 CONNECT BY 快几倍。虽然我刚刚在 30 分钟前读到它,但不知道它在现实世界中有多好

更新 2: 使用 MySQL 的“嵌套集模型”:管理 MySQL 中的分层数据 这与上面 Joe Celko 的 Trees 相同,但有更多示例和解释。

At least Oracle can do hierarchical queries. Consider example of db users' roles:

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

Now select all roles of user 'CM_MARY':

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;   

Result:
COMMERCIAL_DEP
CREATE_ORDERS
CLIENT
SELECT_ORDERS

Select all roles and users, who owns role 'CLIENT'

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;   

Result:
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY

UPDATE:
Since you mentioned, tree will be pretty static, it may be interesting to try Joe Celko's Trees (aprox 180 lines to read).
It doesn't require self joins at all! So, I expect it to perform times faster then CONNECT BY. Though I've just read about it just 30 min ago, and don't know how good it is in real world

Update2: "Nested Set Models" with MySQL: Managing Hierarchical Data in MySQL This is the same as Joe Celko's Trees above but with more examples and explanation.

千里故人稀 2024-10-25 11:57:50

如果“所有子节点”仅表示直接子节点,则只需在每个节点上放置一个子节点列表以及指向父节点的指针即可。请注意,这将使将节点移动到另一个父节点的成本更高,因为所有(孙)子节点也必须更新。

如果“所有子级”确实意味着所有子级,则一种选择是构建每个父级 ID 的字符串,并将其添加为索引列。例如,如果您有 A、子 B、孙子 C,则您将有 C 值为 A/B/C 的列。现在,要查找 A 的所有子级,您只需对 "A/%" 执行 LIKE 查询即可。不过,当您需要更改具有子节点的父节点时,这又是昂贵的。

我认为,如果您需要能够快速更改父母,则需要将父母信息维护为链接列表。但是,您可以使用存储过程来执行此查询操作,只需一次数据库往返。

If "all children" means only direct children, simply put a list of children, as well as a pointer to the parent on each node. Note that this will make moving a node to another parent more expensive, as all (grand)-children must be updated as well.

If "all children" really means all children, one option would be to build a string of the IDs of each parent, and add it as an indexed column. For example, if you have A, with the child B, with the grandchild C, you'd have in C a column with value A/B/C. Now to find all children of A you can simply do a LIKE query on "A/%". Again, though, this is expensive when you need to change the parent of a node with children.

If you need to be able to change parents quickly, you're going to need to maintain parent information as a linked list, I think. You could, however, use a stored procedure to perform this query operation with only one database round trip.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文