데이터 그래프에서 선호 서브셋 수리의 계산 복잡성

일관성이 없는 지식 기반을 수리하는 문제는 데이터베이스 이론 및 지식 표현 및 추론 커뮤니티 내에서 오랜 역사를 가지고 있으며, 특히 구조화된 데이터의 관점에서 그러합니다. 그러나 실제 도메인에서 사용 가능한 데이터가 점점 더 복잡하고 상호 연결됨에 따라, 데이터를 쿼리하고 추론하는 더 적합한 방법을 허용하기 위해 새로운 유형의 저장소, 표현 언어 및 의미론을 개발할 필요성이 자연스럽게 나타납니다. 그래프 데이터베이스는 반구조화된 데이터 간의 관계를 표현하는 효과적인 방법을 제공하며, 이러한 연결을 효율적으로 처리하고 쿼리할 수 있게 해줍니다. 본 연구에서는 그래프 데이터베이스에서 데이터 값을 가진 우선 순위 수리 문제에 주목하며, 무결성 제약으로 Reg-GXPath 표현을 기반으로 하는 일관성 개념을 사용합니다. 우리는 가중치, 다중 집합 및 집합 기반 우선 순위 수준을 포함하는 표준 서브셋 수리 의미론에 기반한 여러 선호 기준을 제시합니다. 우리는 가장 일반적인 수리 작업을 연구하여, 선호 기준이 활용 가능한 경우와 동일한 계산 복잡성을 유지할 수 있음을 보여줍니다. 전체 그림을 완성하기 위해, 우리는 이 설정에서 일관된 쿼리 응답의 복잡성을 탐구하고, 도입된 모든 선호 기준에 대해 엄격한 하한 및 상한을 얻습니다.