데이터베이스에서 가장 긴 관계 체인을 어떻게 찾을 수 있습니까?

Question

나는 아티스트, 노래 및 노래 사이의 큰 관계를 커버하는 postgresql 데이터베이스를 보유하고 있습니다. 나는 이런 식으로 뭔가를하려는 결국 http://www.coversproject.com/artist/longest_chain

유사한 데이터베이스의 커버 관계의 긴 사슬을 찾으려면 :

• 아티스트는 아티스트 B에 의해 원래 노래 1 덮여
• 아티스트 B는 ... 원래 예술가 C는 원래 아티스트 D
• 에 의해 노래 3 덮여
• 아티스트 C에 의해 곡이 덮여

내 경우에는 모든 아티스트가 목록에 한 번만 나타날 수 있으므로이 작업이 더 까다 롭습니다. 질문을 덜 구체적으로하기 위해 여기에 데이터베이스 구조를 단순화했는데 문제가되지 않아야합니다.

확실한 답을 줄 수있는 마법의 쿼리가없는 것 같습니다. 나는 각 쿼리의 결과를 저장하면서 다른 시작 항목으로 데이터베이스를 계속해서 쿼리하는 알고리즘을 필요로한다고 생각합니다. 잠시 후에 나는 그 시간 동안 발견 된 가장 긴 체인을 선택 하겠지만, 이것은 가장 긴 체인이 아니라 나에게 충분하다.

어떻게 수행 할 수 있었는지 알아 주실 수 있나요? (기본적으로 포스트그레스 또는 데이터베이스를 쿼리하는 스크립트 작성)

Answer 1

"스탠포드 GraphBase"섹션에서 축구 공 Knuth는 축구 팀간에 "A 비트 B 5, B 비트 C가 9, C가 D를 43으로 이길 것 "이라고 말하면서, A에 대한 예상 승리 마진이 크다고 주장한다. 그는 이것이 NP 완전 문제이며 제안을 요구한다고 말합니다. 실제로 그가 프로그래밍하는 것은 그가 층화 된 욕심이라고 부르는 것인데, 이것은 http://en.wikipedia.org/wiki/Beam_search과 많이 닮았다.

얼마 전에 Beam Search로 재미있게 놀았지만 제한적 불일치 검색이 더 나은지 궁금해지기 시작했습니다. 부분 응답의 상태를 저장하는 데 소요되는 시간을 줄이는 경향이 있습니다. 역 추적과 거의 유사합니다. 일반적으로 가정을 더 많이하거나 작동하지 않는 가정을 철회 할 때 응답에 작은 변화가 생깁니다.

Answer 2

흠, 전에 이런 식으로 일을 해왔다고 생각합니다. 그 당시에는 계층이 있었고 문제는 "노드 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 필드가 있습니다.간단한 링크

초기화 테이블 : 저는 여기에 테이블을 채워 어떻게 내가 길이 2의 모든 체인 테이블을 채우는 계속

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

:

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; 

Answer 3

내가 얻을 아주 잘 모르겠습니다 정확히 무엇을 찾고있다. 그러나, 나는 같은 것을 할 것 : 예술가의 많은, 성능이 모두 큰 수 없음을

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; 

참고,하지만 당신은 당신의 검색 기준 범위를 좁힐 수 있다면, 그것은 도움이 될 수 있습니다.