4

我有一个包含三个表的数据库：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

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

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

4

2 回答 2

9

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

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在“需要”和“拥有”上查看并创建索引，查询将得到极大改进。

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

于 2009-05-18T10:18:18.767 回答
0

这对我来说是一个很好的开始。几天来，我一直在用头撞墙。让我提供更多细节以使这一点更清楚。不幸的是，这个问题是一个集团问题，并且是 NP 完全的，因为所有三列都不是唯一的。

这是现实世界的应用：我正在做一个关于负互惠效率的研究项目，即以物易物，以代替不适当或非法的货币交换。

具体的例子是器官移植。假设 Bob 需要一个肾脏，而他的妻子愿意捐赠一个肾脏，但不能保证她是匹配的。然而，她可能是数据库中另一个用户的匹配项，作为回报，她可能能够为 Bob 提供匹配的肾脏。

如果我有一个包含数千名接受者和数万个潜在捐赠者的数据库，我可能会促成一项多向交易，以最大限度地为尽可能多的接受者带来利益。

显然必须限制关闭循环所需的最大级别数。5 路交易是可能的，但 100 路交易在逻辑上是不可行的。

直到今天我才听说过 Oracle Spatial。看起来这可能正是我需要使这更容易的产品。

于 2009-05-20T18:14:15.057 回答