Database Constraints and Homomorphism Dualities
Database Constraints and Homomorphism Dualities
复制标题
数据库约束和同态对偶性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
W. Tan
中科院分区：
文献类型：
--
作者：
B. T. Cate;Phokion G. Kolaitis;W. Tan
全局视图（GAV）约束形成了一类数据库约束，已广泛应用于数据交换和数据集成的研究中。具体来说，不同数据库模式之间的关系通常由由一组有限的 GAV 约束组成的模式映射来描述。这种模式映射可以被视为无限数据示例集的表示。我们研究以下问题：GAV 约束的有限集何时可以通过有限的数据示例集唯一地表征？通过在该问题和同态对偶之间建立紧密联系，我们获得了唯一表征性的简单标准。我们还指出了相应决策问题的计算复杂度。
Global-as-view (GAV) constraints form a class of database constraints that has been widely used in the study of data exchange and data integration. Specifically, relationships between different database schemas are commonly described by a schema mapping consisting of a finite set of GAV constraints. Such schema mappings can be viewed as representations of an infinite set of data examples. We study the following problem: when is finite set of GAV constraints uniquely characterizable via a finite set of data examples? By establishing a tight connection between this problem and homomorphism dualities, we obtain a simple criterion for unique characterizability. We also pinpoint the computational complexity of the corresponding decision problem.