圆形比赛

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)
);

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

在对需求和表进行连接之后,我已经满足了需求和需求,并丢弃了在以下视图中任何用户无法满足的请求:

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

我现在正在尝试编写一个查询,在那里我可以计算满足所请求需求的每个用户的排列数.例如,在上面的例子中,鲍勃,乔治和赫比可以一起满足彼此的需要,拉里和沃利也可以,但约翰不能,所以总数将是2.

我首先开始使用LOOP执行此操作,但必须使用单个查询来执行此操作的更简单,资源更少的方法.

Answer 1

有关详细说明,请参阅我博客中的文章:

• 在树中寻找循环

如果您的用户可能needs在表的列中被多次找到,那么这是一项NP复杂的任务.

如果没有,请在您的视图上发出以下查询:

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在"需要"和"拥有"上查看和创建索引,查询将得到极大改进.

在这种情况下,查询完成将只需几分钟.