sql - 循环匹配

Question

我有一个包含三个表的数据库:userid_tbl、need_tbl、have_tbl

create table userid_tbl
(user_id varchar2(15) not null primary key);

create table need_tbl
(user_id varchar2(15) not null,
have_item varchar2(100) not null,
foreign key (user_id) references userid_tbl (user_id)
);

create table have_tbl
(user_id varchar2(15) not null,
have_item varchar2(100) not null,
foreign key (user_id) references userid_tbl (user_id)
);

每个用户都可以在数据库中创建无限数量的需求记录或他们可以提供给其他人的服务。这些项目来自预定列表。

在对 need 和 have 表进行连接后，我匹配了需求和需求，并在如下所示的 View 中丢弃了任何用户无法满足的请求:

Item:         Need:            Have:
1             Bob              George
2             George           Herbie
3             Herbie           Bob
4             Larry            Wally
5             Wally            Larry
6             John             George

我现在正在尝试编写一个查询，我可以在其中计算每个用户满足其请求需求的排列数。例如，在上面的示例中，Bob、George 和 Herbie 可以一起满足彼此的需求，Larry 和 Wally 也可以，但 John 不能，因此总数为 2。

我一开始是用一个 LOOP 来做这件事的，但是必须有一种更简单、资源占用更少的方法来用一个查询来做这件事。

Answer 1

详细解释见我博客中的文章:

• Finding loops in a tree

如果在表格的needs 列中多次找到您的用户，这是一个NP 复杂任务。

如果没有，请在您的 View 上发出此查询:

SELECT  COUNT(*)
FROM    v_needs
CONNECT BY NOCYCLE
        need = PRIOR have
WHERE   CONNECT_BY_ISCYCLE = 1

CONNECT BY NOCYCLE 允许分层查询中的循环(NOCYCLE 只是在发现循环时停止分支，没有 NOCYCLE 返回错误) .

CONNECT_BY_ISCYCLE 在发现循环时返回 true(它返回 1 用于在下一次迭代中产生当前分支根的记录)。

请注意，此查询将返回循环中的所有用户，而不会对它们进行分组。

要对用户进行分组，请发出此查询:

SELECT  n.*, CONNECT_BY_ROOT(have), level
FROM    v_needs n
START WITH
        have IN
        (
        SELECT  MIN(have)
        FROM    (
                SELECT  have, CONNECT_BY_ROOT(have) AS root
                FROM    t_needs
                START WITH
                        have IN
                        (
                        SELECT  have
                        FROM    t_needs n
                        WHERE   CONNECT_BY_ISCYCLE = 1
                        CONNECT BY NOCYCLE
                                needs = PRIOR have
                        )
                CONNECT BY NOCYCLE
                        have = PRIOR needs
                )
        GROUP BY
                root
        )
CONNECT BY NOCYCLE
        have = PRIOR needs

更新:

从您的帖子中我可以看出您对最大循环长度有限制。

这使得这个问题更容易解决。

只需将循环限制条件添加到每个查询中:

SELECT  n.*, CONNECT_BY_ROOT(have), level
FROM    v_needs n
START WITH
        have IN
        (
        SELECT  MIN(have)
        FROM    (
                SELECT  have, CONNECT_BY_ROOT(have) AS root
                FROM    t_needs
                START WITH
                        have IN
                        (
                        SELECT  have
                        FROM    t_needs n
                        WHERE   CONNECT_BY_ISCYCLE = 1
                        CONNECT BY NOCYCLE
                                needs = PRIOR have
                                AND level <= 5
                        )
                CONNECT BY NOCYCLE
                        have = PRIOR needs
                        AND level <= 5
                )
        GROUP BY
                root
        )
CONNECT BY NOCYCLE
        have = PRIOR needs
        AND level <= 5

这将停止遍历 5th 级别的层次结构树。

如果您的数据库中有 1,000,000 个用户，平均每个用户 5 个匹配项，则查询需要检查 1,000,000 * 5^5 = 3,125,000,000 行，这是可观察的行数。

如果您MATERIALIZE View 并在“需要”和“有”上创建索引，查询将得到极大改进。

在这种情况下，查询将在几分钟内完成。