뷰를 통한 삭제 및 주석 전파에 대한 연구

우리는 관계형 데이터베이스에서 두 가지 클래스의 뷰 업데이트 문제를 연구합니다. 우리는 소스 데이터베이스 S, 단조 쿼리 Q, 쿼리에 의해 생성된 뷰 Q(S)를 제공합니다. 우리가 고려하는 첫 번째 문제는 주어진 튜플 t를 뷰에서 제거하기 위해 S에서 삭제하면 되는 튜플의 최소 집합 T를 식별하고자 하는 고전적인 뷰 삭제 문제입니다. 이 설정에서 두 가지 자연스러운 목표를 최적화하는 복잡성을 연구하며, 즉 뷰와 소스에 대한 부작용을 최소화하는 T를 찾는 것입니다. 두 목표 함수 모두에 대해 우리는 복잡성에서 이분법을 보입니다. 흥미롭게도, 이 문제는 같은 목표 함수 내에서 P에 있거나 NP-난해합니다. 우리의 연구에서 두 번째 문제는 주석 배치 문제입니다. S에서 튜플의 속성을 주석한다고 가정해 봅시다. 쿼리를 통해 주석을 전달하는 규칙은 쉽게 설명됩니다. 반면, 만약 우리가 뷰 Q(S)의 튜플 속성을 주석한다고 가정하면, S에서 어떤 주석이 이 주석이 뷰에 나타나게 하며 Q(S)의 다른 속성으로의 전파를 최소화할 것인가? 뷰 주석은 공유 과학 데이터 세트의 사용자 간 메타데이터를 전달하는 점점 더 유용한 방법이 되고 있으며, 우리가 아는 한 이 문제에 대한 공식적인 연구는 없었습니다. 이러한 문제에 대한 우리의 연구는 데이터 출처 또는 계보와 관련된 계산 문제에 대한 중요한 통찰을 제공합니다 --- 데이터가 데이터베이스를 통해 이동하는 프로세스입니다. 우리는 두 문제가 왜(why)와 어디(where) 출처의 두 가지 근본적으로 다른 개념에 해당함을 보여줍니다.