2

我有一个大型的 postgresql 数据库，其中包含艺术家、歌曲和歌曲之间的封面关系。我想在数据库中找到最长的覆盖关系链，类似于 http://www.coversproject.com/artist/longest_chain

最后我想要这样的东西：

  • 艺术家 A 翻唱的歌曲 1 最初由艺术家 B
  • 艺术家 B 翻唱了艺术家 C 原创的歌曲 2
  • 艺术家 C 翻唱了艺术家 D 原创的歌曲 3
  • ...

在我的用例中，任何艺术家只能在列表中出现一次，这使得这更加棘手。我还在这里简化了我的数据库结构，以使问题不那么具体，但这应该不是问题。

在我看来，没有什么神奇的查询可以给我一个明确的答案。我想我需要某种算法，用不同的起始条目一遍又一遍地查询数据库，同时存储每次查询运行的结果。过了一会儿，我会选择在那段时间发现的最长的链条，这可能不是现有的最长的链条，但对我来说已经足够了。

关于如何实现这一点的任何指示？（本机在 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 以 5 分击败 B，B 以 9 分击败 C，C 以 43 分击败 D...”形式的足球队之间的长链比赛的问题，以提供论据A 对 Z 的预期胜率很大。他指出这是一个 NP 完全问题，并征求建议。他实际编写的程序是他称之为分层贪婪的东西，看起来很像http://en.wikipedia.org/wiki/Beam_search。

不久前，我花了一些时间玩 Beam Search 来寻找乐趣，但最后开始怀疑 Limited Discrepancy Search 是否更好 - 它往往需要您花费更少的时间来保存部分答案的状态，因为它非常接近回溯，您通常会在做出更多假设或撤回似乎不起作用的假设时对答案进行小幅更改。

于 2012-07-03T05:06:30.210 回答
0

我不太确定我得到了你正在寻找的东西，a 。但是，我会做类似的事情：

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 回答