Certain answers for XML queries
Certain answers for XML queries
复制标题
DOI：
10.1145/1807085.1807112
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
C. David;L. Libkin;Filip Murlak
中科院分区：
文献类型：
--
作者：
C. David;L. Libkin;Filip Murlak
当查询不完全指定的数据库时，出现某些答案的概念，例如，在数据集成和交换场景中，或者在数据库中缺少信息。虽然在关系型情况下，这个概念很好理解，但是对于返回文档的XML查询，没有自然的类似物。我们开发了一种方法来定义一定的答案，这样的XML查询，并将其应用于不完整的信息和XML数据交换的设置。我们首先重新审视关系的情况下，并展示如何提出的关键概念相关的某些答案在一个新的模型理论的语言。这种新方法自然也扩展到了XML。我们证明了一些通用的，独立于应用程序的结果，可计算性和复杂性的某些答案产生it.Then我们把我们的注意力转向基于模式的XML查询语言与树作为输出，并提出了一种技术，用于计算某些答案，依赖于一组树的基础的概念。我们将展示如何计算这样的基础与空值的文件和文件中产生的数据交换的情况下，并提供复杂的界限。虽然在一般的复杂性，在XML数据交换中的查询回答可能是高的，我们表现出一个自然类的XML模式映射，不仅查询回答，但也可以有效地解决许多静态分析问题。
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.