2

アーティスト、曲、曲間のカバー関係の大規模な postgresql データベースがあります。http://www.coversproject.com/artist/longest_chainのように、データベースでカバー関係の最長チェーンを見つけたいと思い ます。

最後に、私はこのようなものが欲しいです:

  • アーティスト A がアーティスト B の曲 1 をカバー
  • アーティスト B がアーティスト C の曲 2 をカバー
  • アーティスト C がアーティスト D の曲 3 をカバー
  • ...

私の使用例では、どのアーティストもリストに 1 回しか表示されないため、これはさらに厄介です。また、ここでデータベース構造を単純化して、質問の具体性を低くしましたが、これは問題になりません。

決定的な答えをくれる魔法のような質問はないように思えます。各クエリ実行の結果を保存しながら、異なる開始エントリでデータベースを何度もクエリするアルゴリズムが必要だと思います。しばらくすると、その時点で見つかった最長のチェーンを選択します。これは、既存の最長のチェーンではないかもしれませんが、私にとっては十分です.

これをどのように達成できるかについての指針はありますか？(postgres でネイティブに実行するか、データベースにクエリを実行するスクリプトを作成します)

4

3 に答える 3

1

うーん、私は以前にこのようなことをしていたと思います。当時、私には階層があり、問題は「ノードXのすべての子と孫を見つける」ことでした。これはリレーショナルデータベースで行うのは簡単ではありません。そのため、ヘルパーテーブルとそれを設定するためのスクリプトを作成しました。私がそれを思い出せるかどうか見てみましょう...注：これは私の記憶の後で自由に行われ、テストされていません。私がそれを正しく理解したことを保証するものではありません。私の問題もあなたの問題とは少し異なっていたので、解決策が当てはまるかどうかはわかりません。

create table chain_helper (
    head int,
    tail int,
    chain_length int
)
create index chain_helper_by_head(head);
create index chain_helper_by_tail(tail);

このテーブルには、ヘッドとテールが外部キーである可能性のあるすべてのリンクが含まれているという考え方です。階層が厳密で、ループ制御が不要なため、私の場合は少し簡単でした。ソーステーブルにはidフィールドとparent_idフィールドがありました。これが私がテーブルに入力した方法です：

単純なリンクを使用してテーブルを初期化します。

insert into chain_helper (head, tail, chain_length) 
    select id, parent_id, 1 from source_table;

長さ2のすべてのチェーンをテーブルに追加し続けました。

insert into chain_helper (head, tail, chain_length)
    select parent.head, child.tail, min(parent.chain_length + 1)
    from chain_helper parent 
    join source_table child on source_table.parent_id=parent.id
    where not exists 
       (select * from chain_helper where head=parent.head and tail=child.tail)
    group by parent.head, child.tail;

（私は厳密な階層を持っていたので、集約する必要はありませんでした-私の場合、重複はありません）。

繰り返すと、長さ3などのすべてのチェーンが挿入され、挿入するものがなくなるまで、ステートメントをすべて繰り返すことができます。次に、チェーンの最大長を見つけるのは簡単です。

select max(chain_length) from chain_helper;

このソリューションでは、チェーンを簡単に表示することはできませんが、私の場合はそれは必須ではありませんでした。私は主に、結合でchain_helperを使用して、階層内の特定のノードのすべての子と孫をキャッチできるようにしました。つまり、「このサブツリーの総収益」です。

select sum(source_table.revenue) 
from source_table join chain_helper on chain_helper.tail = source_table.id
where chain_helper.head = parent_of_subtree;
于 2012-07-03T05:29:57.467 に答える
1

「The Stanford GraphBase」のセクションで、FOOTBALL Knuth は、「A が B に 5 差で勝った、B が C に 9 差で勝った、C が D に 43 差で勝った...」という形式のフットボール チーム間の試合の長い連鎖を見つける問題を考察し、引数を提供しています。 A の Z に対する予想勝率が大きいこと。彼は、これは NP 完全問題であると述べ、提案を求めています。彼が実際にプログラムしているのは、彼が層別貪欲と呼んでいるもので、 http://en.wikipedia.org/wiki/Beam_searchによく似ています。

しばらく前に、私は楽しみのために Beam Search をいじっていましたが、最終的には Limited Discrepancy Search の方が優れているのではないかと考え始めました。通常、バックトラッキングでは、より多くの仮定を作成したり、機能していないように見える仮定を撤回したりするときに、回答に小さな変更を加えます。

于 2012-07-03T05:06:30.210 に答える
0

あなたが探しているものが正確に得られるかどうかはよくわかりません。ただし、次のようなことを行います。

WITH RECURSIVE chain (artist_id, path) (
    SELECT id, id::text from artist
    UNION
    SELECT a.id, path || ',' || a.id 
      FROM artist a
      JOIN covers co ON (co.covered_by = a.id)
      JOIN chain ch ON (co.originally_by = ch.artist_id)
)
SELECT * 
  FROM artist a
  JOIN chain c ON c.artist_id = a.id
ORDER BY array_upper(string_to_array(c.path, ',')::int[], 1)
LIMIT 1;

アーティストの数が多い場合、パフォーマンスはそれほど優れていないことに注意してください。ただし、検索基準を絞り込むことができれば、それが役立つ可能性があります。

于 2012-09-27T01:49:58.190 に答える