Data exchange beyond complete data
Data exchange beyond complete data
复制标题
超越完整数据的数据交换
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Juan L. Reutter
中科院分区：
文献类型：
--
作者：
M. Arenas;Jorge Pérez;Juan L. Reutter
在传统的数据交换设置中，源实例被限制为完整的，在这个意义上，每个事实在这些实例中要么是真的，要么是假的。虽然对于典型的数据库转换场景来说是自然的，但这种限制正逐渐成为开发需要交换允许多种解释的对象的广泛应用程序的障碍。特别是，我们的动机是两个特定的应用程序，超越了通常的数据交换场景：交换不完整的信息和交换知识库。在本文中，我们提出了一个可以处理这两个应用程序的数据交换通用框架。更具体地说，我们解决的问题，交换信息的表示系统，这基本上是有限的描述（可能是无限的）集的完整的实例。我们利用经典的语义映射指定的逻辑句子集的概念交换代表，从标准的概念的解决方案，空间的解决方案，和普遍的解决方案自然产生一个有意义的语义。我们还介绍了一类映射的强表示系统的概念，类似于查询语言的强表示系统的概念。我们通过将其应用于上述两个应用程序：交换不完整信息和交换知识库，这两个实例的表示系统的交换问题，我们的建议的鲁棒性。我们研究这两个应用程序的详细介绍，表现力，查询回答和计算解决方案的复杂性，以及算法实现的解决方案。
In the traditional data exchange setting, source instances are restricted to be complete in the sense that every fact is either true or false in these instances. Although natural for a typical database translation scenario, this restriction is gradually becoming an impediment to the development of a wide range of applications that need to exchange objects that admit several interpretations. In particular, we are motivated by two specific applications that go beyond the usual data exchange scenario: exchanging incomplete information and exchanging knowledge bases. In this paper, we propose a general framework for data exchange that can deal with these two applications. More specifically, we address the problem of exchanging information given by representation systems, which are essentially finite descriptions of (possibly infinite) sets of complete instances. We make use of the classical semantics of mappings specified by sets of logical sentences to give a meaningful semantics to the notion of exchanging representatives, from which the standard notions of solution, space of solutions, and universal solution naturally arise. We also introduce the notion of strong representation system for a class of mappings, that resembles the concept of strong representation system for a query language. We show the robustness of our proposal by applying it to the two applications mentioned above: exchanging incomplete information and exchanging knowledge bases, which are both instantiations of the exchanging problem for representation systems. We study these two applications in detail, presenting results regarding expressiveness, query answering and complexity of computing solutions, and also algorithms to materialize solutions.