Certain Answers for XML Queries

Claire David, Leonid Libkin, Filip Murlak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The notion of certain answers arises when one queries incompletely specified databases, e.g., in data integration and exchange scenarios, or databases with missing information. While in the relational case this notion is well understood, there is no natural analog of it for XML queries that return documents.

We develop an approach to defining certain answers for such XML queries, and apply it in the settings of incomplete information and XML data exchange. We first revisit the relational case, and show how to present the key concepts related to certain answers in a new model-theoretic language. This new approach naturally extends to XML. We prove a number of generic, application-independent results about computability and complexity of certain answers produced by it. We then turn our attention to a pattern-based XML query language with trees as outputs, and present a technique for computing certain answers that relies on the notion of a basis of a set of trees. We show how to compute such bases for documents with nulls and for documents arising in data exchange scenarios, and provide complexity bounds. While in general complexity of query answering in XML data exchange could be high, we exhibit a natural class of XML schema mappings for which not only query answering, but also many static analysis problems can be solved efficiently.

Original languageEnglish
Title of host publicationPODS 2010: PROCEEDINGS OF THE TWENTY-NINTH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS
Place of PublicationNEW YORK
PublisherASSOC COMPUTING MACHINERY
Pages191-202
Number of pages12
ISBN (Print)978-1-4503-0033-9
Publication statusPublished - 2010
Event29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - Indianapolis
Duration: 6 Jun 201011 Jun 2010

Conference

Conference29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
CityIndianapolis
Period6/06/1011/06/10

Cite this