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

요약

본 연구는 데이터베이스에서 주어진 사실(fact)이 부울 연결 쿼리(CQ)와 관련 있는지 여부를 결정하는 '쿼리 관련성' 문제의 복잡성을 분석했습니다. 기존에 이 문제는 쿼리 평가보다 더 어렵다는 것이 알려져 있었으나, 본 논문은 그 원인을 '자기 조인(self-joins)'에서 찾았습니다. 자기 조인의 발생을 제한하거나 금지할 경우, 쿼리 관련성의 복잡도가 쿼리 평가와 동일한 수준으로 낮아짐을 증명했습니다.

핵심 포인트

• 쿼리 관련성(Query Relevance)은 일반적으로 쿼리 답변(Query Answering)보다 더 높은 복잡도를 가집니다 (예: $\Sigma^p_2$-complete).
• 이러한 복잡성의 주요 원인은 '자기 조인(self-joins)'의 사용입니다.
• 자기 조인을 제한하거나 금지하는 구조적 제약을 도입하면, 쿼리 관련성 문제는 쿼리 평가와 동일한 효율적인 복잡도를 가질 수 있습니다.
• 온톨로지 매개 쿼리 환경에서도 상호작용 너비(interaction width)를 제한함으로써 관련성의 계산 가능성을 높일 수 있음을 보였습니다.