ACM

ACM通信

首页 / 杂志存档 / 2010年1月(第53卷第1期) / 模式映射语言的结构表征 /全文

研究突出了

模式映射语言的结构表征

Balder ten Cate, Phokion G. Kolaitis
ACM通讯，2010年1月，53卷第1期，101-110页
10.1145/1629175.1629201
评论

认为: 打印手机应用程序 ACM数字图书馆全文(PDF) 数码版分享: 通过电子邮件发送在reddit分享在StumbleUpon分享分享到黑客新闻在推特上分享在Facebook上分享

信息集成是所有主要组织，企业和政府都面临的一个关键挑战。近年来，这一挑战的两个研究方面受到了相当多的关注，即数据交换和数据集成。模式映射是描述两个数据库模式之间关系的高级规范，系统地使用模式映射有助于数据交换和数据集成的研究。模式映射通常用基于逻辑形式的声明性语言表示，并在选择时考虑到两个标准:(a)表达能力足以指定有趣的数据互操作性任务，以及(b)理想的结构属性，如查询可重写性和普遍解决方案的存在性，这些反过来意味着良好的算法行为。

在这里，我们从一个新的角度检查模式映射的这些和其他基本结构属性:这些属性的适用范围有多大?哪些模式映射拥有这些属性，哪些没有?我们通过建立结构特征来解决这些问题，即当且仅当模式映射可以用特定的模式映射语言指定时，模式映射具有特定的结构属性。更具体地说，我们获得了模式映射语言的结构特征，例如全局即视图(GAV)依赖关系和局部即视图(LAV)依赖关系。这些结果描述了模式映射研究中可用的工具，并精确地指出了模式映射的属性，即从一种模式映射语言切换到另一种语言时可能获得或失去的属性。

回到顶部

1.简介

信息集成的目的是将分布在多个异构源上的信息合成为单一的统一格式。信息集成已经被认为是当今大型组织面临的一个关键(和昂贵的)挑战(见Bernstein和Haas)^3.，12)．这也是很容易理解的¹²信息集成不是一个单一的问题，而是一系列相互关联的问题的集合，这些问题包括从源中提取和清理数据，为集成数据导出统一格式，将源中的数据转换为符合统一格式的数据，并根据统一格式回答查询。在本文中，我们关注的是关系信息集成，也就是说，我们假设源是(不同的)关系模式上的数据库，称为源或当地的模式，统一的格式是其他一些关系模式，称为目标或者是全球模式。关系模式或简单的模式由关系名称和每个关系的列名称组成。一个数据库实例或一个给定模式的实例是一个集合，对于模式中的每个关系名，它包含一个有限关系(即一个记录表)。中给出了源模式和目标模式的示例图1．源模式由三个关系名称组成，其中包含关于来自制造商的直接订单的信息以及关于零售销售的信息;目标模式由单个关系名称组成，用于汇总销售记录。图1还将描述一个源实例和三个目标实例，稍后将使用它们来说明主要概念。

信息集成的两个重要方面是数据交换和数据集成。这两个方面都涉及信息集成的实现，但它们采用截然不同的方法。数据交换是将驻留在不同数据源中的数据转换为目标模式下的结构化数据的问题;特别是，数据交换需要在数据从源中提取并重组为统一格式之后，将数据物化。相反，数据集成可以描述为符号或虚拟集成:用户可以通过统一的格式接口提出查询并获得答案，而数据仍然在源中，没有发生重新构造的数据的具体化。图2描述数据集成和数据交换任务。

在数据交换和数据集成中，必须说明本地模式和全局模式之间的关系。实现这一点的一种方法是通过人工专家编写的程序或SQL脚本;然而，由于所涉及的转换的复杂性，这可能是一项昂贵且容易出错的工作。相反，研究界引入了模式映射，这是一种更高层次的抽象，使得将模式之间的关系规范从转换的实际实现中分离出来成为可能。模式映射是描述两个数据库模式之间关系的声明性规范。近年来，模式映射被广泛用于指定数据互操作性任务，并被视为数据交换和数据集成的基本构件(参见，例如，调查^14，15)．模式映射的使用有助于用户理解和推断源模式和目标模式之间的关系;此外，模式映射可以自动编译成各种语言的可执行脚本。

中给出了一个模式映射的具体例子图1．模式映射由两句一阶逻辑指定。第一句话断言只要源关系DirectCustomer包含一个三元组(v₁，v₂，v_3.)的值和源关系DirectOrder包含一个四元组(v₁，v₄，v₅，v₆)的值，以便这两个元组中的cust-id的值重合，那么目标关系Sales必须包含四元组(v₁，v₂，v₄，v₅)．第二句断言只要源关系Retail包含一个四元组(w₁，w₂，w_3.，w₄)的值，那么一定存在某些值V使目标关系Sales包含四个(w₂，V, w_3.，w₄)．显然，这一对(我,我₁)由源关系构成我和目标关系J₁满足这两个公式;对于配对(我,我₂)．相比之下，这一对(我,我_3.)不能满足第一个公式，因为Sales关系不包含所需的四倍(05-01-2009,UCSC, TFT-933SN-Wide, 100)。

这个例子还揭示了数据交换和数据集成中出现的一些主要概念和算法问题。在数据交换端，假设我们希望转换上面的源实例我到目标实例J中的模式映射图1．至少有两个不同的目标实例，它们一起是源实例我，满足模式映射规范;事实上，很容易看到有无限许多这样的目标实例。那么，我们应该选择哪一个实现呢?是什么使一个目标实例成为比另一个“更好”的实现候选实例，以及如何计算一个实例?我们将会看到，通用解决方案这是实现的首选目标实例。在数据集成方面，假设用户对目标模式提出查询。通过对满足模式映射规范的不同目标实例(以及给定的源实例)进行查询，可以得到不同的答案。那么，数据集成中目标查询的“正确”语义是什么呢?是否可以将目标查询重写为基于源模式的查询，以便可以直接针对给定的源实例计算它们?这将引导我们认识到确定的答案和允许查询重写．在下一节中，我们将介绍一些最常用的模式映射语言，包括全局即视图(GAV)依赖关系和本地即视图(LAV)依赖关系，我们将发现在这些形式中指定的模式映射确实允许通用解决方案，并允许重写关系数据库中最常见的查询(参见图2)．

系统地使用模式映射的系统是Clio，它是一个数据交换系统，最初是IBM Almaden研究中心的一个研究原型，现在是IBM信息集成工具套件的一部分。¹³克里奥的建筑被描绘在图3．这个系统有一个的模式匹配组件,模式映射的一代组件和一个执行脚本的一代组件。模式匹配组件生成一组源模式和目标模式中属性之间的对应关系;这些通信是通过与用户的交互以及允许用户干预和做出更改的图形用户界面自动或半自动地导出的。模式映射生成组件以这些属性对应作为输入，并返回模式映射。通常，有不止一种模式映射与一组属性对应保持一致。Clio只产生其中一种可能的模式映射，但用户可以再次干预并编辑系统返回的模式映射。最后，可执行脚本生成组件将这个模式映射自动转换为一组使用某种语言(如SQL或XSLT)的脚本。

回到顶部

2.架构映射和语言

在本节中，我们定义了模式映射的基本概念，并介绍了研究界研究的一些主要的模式映射语言。

2.1.基本概念

一个(关系)模式是一个元组R= (R₁、……R_n)，每个关系符号都有固定的数量(属性的数量)。一个R-实例是一个元组我= (R₁^我、……R_n^我)的有限关系，它们的性与的关系符号的性相匹配R．一个事实的我是一个表达式R_我一个,在那里我n而且一个值的元组属于关系吗R_我^我．的活跃的领域的我,用adom（我)，是关系中出现的所有值的集合R_我^我, 1我n．我们通常会使用两种不相交的模式，称为源模式年代= (年代₁、……年代_n)和目标模式T= (T₁、……T_米)．一个年代-instance被称为a源的实例和一个T-instance被称为a目标实例．当我们考虑一对实例(我,我)，据了解我是源实例和J是一个目标实例。

如前所述，模式映射是描述两个模式之间关系的声明性规范。更准确地说,一个模式映射是一个三米= (S T),年代是源模式，T目标图式与年代，是某种逻辑形式主义中的一组句子(即没有自由变量的公式)。这是语法架构映射的视图。两者之间也存在互补语义接下来我们将介绍的模式映射视图。让我是一个源实例J目标实例。我们说J是一个一个模式映射M= (S T，)如果(我,我）=，这意味着(我,我满足的每一句话。因此，从语义的角度来看，这是一种模式映射米可以被认为是三倍米= (S T),W是所有对(我,我),这样J是解决方案我关于米．因此，作为语义对象，模式映射米是三倍米= (S T，W),年代是源模式，T目标图式与年代,W是一对的集合(我,我),我一个源实例和J目标实例。

让l做一种逻辑的语言，让一种集合l句子,让米= (S T，W)是作为语义对象给出的模式映射。我们说米是L-definable由对于每个源实例我每个目标实例J，我们有那个(我,我）W当且仅当(我,我）．当我们在续集中处理模式映射时，从上下文可以清楚地看出当前的模式映射是被视为语法对象还是语义对象。

例2.1。为了说明这些概念，请考虑中的模式映射图1．在本例中，源模式年代包括关系DirectCustomer、DirectOrder和Retail，而目标模式T由单一关系Sales组成。然后通过模式映射描述源和目标之间的关系米= (S T，)，由中所列的两个一级句组成图1．作为一个语义对象，米是三元组(S T，W),W由所有对组成(我,我)满足中两句话。特别是成对的(我,我₁)和(我,我₂)属于W，但这一对(我,我_3.)没有。换句话说,J₁而且J₂是解决方案我w.r.t.来米,但J_3.不是。

2.2.模式映射语言

什么是指定模式映射的“好”语言?为了解决这个问题，让我们反思一下E.F. Codd在40年前提出的关系数据库模型。⁴该模型成功的原因之一是它支持功能强大的高级数据库查询语言，例如关系代数而且关系演算，它们构成了SQL的基础。关系代数和关系演算具有与一阶逻辑相同的表达能力⁵；事实上，关系演算是为数据库量身定制的一阶逻辑的语法变体。因此，乍一看，我们很自然地会问:一阶逻辑也可以用作模式映射语言吗?然而，我们不难发现，数据集成和数据交换中的基本算法问题，如解的存在性和查询回答，变成了不可判定的如果在指定数据库模式之间的关系时允许不受限制地使用一阶逻辑(直观地说，这是因为这类任务涉及测试一阶句子的可满足性，因为它们对源实例的所有解决方案进行量化)。因此，我们必须确定一阶逻辑的适当子语言，以便在数据互操作性目的的表达能力和算法属性之间取得良好的平衡。为了实现这一目标，让我们考虑每种模式映射语言都应该支持的以下基本任务。

复制(昵称):将源关系复制到目标关系中，并对其重命名。
投影(列删除):通过删除源关系的一个或多个列来形成目标关系。
增加(列添加):通过向源关系添加一个或多个列来形成目标关系。
分解:将一个源关系分解为两个或多个目标关系。
加入:通过连接两个或多个源关系来形成目标关系。
以上各项的组合:例如，结合连接和列扩充。

可以很容易地用一阶逻辑指定这些任务，如下所示。对于具体性，我们使用二或三的关系。

可以看到，上述公式在句法上有惊人的相似性。事实上，它们都属于一类一阶公式生成依赖项的源到目标元组我们在下面定义它。

如果R= (R₁、……R_n)是一个关系模式，那么原子公式在R是一种表达形式吗R_我（x),我n而且x长度变量的元组是否等于的维度R_我．
一个tuple-generating依赖(tgd)一阶公式是这样的吗

在哪里x而且y是变量的元组，（x)是原子公式与中变量的结合x中的每个变量x的至少一个连词中出现（x)和(x, y)是原子公式与中的变量的结合x而且y．

一个满tgd右边没有存在量词的TGD，也就是说，它是这样的形式吗x（（x) (x))。

一个源到目标tuple-generating依赖（s - t tgd)是一种TGD（x)是源模式上原子公式的结合年代和(x, y)是目标模式上原子公式的连接T．

非正式地，s-t tgds断言，如果一种事实模式出现在源中，那么另一种事实模式必须出现在目标中。他们也被称为global-and-local-as-view (GLAV)依赖关系。近年来，在数据交换和数据集成的背景下，s-t tgds得到了广泛的研究^14，15因为，尽管它们的语法简单，但它们可以表达应用程序中出现的许多数据互操作性任务。此外，s-t tgds具有理想的结构特性，我们将在下一节讨论这些特性。以下两种依赖关系是s-t tgds的重要特殊情况。

一个GAVDependency是一个s-t TGD，其中含义的右手边由单个原子公式组成。因此，这就是GAV依赖的形式

与（x)是源模式上原子公式的结合U（x的原子公式，这样在目标模式上的变量x的人都在x．

一个洗手间Dependency是一个s-t TGD，其中左手边的含义是单个原子公式。因此，LAV依赖关系是这样的

与R（x)源模式上的原子公式和(x, y)原子公式在目标模式上的结合。

再次考虑中的模式映射图1．第一个句子用来指定模式映射是GAV依赖项，而第二个句子是LAV依赖项。还要注意的是，Copy和Projection任务的表达式都是GAV和LAV依赖项，augment和Decomposition任务的表达式是LAV依赖项，Join任务的表达式是GAV依赖项。分解任务的表达式是一个完整的tgd。很容易看出，每个完整的tgd在逻辑上等价于有限多个GAV依赖项。例如，完整的tgdx, y, z（P（x, y, z）U（x, y）V（y, z))的分解任务在逻辑上等价于由GAV依赖项组成的集合x, y, z（P（x, y, z）U（x, y)),x, y, z（P（x, y, z）V（y, z))。

在用于数据交换和数据集成之前，元组生成依赖关系已经在上下文中进行了深入研究依附理论在20世纪70年代和80年代。依赖理论是对数据库完整性约束的研究;在这种情况下，元组生成的依赖项具有理想的算法属性，并在特殊情况下包含数据库中许多众所周知的完整性约束类，如包含依赖项、连接依赖项和多值依赖项。¹⁰值得注意的是，元组生成的依赖关系似乎在很久以前就已经出现了(至少以隐式形式出现)。事实上，在最近的一篇文章中²为欧几里得的元素提出了一个正式的系统，作者令人信服地认为元素中的定理可以用元组生成的依赖关系表示!直观地说，这是因为典型的欧几里得几何定理指出，如果几何物体(点、线、三角形或圆)之间存在某种模式，那么几何物体之间也必然存在另一种模式。

回到顶部

3.架构映射的属性

在本节中，我们将介绍模式映射的几个结构属性，这些属性在数据交换和数据集成的文献中被广泛使用。它们将在模式映射语言的描述中发挥关键作用。然而，在介绍这些属性之前，我们需要介绍数据交换和数据集成中的一些重要概念。

同态．模式映射研究中的一个核心概念是同态．让K而且K是同一个模式上的两个实例R= (R₁、……R_n)．一个同态K来K是活动域的函数K到活动域K’这样如果(一个₁、……一个_米）R_我^k,然后(h（一个₁、……一个_米）)R_我^k＇,因为我= 1,…,n．

一个同态h据说是常数在一组X如果h局限于X dom（h)是身份函数,即h（x) =x,如果xX而且h（x定义)。这里，我们将考虑目标实例之间的同态，我们将要求它们在某些源实例的活动域上是恒定的。这一要求背后的基本原理如下。通常，当从源到目标交换数据时，给定源实例的活动域中的元素是“已知”值。但是，现有的模式映射可能没有指定源和目标之间的关系。反过来，这可能会强制使用“未知”值，称为标记为零位，以实现给定源实例的解决方案。因此，目标实例可能同时具有“已知”值(源自源实例)和“未知”值(新鲜选择并充当占位符)。标记为null的一个例子是值N₁在目标实例中J₁在图1．同态需要保持“已知”值不变，但可以自由地用另一个“已知”或“未知”值替换“未知”值。

通用解决方案．让米= (S T，)是一种模式映射。回想一下,如果我源实例是?的解决方案我关于米是一个目标实例J这样,(我,我）=。一般来说，是一个源实例我可能有多个解，事实上，无穷多个;特别是，这对于模式映射是成立的米由s-t TGDS指定，因为如果J是解决方案我关于米，则每个实例J”包含J(作为一组事实)也是一个解决方案我．在这些解决方案中，哪一个应该实现我是否转换为目标实例?为了解决这个问题，下面的一个概念通用在Fagin等人中介绍了解决方案。⁷

让米= (S T，W)是一个模式映射，并让我成为一个源实例。目标实例J是一个I的通解如果

J是解决方案我．
对于每个目标实例J这是一个解决方案我，存在同态h：J J这是永恒不变的。我)．

这个概念背后的直觉，在图4通用解决方案是一种“最通用”的解决方案，因为它所包含的信息不多于也不少于给定模式映射所指定的信息。

例3.1。考虑源实例我在图1．一个解决方案我相对于给定的模式映射是目标实例J₁．请注意,N₁中没有出现的值我，因此被解释为标记为null。另一个解决方案我是目标实例J₂，也就是J₁除了那个标记为空的值N₁取而代之的是UCLA。然而,J₂包含了模式映射没有隐含的信息，即2009年5月3日订单的客户是UCLA，因此，它不是一个通用的解决方案。事实上，有一个同态来自J₁来J₂活性域上的常数我（N₁与加州大学洛杉矶分校对应)，但反之则不然。

查询和特定答案．非正式地,查询是用户对数据库提出的问题。更正式,查询问接受一个实例作为输入K并返回一个关系作为输出问（K)的固定性，其值来自的活动域K．假设现在我们有了源模式和目标模式之间的模式映射。假设还有一个查询问在目标模式上提出，并且是一个源实例我是给定的。什么回答问使用源实例我的意思吗?如前所述，可能有无穷多个解J对于给定的源实例我；此外,如果问在不同的解决方案上评估J为我，有可能每次得到不同的答案。这种模糊性提出了在数据交换和数据集成中为查询回答提供精确语义的概念问题。研究界采取的方法是采用确定的答案语义学，这一语义学起源于不完整数据库的研究(参见范德梅登¹⁹)．

让米= (S T，)是一个模式映射，并且问对目标模式的查询T．如果我那么，是源实例吗I上q关于M的确定答案,表示一定_米（问）（我)，是集合

一定的答案语义提供了保证，如果一个元组t属于特定的_米（问）（我),然后t属于结果问(J)的问在每一个解决方案J为我．很容易看到，每个元组在某些_米(问)(我)值的元组是从我．因此，每个模式映射米诱发某种(语义)转换_米从对目标模式的查询到对源模式的查询，因此如果问如果查询是针对目标模式的，那么这个转换将查询与之关联确定_米(问)在源模式上，具有相同的相似性问并且是由确定定义的_米（问）（我) = {问（J)：J是解决方案我关于米}。

表面上看，确定的答案语义是无效的，因为计算确定_米(问)(我)可能需要计算无穷多个集合的交集。然而，对于许多常见的查询，存在计算其特定答案的有效算法。

合取查询是一阶公式的形式wX（x, w), (x, w)是原子和(或)等式的连词。连接查询是关系数据库中最常见的查询。他们也被称为项目select-join(SPJ)查询，因为它们正是使用选择、投影和连接操作在关系代数中表示的查询;特别是，使用SELECT FROM WHERE构造可以很容易地在SQL中表示连接查询。一个连接查询的并集是合取查询的有限分离;同样，它们是使用选择、投影、连接和联合操作在关系代数中表示的查询。

在信息集成中，计算特定答案的主要方法是尝试将针对目标的查询重写为针对源的查询。在数据交换中，人们希望利用物化解决方案，并使用它来获得目标查询的特定答案。这两种方法都产生了计算连接查询并集确定答案的多项式时间算法。特别是，如Fagin等人所示，⁷利用通解可以得到合取查询并集的确定解。具体地说,让米= (S T，)是一个模式映射，它是s-t TGDS的有限集，并让问是连词查询的一个联合T．如果我是源实例和J是一个通用的解决方案我,然后确定_米(问)(我)＝问(J),在那里问(J)是通过第一次计算得到的结果吗问(J)然后只保留那些包含活动域的值的元组我只有。

例3.2。回到示例模式映射米和源实例我从图1，考虑连接式查询问在给定的目标模式上

它要求所有成对的产品(x, y)，以至于有顾客买了x而且y(部分数量)在同一天。不难看出，对于每一个解J的我关于米，这对(Quadcore-9950-PC,TFT-933SN-Wide)属于问(J)．换句话说，这个元组属于问在我关于米．事实证明，特定的答案问在源实例上我答案是什么问(我),在那里问的是以下源架构上的连接查询的并集:

请注意,零售Relation不提供有关买方姓名的信息，因此只能对的某些答案提供身份对问．

或者，特定的答案问在我可以通过评估来计算吗问关于普遍解J₁的我，并且只保留那些只包含活动域中值的元组我．

架构映射的结构属性．回想一下模式映射米可以看作是句法对象，也可以看作是语义对象。作为句法宾语，米由三次方(S T，)，是某种逻辑形式主义的一组句子;作为一个语义对象，米由三次方(S T，W),W是一对(我,我),我一个源实例和J目标实例。在接下来的内容中，每当我们写下(我,我）米，我们的意思是(我,我）或者,(我,我）W这取决于米作为句法对象或语义对象给出。

现在我们准备展示模式映射的结构属性，它将在我们的表征结果中发挥关键作用。我们首先介绍在数据交换和数据集成中广泛使用的三个这样的属性。

定义3.3。设M为模式映射．

目标同态下的闭包：我们说M在目标同态下是封闭的吗if for all (I, J)M和对于所有同态h: J对于adom(I) J'是常数，我们有(I, J')）米．（看到图5一个)．
承认普遍的解决方案：我们说M承认普遍的解决方案如果对于每个源实例I, I w.r.t M有一个通用解J．
允许连接查询重写：我们说M允许连接查询重写如果对于目标模式上的连接查询的每个联合q，特定的回答查询某些米（问）可以通过源架构上的连接查询的联合来定义。换句话说，源模式上的连接查询有一个联合q'某些_米（问）（我) =问的（我)，对于每个源实例I．

目标同态下的闭包条件和承认普遍解的前两个条件配合得很好。正如费金等人所观察到的，⁷如果模式映射在目标同态下是封闭的，并且允许通用解决方案，那么对于每个源实例我的所有解的(通常是无限的)空间我关于米是否可以由单个目标实例完全描述J，即通过任何普遍解J为我．这是因为如果J是普遍的我而且米在目标同态下是封闭的，那么对于每个目标实例J '，我们有J '是解决方案我当且仅当存在同态h: JJ '这是恒定的adom(我)．我们顺便提一下，这两种条件合在一起还意味着核心通用解，它们是最小的通用解(参见Fagin et al。⁸)．因此，这两个条件是基础数据交换．的上下文中，允许连接查询重写的第三个条件非常重要数据集成，因为它意味着在多项式时间内(在数据复杂性的意义上)，目标上的合取查询并的某些答案是可计算的。

众所周知，每个模式映射都具有目标同态下闭包、允许全集解和允许合并查询重写的所有三个条件米可由有限集s-t tgds定义。同态下的闭包很容易从定义中得到;承认普遍的解决方案显示在费金等人。⁷使用追逐过程．在GAV依赖的情况下，通过简单地替换每个目标关系符号，可以很容易地将针对目标的连接查询的并集转换为针对源的连接查询的并集P定义的源上的连接查询的联合P．在任意s-t tgds的情况下，允许合并查询重写是通过首先“分解”给定的s-t tgds到GAV依赖和LAV依赖，然后应用来自Abiteboul和Duschka的结果¹杜施卡和杰尼色列。⁶我们把这些结果归纳为一个定理。

定理3.4。由有限的s-t tgds集合定义的每个模式映射在目标同态下是闭的，允许通用解，并允许合并查询重写．

接下来，我们定义模式映射的三个附加属性。

定义3.5。设M为模式映射．

目标交叉口下封闭：我们说M在目标交叉口关闭了吗如果对于所有源实例I和所有目标实例J₁，J₂如果(I, J₁）米和(我,我₂）米,也（我,我₁J₂）m(见图5 b．）
关闭在联盟：我们说M是联盟下封闭如果（，）M，为所有人（我₁，J₁）M,（我₂，J₂）M，我们也有（我₁我₂，J₁J₂）米．（看到图5 c．）
n模块化：设n为正整数。我们说M等于n模块化如果当一对(I, J)不属于M时，就有一个子实例I'我I使|adom (I')| n and (I'， J)不属于M．

直观地说，如果解决方案可以以“模块化”的方式构造，即以元组为基础，那么模式映射在union下是封闭的。同样的,n模块性断言if (我,我）米，那么对这一事实有一个简明的解释;这一财产也可以被视为放松关闭下的工会。

现在我们就刚才介绍的性质给出几个有用的命题。

命题3.6。设M为模式映射．

如果M是由GAV依赖的有限集合定义的，那么M在目标交集下是封闭的．
如果M是由有限的LAV依赖集定义的，那么M在并集下是闭的．
如果M是由有限的s-t tgds定义的，那么M对于某个n 1是n模的．

证明。根据定义可以很容易地推导出前两部分。对于第三部分，假设米是一个模式映射，可由有限的s-t tgds集合定义。让n是s-t TGDS左边发生的变量的最大数目。我们声称米是n模块化。假设(我,我）米．然后是s-t tgdx（（x）y（x, y)和一个由from值组成的元组aadom(我)这样,(我,我）（一个）¬y（一个y)．现在,让我的子实例我只包含值一个．那么，情况仍然是(我,我) =（一个）¬y（一个y)，因此(我”,J）米．

回到顶部

4.语言特征

本节包含本文的主要技术成果，这些成果产生了前面几节中考虑的各种模式映射语言的结构特征。我们从由LAV依赖项指定的模式映射开始。

定理4.1。对于所有模式映射M，以下是等价的:

M可由LAV依赖的有限集合定义．
M在目标同态下是封闭的，允许通解，允许合取查询重写，在并集下是封闭的．

证明。言外之意(1)(2)由定理3.4和命题3.6推导而来。现在我们证明这一推论(2)这个证明背后的思想是，因为米在源实例的联合通用解决方案下是否关闭我可以用通用的解决方案来构造我．这意味着，在定义我们的模式映射时，我们只需要考虑到同构之前有限数量的源实例，即那些只包含一个元组的实例。在接下来的内容中，我们将使这个想法更加精确。

假设米满足列出的条件。让R₁、……R_n是源模式的关系，并让D是由…组成的集合k不同的值,k=最大_我n参数数量(R_我)．让事实成为所有可能的事实的集合R_我（d₁、……d_l),我n, l=参数数量(R_我),d₁、……d_lD．为每一个事实,让我是一个仅包含事实的源实例，并让J成为一个通用的解决方案我．让PosDiag_我（x)是I正图，即所有真实的事实的结合我(它只包含一个事实)和letPosDiag_J（x, y的正图J在哪里x的元素有多少变量就有多少变量adom（我),y有多少元素就有多少变量adom（J) \adom（我)．让是以下LAV依赖:x（PosDiag_我（x）yPosDiag_J（x, y))。最后，设2 = {＼事实}。我们认为这定义了米．

首先,我们证明稳健:每一个(我,我）米满足。假设(我,我）米，并取任何．更进一步，假设的先行词是满足于(我,我)进行变量赋值h．换句话说,h同态来自哪里我来我．让问是连词查询的确定答案查询yPosDiag_J（x, y)．自米允许连接查询重写，问可以由连接查询的并集定义。此外,由于yPosDiag_j（x, y)满足于J，这是一个通用的解决方案我的所有解都满足我．换句话说,问是满意的我，因此，在我下作业h．因此,(我,我)满足．

接下来,我们证明完整性:每一对(我,我使满意的属于米．假设(我,我)满足。写我作为我＝我₁.．.我_n其中每个我_我只包含一个事实。然后每个(我_我，J)仍然令人满意。自我_我包含一个单一事实，它必须同构到我对于一些事实利用这个事实(我_我，J)满足的一个普适解的同态性我_我来J常数,adom(我_我)，因此，通过目标同态下的闭包(我_我，J）米．紧随其后的是工会关闭(我,我）米．

我们的下一个结果描述了由GAV依赖项指定的模式映射。

定理4.2。对于所有模式映射M，以下是等价的:

M可由GAV依赖的有限集合定义．
M在目标同态下封闭，允许通解，允许合取查询重写，在目标交下封闭．

证明。(提示)含义(1)(2)由定理3.4和命题3.6推导而来。寓意(2)(1)，我们首先展示每个模式的映射米满足(2)n模块化对一些n> 0。对于每个目标关系R,让问_R=一定_米（Ry),y是具有适当长度的不同新鲜变量的序列。注意,因为米允许连接查询重写，问_R可以编写为连接查询的联合。现在,让n是每个变量中出现的最大变量数问_R．使用假设米承认通解，在目标同态下闭，在目标交下闭，可以证明米是n模块化。

在此之后，推论(2)(1)的建立与定理4.1的证明相同。我们不考虑由一个元组组成的所有源实例，而是考虑所有源实例我与|adom(我)|n．在同构之前，这样的源实例是有限的。此外，它可以显示，使用交集下的闭包，每个都有一个无空的普遍解，因此只有完整的需要S-t TGDS来描述它们。

现在我们关注由任意s-t tgds指定的模式映射。如定理3.4所示，每个模式映射由有限的s-t TGDS集合在目标同态下是闭的，允许通解，并允许合并查询重写。下一个结果断言，满足这些条件的任何模式映射都可以由无限s-t tgds的集合。

命题4.3。如果一个模式映射M在目标同态下是封闭的，允许通用解，并允许合并查询重写，那么M是可由无限个s-t tgds集合定义的．

证明。(提示)假设米满足列出的属性。考虑一个源实例我和一个目标实例J这样J是一个通用的解决方案我关于米．的每个元素adom(我)，引入一个不同的变量x_我的每个元素adom (J)＼adom(我)引入一个不同的变量y_j．定义PosDiag_我（x中所有原子公式的连接x适用于我(在选定的赋值下)和定义PosDiag_我（x, y像明智的。最后，设为所有s-t tgds的集合_我,我的形式x（PosDiag_我（x）yPosDiag_J（x, y)),我是源实例和J是一个通用的解决方案我关于米．使用一个类似于定理4.1证明中使用的论证，它可以被证明定义米．

命题4.3能否被加强为由a指定的模式映射的表征有限的s-t tgds集合?费金等人证明了下一个结果，⁹这表明这是不可能的。

命题4.4。一阶句定义的模式映射xyz（RxzSyz）是否在目标同态下封闭，允许通解，允许合并查询重写，但不能被任何有限的s-t TGDS定义．

命题4.3可以转化为模式映射的表征吗无限s-t tgds集合?接下来的观察表明这是不可能的。

命题4.5。由下面无限集的s-t tgds定义的模式映射不承认通用的解决方案：

证明。(提示)很容易看出没有解我= {巴勒斯坦权力机构}可以是通用的。在这里，所有实例(因此所有解)都是有限的这一假设是至关重要的。

命题4.4意味着必须考虑额外的属性，以便描述由有限的s-t tgds集合定义的模式映射。结果是加法n模块化,对于一些n> 0，产生这样的表征。

定理4.6。对于所有模式映射M，以下内容是等价的：

M可由有限集s-t tgds定义．
M在目标同态下是封闭的，允许通解，允许合取查询重写，并且对某个n是n模的> 0。

我们通过简要评论本文前一版本中提出的其他特征来结束这一节。¹⁷观察到的情况允许连接查询重写与其他结构条件不同的是:后者是模型理论条件，而前者是指特定的语法定义的查询类。因此，我们很自然地会问:允许连接查询重写的条件是否可以被模型理论性质的条件所取代?为此，我们考虑反映源同态，它大致说明了源实例之间的每一个同态我,我的的任意通解延伸到同态我的任何普遍解决方案我”。我们证明了定理4.1中LAV依赖的结构刻画和定理4.6中s-t tgds的结构刻画在允许合并查询重写为反映源同态的条件下成立。进一步，我们将继续研究假定模式映射是一阶可定义的特征。对于所有模式映射，我们都建立了这个米可以用一阶句子来定义，米是可由GAV依赖的有限集合定义的当且仅当米在目标同态下闭，承认全称解，反映源同态，在目标交下闭。这一证明充分利用了罗斯曼研制的精密机械¹⁶证明了有限上的保-欠同态定理。

回到顶部

5.可定义性的复杂性

我们的特征描述提供了测试用一种语言定义的模式映射是否也可以用另一种语言定义的工具。例如，我们的结果表明，一个由有限集s-t tgds定义的模式映射，当且仅当它在目标交集下是封闭的时，它是由有限集GAV依赖定义的:此外，当且仅当它在联合下是封闭的时，它是由有限集LAV依赖定义的。在这里，我们指出计算复杂度测试不同语言的可定义性。

首先，假设问题的输入是一个有限的s-t tgds集合。结果总结如下表。

这些证明还产生了在较小的语言中构造等效模式映射的有效方法，只要它存在。我们的证明是基于可定义性问题到s-t tgds的蕴涵问题给定两个模式映射米₁，米₂，由有限集s-t tgds指定，当(我,我）米₁也(我,我）米₂？我们证明了np完全中的后一个问题;此外，它是在PTIME如果米₁是由LAV依赖项指定的米₂由GAV依赖性。

也很自然地要考虑这样一个问题:在本文研究的模式映射语言中，测试由一阶句子指定的模式映射是否可定义。然而，无论我们考虑什么模式映射语言(s-t tgds、GAV依赖关系或LAV依赖关系)，这个问题都是不可确定的。利用一阶句子的可满足性的不可判定性，可以很容易地证明这一点。¹⁸

回到顶部

6.讨论和开放问题

本研究对模式映射的研究具有方法论意义。具体地说，我们的结构表征描述了在研究特定语言中指定的模式映射时可用的确切工具集。例如，考虑一下LAV依赖的语言。对文献的仔细阅读表明，早期关于由有限的LAV依赖集指定的模式映射的结果系统地利用了这样一个事实:这种模式映射在目标同态下是封闭的，承认全集解，允许连接查询重写，并且在联合下是封闭的。在定理4.1中给出的结构描述，实际上，颠倒了表格，断言这四个属性是只有在推理由LAV依赖项指定的模式映射时需要使用的属性。在计算方面，第5节中的复杂性理论结果精确地量化了确定用一种语言指定的模式映射是否也可以用另一种语言指定的难度。

对于使用比s-t tgds语言更丰富的语言指定的模式映射也进行了广泛的研究。考虑，例如，由s-t tgds和目标tgds指定的模式映射，这是在Fagin等人研究的，⁷或者由二阶tgds (SO tgds)指定的模式映射，这是在组合由s-t tgds指定的模式映射时产生的。⁹这些语言被认为比s-t tgds的语言更具表达能力。我们的结果预测，这些语言至少缺乏这里考虑的一种结构属性。事实上，s-t tgds和目标tgds指定的模式映射在目标同态下是封闭的，并承认通用解，但这是必要的不允许连接查询重写。同样，SO tgds指定的模式映射承认通用解决方案，并允许合并查询重写，但这是必要的不在目标同态下闭合。为如此丰富的依赖语言建立结构表征仍然是一个开放的问题。一个特别有趣的问题是，是否有一种自然的方式来描述弱无环目标tgds集合，⁷在数据交换中具有核心重要性的一类目标依赖项，因为它们保证在多项式级的步骤数内终止跟踪过程。

在这里考虑的模式映射属性中，目标同态下的闭包、承认通用解以及允许合并查询重写可以说是数据交换和数据集成最基本的属性。命题4.4告诉我们存在满足这些属性的模式映射，这些属性不能由任何有限的s-t tgds集合定义。是否存在s-t tgds语言的自然扩展，其特征是这三个属性?为了表示包含分组和数据合并的转换，s-t tgds语言的适当扩展称为嵌套的s - t tgds，由Fuxman等人提出。¹¹在本文之前的版本中，¹⁷我们证明了由嵌套的有限集s-t TGDS指定的模式映射在目标同态下是封闭的，承认全称解，允许合并查询重写(但也可能不是)n模块化对任何n是否所有满足这些属性的模式映射都可以用嵌套的s-t tgds定义，这是一个有待解决的问题。

回到顶部