Laconic Schema Mappings: Computing the Core with SQL Queries
Laconic Schema Mappings: Computing the Core with SQL Queries
复制标题
简洁模式映射：使用 SQL 查询计算核心
DOI：
--
复制
发表时间：
2009
影响因子：
2.5
通讯作者：
W. Tan
中科院分区：
文献类型：
--
作者：
B. T. Cate;Laura Chiticariu;Phokion G. Kolaitis;W. Tan
模式映射是源模式实例和目标模式实例之间关系的声明性规范。数据交换(或数据转换)问题涉及：在源模式上给定一个实例，在目标模式上物化满足模式映射的实例(或解决方案)。通常，给定源实例可能有许多不同的解决方案。在所有的解决方案中，通用解决方案和核心通用解决方案被挑出来并得到了广泛的研究。泛解是最一般的解，也代表解的整个空间，而核心泛解是最小的泛解，并且在同构下是唯一的(因此，我们可以谈论核心)。
近年来，如何设计高效的核计算算法引起了人们的极大关注。在本文中，我们提出了一种由源到目标元组生成依赖关系(S-tgds)来指定模式映射时，由SQL查询直接计算核的方法。与以前的方法不同的是，给定一个源实例，首先计算一个目标实例，然后递归地将该实例最小化到核心，我们的方法避免了构造这样的中间实例。这是通过将模式映射重写为由一阶S-tTGDS以源实例的活动域中的线性顺序指定的简洁模式映射来完成的。简洁的模式映射具有这样的特性，即根据简洁的模式映射对源实例进行“直接翻译”会产生核心。此外，简洁的模式映射可以很容易地转换为SQL，因此它可以由数据库系统优化和执行，以生成核心。我们还证明了我们的结果是最优的：线性顺序的使用是不可避免的，并且通常情况下，具有对目标模式的约束的模式映射不能被重写为简洁的模式映射。
A schema mapping is a declarative specification of the relationship between instances of a source schema and a target schema. The data exchange (or data translation) problem asks: given an instance over the source schema, materialize an instance (or solution) over the target schema that satisfies the schema mapping. In general, a given source instance may have numerous different solutions. Among all the solutions, universal solutions and core universal solutions have been singled out and extensively studied. A universal solution is a most general one and also represents the entire space of solutions, while a core universal solution is the smallest universal solution and is unique up to isomorphism (hence, we can talk about the core).
The problem of designing efficient algorithms for computing the core has attracted considerable attention in recent years. In this paper, we present a method for directly computing the core by SQL queries, when schema mappings are specified by source-to-target tuple-generating dependencies (s-t tgds). Unlike prior methods that, given a source instance, first compute a target instance and then recursively minimize that instance to the core, our method avoids the construction of such intermediate instances. This is done by rewriting the schema mapping into a laconic schema mapping that is specified by first-order s-t tgds with a linear order in the active domain of the source instances. A laconic schema mapping has the property that a "direct translation" of the source instance according to the laconic schema mapping produces the core. Furthermore, a laconic schema mapping can be easily translated into SQL, hence it can be optimized and executed by a database system to produce the core. We also show that our results are optimal: the use of the linear order is inevitable and, in general, schema mappings with constraints over the target schema cannot be rewritten to a laconic schema mapping.