November 10, 2016, 9:30 am, Room 02/022, Building 5, Saint Priest – Elena Botoeva (Free University of Bozen-Bolzano)
Title: Query Inseparability of Description Logic Knowledge Bases and TBoxes.
Abstract: Deciding inseparability of description logic knowledge bases (KBs) with respect to conjunctive queries is fundamental for many KB engineering and maintenance tasks including versioning, module extraction, knowledge exchange and forgetting. We study the combined and data complexity of this inseparability problem for ALC and for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. In the Horn case, we give a uniform game-theoretic characterisation of KB conjunctive query inseparability, and devise a number of combined complexity results ranging from P- to ExpTime- to 2ExpTime-completeness. In the ALC case, we also consider unions of conjunctive queries; we provide model-theoretic criteria of KB query inseparability, and prove that this problem is undecidable for conjunctive queries, but 2ExpTime-complete for unions of conjunctive queries. We also report some known results on the problem of whether two TBoxes give the same answers to all queries in a given vocabulary over all ABoxes.