问题描述

我有一个包含分层数据的表格.此层次结构中目前有大约 8 个级别.

I have a table containing hierarchical data. There are currently ~8 levels in this hierarchy.

我真的很喜欢数据的结构方式，但是当我需要知道级别 8 的记录是否是级别 1 的记录的子级时，性能很差.

I really like the way the data is structured, but performance is dismal when I need to know if a record at level 8 is a child of a record at level 1.

我有 PL/SQL 存储函数，它们为我执行这些查找，每个函数都有一个 select * from tbl start with ... connect by... 语句.当我查询少量记录时，这很好用，但我现在需要一次查询约 10k 条记录，并为每个记录运行此函数.我需要它在几秒钟内运行需要 2-3 分钟.

I have PL/SQL stored functions which do these lookups for me, each having a select * from tbl start with ... connect by... statement. This works fine when I'm querying a handful of records, but I'm in a situation now where I need to query ~10k records at once and for each of them run this function. It's taking 2-3 minutes where I need it to run in just a few seconds.

根据我对当前数据的了解使用一些启发式方法，我可以摆脱查找功能，只需执行 childrecord.key ||'%' LIKE parentrecord.key 但这是一个非常肮脏的黑客，并不总是有效.

Using some heuristics based on my knowledge of the current data, I can get rid of the lookup function and just do childrecord.key || '%' LIKE parentrecord.key but that's a really dirty hack and will not always work.

所以现在我在想，对于这个分层定义的表，我需要有一个单独的父子表，它将包含每个关系……对于从 1-8 级的层次结构，将有 8 个！记录，将 1 与 2、1 与 3、...、1 与 8 和 2 与 3、2 与 4、...、2 与 8 相关联.依此类推.

So now I'm thinking that for this hierarchically-defined table I need to have a separate parent-child table, which will contain every relationship...for a hierarchy going from level 1-8 there would be 8! records, associating 1 with 2, 1 with 3,...,1 with 8 and 2 with 3, 2 with 4,...,2 with 8. And so forth.

我的想法是我需要有一个插入触发器，它基本上会运行 connect by 查询，并且对于层次结构中的每个匹配项，它都会在查找表中插入一条记录.为了处理旧数据，我将通过级联删除设置主表的外键.

My thought is that I would need to have an insert trigger where it will basically run the connect by query and for every match going up the hierarchy it will insert a record in the lookup table. And to deal with old data I'll just set up foreign keys to the main table with cascading deletes.

还有比这更好的选择吗?我是否错过了另一种可以更快确定这些远亲/后代关系的方法?

Are there better options than this? Am I missing another way that I could determine these distant ancestor/descendant relationships more quickly?

这似乎正是我在想的:http://evolt.org/working_with_hierarchical_data_in_sql_using_ancestor_tables

推荐答案

所以你想要的是实现传递闭包.也就是说，给定这个应用表......

So what you want is to materialize the transitive closures. That is, given this application table ...

 ID   | PARENT_ID
------+----------
    1 | 
    2 |         1
    3 |         2
    4 |         2
    5 |         4

...图表看起来像这样:

... the graph table would look like this:

 PARENT_ID | CHILD_ID
-----------+----------
         1 |        2
         1 |        3
         1 |        4
         1 |        5
         2 |        3
         2 |        4
         2 |        5
         4 |        5

可以在 Oracle 中维护这样的表，尽管您需要为它滚动自己的框架.问题是是否值得开销.如果源表是不稳定的，那么保持图形数据新鲜可能会花费比您节省的查询更多的周期.只有您知道您的数据配置文件.

It is possible to maintain a table like this in Oracle, although you will need to roll your own framework for it. The question is whether it is worth the overhead. If the source table is volatile then keeping the graph data fresh may cost more cycles than you will save on the queries. Only you know your data's profile.

我认为您无法使用 CONNECT BY 查询和级联外键来维护这样的图表.太多的间接活动，很难做到正确.还有一个物化视图，因为当我们删除 ID=4 的源记录时，我们无法编写一个 SQL 查询来清除 1->5 记录.

I don't think you can maintain such a graph table with CONNECT BY queries and cascading foreign keys. Too much indirect activity, too hard to get right. Also a materialized view is out, because we cannot write a SQL query which will zap the 1->5 record when we delete the source record for ID=4.

所以我建议你阅读一篇名为在 SQL 中维护图的传递闭包 作者:Dong、Libkin、Su 和 Wong.这包含了很多理论和一些粗糙的 (Oracle) SQL，但它将为您构建维护图表所需的 PL/SQL 奠定基础.

So what I suggest you read a paper called Maintaining Transitive Closure of Graphs in SQL by Dong, Libkin, Su and Wong. This contains a lot of theory and some gnarly (Oracle) SQL but it will give you the grounding to build the PL/SQL you need to maintain a graph table.

"你能扩展一下关于它的部分吗太难维持通过/级联 FK 连接?如果我控制访问表和所有插入/更新/删除通过存储过程，有哪些有这样的场景崩溃了?"

"can you expand on the part about it being too difficult to maintain with CONNECT BY/cascading FKs? If I control access to the table and all inserts/updates/deletes take place via stored procedures, what kinds of scenarios are there where this would break down?"

考虑记录1->5，它是1->2->4->5的短路.现在，如我之前所说，如果我们删除 ID=4 的源记录会发生什么?级联外键可以删除 2->4 和 4->5 的条目.但这会在图表中留下 1->5(实际上是 2->5)，尽管它们不再代表图表中的有效边.

Consider the record 1->5 which is a short-circuit of 1->2->4->5. Now what happens if, as I said before, we delete the the source record for ID=4? Cascading foreign keys could delete the entries for 2->4 and 4->5. But that leaves 1->5 (and indeed 2->5) in the graph table although they no longer represent a valid edge in the graph.

可能有效的方法(我认为，我还没有这样做过)是在源表中使用一个额外的合成键，就像这样.

What might work (I think, I haven't done it) would be to use an additional synthetic key in the source table, like this.

 ID   | PARENT_ID | NEW_KEY
------+-----------+---------
    1 |           | AAA
    2 |         1 | BBB
    3 |         2 | CCC
    4 |         2 | DDD
    5 |         4 | EEE

现在图表看起来像这样:

Now the graph table would look like this:

 PARENT_ID | CHILD_ID | NEW_KEY
-----------+----------+---------
         1 |        2 | BBB
         1 |        3 | CCC
         1 |        4 | DDD
         1 |        5 | DDD
         2 |        3 | CCC
         2 |        4 | DDD
         2 |        5 | DDD
         4 |        5 | DDD

所以图形表有一个外键引用生成它的源表中的关系，而不是链接到 ID.然后删除 ID=4 的记录将级联删除图表中 NEW_KEY=DDD 的所有记录.

So the graph table has a foreign key referencing the relationship in the source table which generated it, rather than linking to the ID. Then deleting the record for ID=4 would cascade deletes of all records in the graph table where NEW_KEY=DDD.

如果任何给定的 ID 只能有零个或一个父 ID，这将起作用.但如果允许这种情况发生，它就行不通:

This would work if any given ID can only have zero or one parent IDs. But it won't work if it is permissible for this to happen:

 ID   | PARENT_ID
------+----------
    5 |         2
    5 |         4

换句话说，边 1->5 代表 1->2->4->5 和 1->;2->5.因此，什么可行取决于数据的复杂性.

In other words the edge 1->5 represents both 1->2->4->5 and 1->2->5. So, what might work depends on the complexity of your data.

这篇关于创建分层定义的数据集的扁平表/视图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！