사실의 쿼리에 대한 관련성을 결정하는 것은 얼마나 어려운가?

우리는 다음과 같은 근본적인 문제를 고려합니다: 데이터베이스 D, 부울 연결 쿼리 (Boolean conjunctive query, CQ) q, 그리고 D 속의 사실 f 가 주어졌을 때, f 가 D 에 대해 q 와 관련이 있는지 결정하는 것입니다. 즉, S |= q 인 D 의 최소 부분집합 S 에 f 가 포함되는지 여부를 판단합니다. 쿼리 답변 설명 (query answer explanation) 에 있어 핵심적인 중요성을 가지지만, 쿼리 관련성 (query relevance) 을 결정하는 결합 복잡성 (combined complexity) 은 자세히 연구되지 않아 이 문제가 어려운 이유와 어떤 제한이 낮은 복잡성을 가져올 수 있는지 여부는 여전히 미해결 상태였습니다. 관련성은 이미 쿼리 평가 (query evaluation) 보다 더 어렵다는 것이 입증되었습니다: 구체적으로, 이진 서명 (binary signature) 을 가진 CQ 에 대해 $Σ^p_2$-완전 ($Σ^p_2$-complete) 입니다. 우리는 또한 NP-난해성 (NP-hardness) 이 이미 비순환 체인 CQ ((acyclic) chain CQ) 에 적용된다는 점을 추가로 관찰합니다. 본 연구에서는 자기 조인 (self-joins, 동일한 관계의 여러 원자) 을 문제의 원인 (culprit) 으로 규명합니다. 실제로, 우리는 자기 조인의 발생을 금지하거나 제한할 경우 관련성이 쿼리 평가와 동일한 복잡성을 가진다고 증명합니다: 구체적으로, 구조적 제한 없이 NP 인 경우와 유한한 하이퍼트리 너비 (bounded hypertreewidth) 클래스에 대해 LogCFL 인 경우입니다. 온톨로지 설정 (ontology setting) 에서는 CQ 와 DL-Lite_R 온톨로지를 포함하는 온톨로지 매개 쿼리 (ontology-mediated queries) 에 대해 유사한 결과를 도출합니다: 즉, 상호작용 너비 (interaction width) 를 제한할 경우 (이는 자기 조인 너비와 최근 도입된 '상호작용 없음' (interaction-free) 조건을 모두 일반화함) 관련성이 쿼리 답변 (query answering) 보다 더 어렵지 않음을 보여줍니다. 따라서 우리의 결과는 관련성이 쿼리 평가보다 더 어려운 요인을 정확히 지적하고, 효율적인 관련성 계산을 허용하는 자연스러운 쿼리 클래스를 식별합니다.