4

userid_tbl、need_tbl、have_tbl の 3 つのテーブルを持つデータベースがあります。

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 テーブルで結合を行った後、ニーズとウォンツを一致させ、次のようなビューでどのユーザーも満たすことができない要求を破棄しました。

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

現在、要求されたニーズが満たされている各ユーザーの順列の数を計算できるクエリを作成しようとしています。たとえば、上記の例では、ボブ、ジョージ、およびハービーは、ラリーとウォーリーと同様に、お互いのニーズを一緒に満たすことができますが、ジョンはできないため、合計数は 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が見つかったときにブランチを停止するだけで、noNOCYCLEはエラーを返します)。

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'need' と 'have' を参照してインデックスを作成すると、クエリが大幅に改善されます。

この場合、クエリは数分で完了します。

于 2009-05-18T10:18:18.767 に答える
0

これは私にとって素晴らしいスタートです。私は何日も頭を壁にぶつけていました。これをより明確にするために、もう少し詳細を説明しましょう。残念ながら、問題はクリークの問題であり、3 つの列すべてが一意ではないため、NP 完全です。

これが実際のアプリケーションです。私は、不適切または違法な通貨交換の代わりに、負の相互関係、つまり物々交換の効率に関する研究プロジェクトを行っています。

具体例は臓器移植です。ボブが腎臓を必要としていて、彼の妻が喜んで腎臓を提供したとしましょう。彼女が一致するという保証はありません。ただし、彼女はデータベース内の別のユーザーと一致する可能性があり、代わりにそのユーザーが一致する腎臓をボブに提供できる可能性があります。

数千人の受信者と数万人の潜在的な寄付者を含むデータベースがある場合、多方向トランザクションを仲介して、できるだけ多くの受信者の利益を最大化できる可能性があります。

ループを閉じるために必要なレベルの最大数に関しては、明らかに制限が必要です。5 方向のトランザクションは可能ですが、100 方向のトランザクションは論理的に実現可能ではありません。

私は今日まで Oracle Spatial について聞いたことがありませんでした。これは、まさにこれを簡単にするために必要な製品のようです。

于 2009-05-20T18:14:15.057 に答える