Local transformations and conjunctive-query equivalence
Local transformations and conjunctive-query equivalence
复制标题
局部转换和联合查询等价
DOI：
10.1145/2213556.2213583
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Phokion G. Kolaitis
中科院分区：
文献类型：
--
作者：
Ronald Fagin;Phokion G. Kolaitis
在过去的几十年里，联合查询的研究在数据库系统的理论和实践中占据了中心地位。近年来，联合查询在数据集成和数据交换任务的模式映射的设计和使用中发挥了重要作用。在本文中，我们在模式映射和数据交换的背景下研究了联合查询等价性的几个不同方面。在本文的第一部分中，我们介绍并研究了基于联合查询等价的数据库实例之间的局部转换的概念。我们证明 GLAV 映射（即由源到目标元组生成依赖项指定的模式映射）的追踪过程是关于联合查询等价的局部转换。这意味着追逐过程保留有界联合查询等价性，即，如果使用足够大尺寸的联合查询无法区分两个源实例，则使用给定尺寸的联合查询，通过追踪这两个源实例获得的目标实例也无法区分。此外，我们获得了源实例之间的不可区分性水平的多项式界限，以保证追逐产生的目标实例之间的不可区分性。追踪的局部性扩展到由二阶元组生成依赖项（SO tgd）指定的模式映射，但不适用于其规范包括目标约束的模式映射。在本文的第二部分中，我们仔细研究了两个 GLAV 映射的组成。特别是，我们将 GLAV 映射分解为少量经过充分研究的类（包括 LAV 和 GAV），并完成关于何时可以保证来自这些不同类的模式映射的组合是 GLAV 映射，以及何时可以保证它们是与 GLAV 映射等效的联合查询。我们还表明以下问题是可判定的：给定由 SO tgd 和 GLAV 映射指定的模式映射，它们是否等效于联合查询？相反，已知以下问题是不可判定的：给定由 SO tgd 和 GLAV 映射指定的模式映射，它们在逻辑上是否等效？
Over the past several decades, the study of conjunctive queries has occupied a central place in the theory and practice of database systems. In recent years, conjunctive queries have played a prominent role in the design and use of schema mappings for data integration and data exchange tasks. In this paper, we investigate several different aspects of conjunctive-query equivalence in the context of schema mappings and data exchange. In the first part of the paper, we introduce and study a notion of a local transformation between database instances that is based on conjunctive-query equivalence. We show that the chase procedure for GLAV mappings (that is, schema mappings specified by source-to-target tuple-generating dependencies) is a local transformation with respect to conjunctive-query equivalence. This means that the chase procedure preserves bounded conjunctive-query equivalence, that is, if two source instances are indistinguishable using conjunctive queries of a sufficiently large size, then the target instances obtained by chasing these two source instances are also indistinguishable using conjunctive queries of a given size. Moreover, we obtain polynomial bounds on the level of indistinguishability between source instances needed to guarantee indistinguishability between the target instances produced by the chase. The locality of the chase extends to schema mappings specified by a second-order tuple-generating dependency (SO tgd), but does not hold for schema mappings whose specification includes target constraints. In the second part of the paper, we take a closer look at the composition of two GLAV mappings. In particular, we break GLAV mappings into a small number of well-studied classes (including LAV and GAV), and complete the picture as to when the composition of schema mappings from these various classes can be guaranteed to be a GLAV mapping, and when they can be guaranteed to be conjunctive-query equivalent to a GLAV mapping. We also show that the following problem is decidable: given a schema mapping specified by an SO tgd and a GLAV mapping, are they conjunctive-query equivalent? In contrast, the following problem is known to be undecidable: given a schema mapping specified by an SO tgd and a GLAV mapping, are they logically equivalent?
关系和 XML 数据交换
DOI：
10.2200/s00297ed1v01y201008dtm008
发表时间：
2010
期刊：
Synthesis Lectures on Data Management
影响因子：
--
作者：
Arenas M
通讯作者：
Arenas M