理论计算机科学电子笔记150（2006）37-54www.elsevier.com/locate/entcs数据映射George H. L. Fletcher，a，1Catharine M.Wyndham，a，b，2Edward L.Robertson，a，b，3和Dirk Van Guchta，4a美国印第安纳大学布卢明顿分校计算机科学系b印第安纳大学信息学院摘要克服自治数据源之间的异质性的技术是新兴网络世界的关键。在本文中，我们讨论了初步结果的正式调查的基础上的技术，以减轻结构的异质性。结构异构性的核心是数据映射问题：发现数据的结构化表示之间的有效映射。自动发现这些映射是数据互操作性、集成和共享方面尚未解决的基本挑战之一。我们介绍了一种新的数据模型和演算表示关系数据源之间的数据映射，奠定了基础，更好地理解数据映射问题。这项研究揭示了数据映射语言中的几个新的安全问题。我们讨论正在进行的调查的语法和语义的限制演算来处理这些问题。关键词：数据演算，数据映射，数据库互操作1介绍新兴的网络世界为信息传播、大规模合作和知识共享提供了新的机会和可能性这些机会将在很大程度上由汇集自主数据源的技术来促进。由于这些数据源的创建1gefletc h @cs。I n diana。埃杜乌2cmw@ c s. 我和我一个一个。埃杜乌3edrbtsn@cs。In di a na。ed u。工作由NSFGRANTIS82407提供。4vguc h t@cs. 我和我一个一个。edu。工作是由NSFGRANS82407完成的。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.11.03338GHL Fletcher等人理论计算机科学电子笔记150（2006）37并且是孤立地发展的，它们各自根据本地限制和使用模式进行不同的维护。因此，促进技术必须弥合各种异质性。这些异质性包括系统层次的差异性、数据结构的差异性和数据解释的语义多元化我们正在研究一种克服关系数据源之间结构异质性的方法[5]。尽管数据库的研究在结构化数据的存储和管理方面取得了巨大的实际成功，但在减轻结构异构性的技术方面取得的进展有限。克服结构异构性的核心是数据映射问题：自动发现结构化数据源之间的映射[5]。这些映射是构建信息共享系统的基本这个普遍存在的问题出现在几乎所有涉及多个结构化数据源的信息系统中。因此，这个问题有许多传统的表现形式：数据库中的模式匹配[17]和模式映射[15]，语义Web上的本体映射[9]，对等系统中的模式中介[7]，以及信息模型的匹配[13]，仅举几例。一般来说，这个问题被认为是为了说明数据映射问题，考虑图1中包含学生成绩信息的三个数据库。在本例中，每个数据库包含相同的学生信息。如图所示，即使是最简单的数据集，也有许多自然的方法来组织。例如，G1和G2在一个表中维护学生信息，而G3包含每个赋值的表。请注意，要在这些学生数据表示之间移动，必须执行模式匹配以及数据-数据和数据-元数据转换。例如，将数据从G1映射到G2涉及将G1中的属性Assignment中的值提升到G2中的属性名称，并还要注意，这个映射动态地创建了与Assignment中的值一样多的新属性。要将信息从G3移动到G1，必须将关系名称降级为数据值。这将是我们在论文中的运行示例。任何克服关系结构异构性的解决方案都必须考虑关系数据源的完整数据映射问题空间。模式匹配（模式之间的“传统”元数据-元数据映射GHL Fletcher等人理论计算机科学电子笔记150（2006）3739等级：学生分配1分配2Saori 94 97Yukie 88 89G2«↑↓↑↓G3任务1：名称Saori 94百分比Yukie 88任务2：名称Saori 97百分比Yukie 89Fig. 1. 学生成绩表示之间的映射。元素[17]）和数据-元数据/元数据-数据映射（其中一个结构中的数据元素用作另一个结构中的元数据组件，反之亦然[10，14]）必须是可表达的。重要的是要注意到，全映射空间的概念模糊了模式匹配和模式映射之间的区别[15]，因为数据-元数据映射将模式匹配作为一种特殊情况。当元数据本身被视为数据时，整个模式匹配和模式映射都包含在数据映射中。我们对数据映射问题的研究是印第安纳大学可查询信息源模块集成（MIQIS）项目的一部分[22]，这是语义Web和对等数据管理系统中数据互操作性的框架[7]。MIQIS的突出特点之一是关注信息系统的模块化本质，包括XML、关系、文本和其他数据源。该框架充分尊重对等体的自主权，以本地管理其模式和概念。 MIQIS的两个主要组成部分是数据互操作性的正式调查和由该调查驱动的模块的实际实现。在本文中，我们提出了初步的结果，正式研究的数据互操作性的关系模块MIQIS。1.1相关工作克服结构异构性是数据库研究中一个长期存在的问题。我们在本文中的工作是由数据库互操作性的关系语言（如FISQL[21]）、数据映射解决方案和G1等级：名称分配百分比Saori分配194Saori Assignment 2Yukie Assignment1 88Yukie Assignment2 8940GHL Fletcher等人理论计算机科学电子笔记150（2006）37数据交换问题的最新研究。1.1.1关系联盟语言一段时间以来，人们已经知道一阶逻辑（即，SQL）不适合表达许多有用的数据互操作性转换[10，14]。这导致了在过去十年中针对联邦数据模型的关系语言的工作。对我们的工作最有启发的是Chen等人。[2]关于高阶逻辑编程，Grant等人。[6]，Krishnamurthy等人。[10]和Lakshmanan等人。[11]关于多数据库语言，Sattler等人。[19]关于数据库联邦语言，以及Jain等人。[8]关于通用数据模型和数据元数据查询语言。我们的工作补充和扩展了这条线的研究与逻辑表征的关系数据映射转换的整个空间。1.1.2联合互操作SQL我们的工作是一个直接的研究成果的关系元数据查询语言联邦互操作SQL（FISQL）的Wessel等人。[21]. 这个SQL的原则性扩展自然地表达了图1中的所有数据库转换。1.一、示例1.2为了说明FISQL，考虑以下查询，将G1中的数据重构为G2的格式：SELECT G.Name ASG.从G1级到G2级的这种查询语言在转换上是完全的，因为它精确地表达了所有自然的关系数据-元数据转换[21]。FISQL也有一个等价的查询代数，FIRA[21]。除了正常的关系运算符之外，该代数还具有用于数据元数据查询，例如：↑以提升元数据，↓以降级元数据，以及→取消引用数据。FISQL将作为我们关系互操作性的基准;一个成功的关系数据映射语言至少应该具有FISQL的表达能力。1.1.3数据映射解决方案本文中开始的正式调查与使用FIRA操作符和受限合并操作符的数据映射解决方案[5]的成功实现同时进行。该解决方案将数据映射视为搜索问题，这是一个新颖的视角，使我们能够利用人工智能的传统技术。本研究为正式的调查数据映射解决方案。GHL Fletcher等人理论计算机科学电子笔记150（2006）37411.1.4数据交换问题与数据映射问题密切相关的一个问题是数据交换问题，最近由Fagin等人[3]提出，以形式化IBM [15]开发的Clio模式映射系统的各个方面。简单地说，数据交换问题如下：给定一个源模式S，目标模式T，源实例I，以及一组源到目标依赖的逻辑形式，找到一个满足S ，T 的目标实例J[3]。Fagin等人已经描述了数据交换问题的解决方案，并探索了数据交换设置中的查询应答[3]。这些限制结果是用于表示一阶逻辑的片段的逻辑形式主义的限制，一阶逻辑并不总是充分地表示自然发生的数据映射。此外，在数据交换中，假设（1）这些依赖性作为输入给出，并且（2）目标模式T是固定的。在数据映射问题中，我们关注的是发现有意义的源到目标约束，给定S，T，也许还有（I，J）作为输入，其中目标模式T可能是动态的[5]，正如我们在从G1到G2的映射中看到的那样，它在G2中创建的新赋值名称与G1中的赋值值一样多。1.2投稿及论文在本文中，我们介绍了一个数据映射演算推理的数据映射问题。这种语言是由Jain等人开发的统一演算的后代。[8]，专门研究关系数据映射;它是Jain语言的新发展，因为它清楚地捕获了标准关系模型的最小扩展，用于数据库互操作性的结构转换。这个简单的逻辑形式表达了数据映射的转换，并补充了我们在自动化数据映射解决方案方面的工作[5]。微积分的一个主要动机是，它有利于调查的复杂性和/或决策方面的数据映射问题。在本文中，我们的贡献如下：• 在2.1节中介绍了一种用于数据映射的新型数据模型。• 数据映射演算在2.2节和2.3节中介绍。• 在结构化数据映射中出现的几个重要的安全问题，如模式安全和功能，在第2.4-2.6节中介绍。在这些章节中，我们还讨论了正在进行的工作，描述了一个适当的安全的微积分片段，它相当于关系数据互操作性的易处理的查询我们在第3节中给出结论性意见和对未来工作的指示。42GHL Fletcher等人理论计算机科学电子笔记150（2006）372数据映射：数据模型和微积分本节将介绍一个新的数据模型和声明性数据映射演算（DMC）来解决数据映射问题。在整个演示文稿中，我们用几个例子说明了DMC的有效性在第2.1节中介绍了DMC的数据模型之后，我们在第2.2节中介绍了DMC语法，在第2.3节中介绍了语义。事实证明，不受限制的DMC太强大了，DMC的自然语义是有问题的。在第2.4-2.6节中，我们说明了出现的问题，并提出了将DMC细化为一个片段的方法，该片段对于数据映射来说具有足够的表达力，但又受到足够的限制，以承认与现有的有效语言等价，数据映射2.1数据模型这种数据模型支持DMC是密切相关的联邦数据模型的Wessel等人。[21]以及Jain等人的统一数据模型[8]的一项建议。与关系数据模型类似，数据库是有限的结构化对象在原子的可数无限集合DOM上（例如，字母数字串）。然而，在DMC数据模型中，元组只是用关系名称显式标记的有序对的有限集合。一个数据库就是这样的元组的有限集合。形式上，该模型定义如下。设P_fin（X）表示给定集合X的所有有限子集的集合。• 元组T是一个有序对r，{，a n，v n}其中r，a1，.，an，v1，.，vn∈DOM和n0.我们将使用符号name（T）表示r，body（T）表示属性值对的集合设T表示DOM上所有可能元组的集合。• 数据库D是一个有序对T∈（DOM× Pfin（T））.作为简写，我们写name（D）和body（D），分别表示D的第一个和第二个元素令D表示DOM上所有数据库的集合。• 数据库D中的关系r是元组的集合{t∈body（D）|name（t）= r}。请注意，每个数据库D都有一个有限的关系集，这些关系集划分了body（D）。GHL Fletcher等人理论计算机科学电子笔记150（2006）3743• AfederationD？ 是一组有限的数据库：D<$={D1， . . ，Dn}∈Pfin（D）其中rename（Di）name（Dj），对于i j。LetADOM（D¯）den tthettof所有的a到m都在D中出现。另外，让TDtuple s overAD OM（D<$）.表示所有可能的示例2.1在这个数据模型中，图1的联邦的表示是数据库集合{G1，G2，G3}。此外，G2（例如）具有以下表示：.G2，.年级，{ΣΣ⟨ Grades，{⟨ Student，Yukie ⟩，⟨ Assignment1，88 ⟩，⟨ Assignment2，89 ⟩}⟩.2.1.1对数据模型的请注意，我们的数据模型是关系数据模型的适当扩展，因为它允许非功能性元组，即，元组在其主体中有多个对，具有相同的第一个元素。这种灵活性对于适应在数据映射期间发生的自然转换是必要的;强制执行严格的功能（即，关系数据模型）是我们在本文中详细讨论的问题，也是正在进行的研究的焦点。这种现象模仿了另一个有趣的特性是数据模型自然地支持丢失信息。常见的是，在数据映射期间，查询可以动态地允许输入数据变成输出元数据。通常引入特殊的DMC数据模型干净简单地避免了与此应用相关的问题，通过将空值视为不存在来接近。例如，如果G2中的单个学生具有属性-值对“extra-credit，83”，则不必在所有学生的元组中显式地为属性extra-credit设置空值。其他学生。数据模型的这些灵活特性使其特别适合用于动态数据映射。我们现在转向DMC的语法的呈现。44GHL Fletcher等人理论计算机科学电子笔记150（2006）372.2微积分2.2.1方面我们假设语言的以下基本构建块：• 一个可数无限的常数集C ={c1，c2，. . }的情况下，• 定义域变量DV ={x1，x2，. . }，以及• 元组变量T V ={t1，t2，. . }。此外，我们假设C，DV和T V是成对不相交的。DMC项T的集合由常数和变量建立如下。• 如果c∈ C，则c∈ T。• 如果x∈ DV，则x∈ T。• 若t∈ T V且c∈ C，则t. c∈ T.• 若t∈ T V，x∈ DV，则t.x∈ T.直观地说，语法t.x表示属性上元组t的值集X.2.2.2公式DMC中的公式由以下项构建。• 若α，β∈ T，则α=β∈DMC.• 如果n，n∈DMC，则· <$∈DMC· 公司简介· 公司简介• 如果t∈ T V，c∈ C，x∈ DV，且x∈DMC，则· （X）X∈DMC· （nx：t∈c）n∈DMC注意：（1）语法x：t强调x是与元组t耦合的关系名称，（2）数据库名称c是一个常量，（3）我们将使用（x. . ）是<$（. . ）<$，和往常一样，→是<$的简写2.2.3查询DMC查询的格式为{x：t|n（x，t）}，其中x∈ DV和t∈ T V是唯一的自由变量在DMC中。GHL Fletcher等人理论计算机科学电子笔记150（2006）3745DD2.2.4示例一些例子将说明这种语法的表达能力。例2.2我们从数据库G1上的一个标准关系查询开始，该查询返回Grades关系中出现的所有学生姓名，并将它们放在名为StudentNames的输出关系中：{x：t|x=StudentNames（r：s ∈ G1）（r= Grades t. Name= s. Name）}。示例2.3接下来，考虑一个查询映射G2到G3。此查询必须将属性名称提升为关系名称，这可以按如下方式完成{x：t|（r：s ∈ G2）（a）（v）（r = Grades a/= Student s.a = v x = a不客气。Name= s. 学弟学妹。百分比=v）}。例2.4最后，一个将G2映射到G1的查询必须将属性名降级为数据值：{x：t|x=Grades（r：s ∈ G2）（a）（v）（r= Grades s.a=v aStudent不客气。Name= s. 学弟学妹。赋值= a t。百分比= v）}。注意，DMC可以清楚地表达图1中数据库之间的所有映射。1.一、其他转换的示例将在后续部分中给出2.3演算语义DMC具有主动域语义，这是避免查询的域安全问题的自然选择[1]。在这种语义下，量化器仅限于AD OM（ D<$），即输入联合D<$的主体。Aformula在一个估值下解释了DMC。 对以下方面进行估值：afederationD？是以下类型之一的函数：νC：C→ADOM（D<$）νDV：DV→ADOM（D<$）VTV：T V →T <$。DD由于C、DV和TV是成对分开的，我们可以使用VD指的是这些功能没有混淆（当上下文清楚时，只有ν2.3.1方面DMC项α相对于估值ν（表示为[α]]ν）的含义给出如下：• 对于c∈ C， [c]]v={v（c）}，即，常数c的单例值。• 对于x∈ DV， [x]]v={v（x）}，即，域变量x的单例值。46GHL Fletcher等人理论计算机科学电子笔记150（2006）37• 对于t∈ T V和c∈ C，[t.c]] ν={y∈DOM|<$v（c），y<$∈body（v（t））}，即，属性名v（c）上的元组t的值的集合• 对于t∈ T V和x∈ DV，[t.x]] ν={y∈DOM| <$v（x），y <$∈body（v（t））}，即，属性名ν（x）上的元组t的值的集合2.3.2公式Givenafor mula∈DMCandavationνD<$，我们可以根据的句法形式归纳地定义满足的标准概念如下。我们写“ν| =“表示满意。ν |= α = βi[α]] ν[[β]] νν|=<$i|=ν |=|=或ν |=ν |=|=和ν|=ν|=（x）ia∈AD OM（D<$）su chthatv [x←a]|=ν|=（x：t∈c）iD∈D<$T∈body（D），name（D）=ν（c）且v [x←name（T），t←T]|=请注意，DMC中的相等语义是基于集合的。这是因为元组不一定是功能性的，如上所述。 虽然看起来奇怪的是，将项的相等定义为非空交集，这直接反映了我们的数据模型可以包含非函数元组的事实。这样做的一个结果是，一个原子x等同于单例集{x}。 这种方法最近在文献中越来越被接受，因为在定义XML数据的数据模型和查询语言时，项目集也会出现同样的现象[4]。2.3.3查询给定一个DMC查询Q和输入联邦D<$，我们可以定义Q的语义，其中Q表示D<$，d表示[Q]]D<$，等等。[[{x：t|{\displaystyle {\frac{x，t}D<$={[[t]]v|v是关于verD的一个值这样，|=（name（[[t]] v），[[t]] v）}。这种语义是关系元组演算语义的自然扩展[1]。这种语义给出了一个唯一的、定义良好的输出数据库作为结果GHL Fletcher等人理论计算机科学电子笔记150（2006）3747任何DMC查询。然而，存在与自然语义相关联的若干不足。这些出现是因为（i）DMC查询的输出是动态的，因此不能被显式地键入，导致输出中的无关元组，（ii）DMC数据模型允许非功能元组，以及（iii）演算太强大而不能用作实用的查询语言。在下一节我们将说明什么可能出错，并提供DMC的连续限制。请注意，这些限制中的一个考虑因素是开发DMC的一个片段，它相当于转换完整的关系数据映射语言，如FISQL[21]。2.4架构安全性一个最重要的考虑是，DMC查询的自然语义迫使不直观的结果，因为DMC输出模式是动态的。这我在TD中没有任何元组在输出中出现，而不仅仅是“适当”的模式Example2.5ConsiderrinputfederationD<$：={a，{a，{b，b}}，查询Q：={x：t |x = a <$（r = a <$t. b= s。b）}。 在这种情况下我们有：[[Q]]D<$={a，{b，b}，a，{a，{a，{a，{a，{Qu eryQ onD<$o规定，输出数据库不属于包含一个属性值pair_b、b_c的重复的关系。 TD<$中每个名为a且包含b，b的元组都将包含在结果中，这显然是自然语义在动态输出模式面前的意外结果。在这个意义上，DMC查询的自然语义是模式不安全的，即，查询结果潜在地包含不直观的、意外的元组。因此，我们对DMC的第一个限制是提供模式安全性。我们可以从句法（2.4.1节）或语义（2.4.2节）两个方面来做这件事。2.4.1语法模式安全从语法上讲，将DMC查询限制为模式安全查询是一件简单的事情。所需要做的就是在每个查询中包含一个参数化公式σ∈DMC，该公式明确声明不存在无关的属性-值对48GHL Fletcher等人理论计算机科学电子笔记150（2006）37在输出中我们在第2.2.4节中的前两个查询上说明了这个过程。例2.6首先，我们将例2.2中的简单查询重写如下.{x：t|x=StudentNames（r：s ∈ G1）（r= Grades t. Name=s. 名称<$σ（t））}，其中σ（t）：=（u）u/=Name→<$（v）t.u=v。例2.7类似地，对于例2.3中的查询映射G2到G3，σ（t）：=（u）（u/=NameuPercentage）→ <$（v）t.u=v.对于具有动态输出的查询，例如示例2.8或2.12（下面）中的查询，构造模式安全条件σ稍微有点棘手，但该方法仍然有效（通过量化由于篇幅所限，细节省略。2.4.2语义模式安全模式安全性也可以通过采用更严格的查询语义来加强。直观地，我们将查询结果限制为自然定义的最小答案。其思想是在查询结果中只包含这种语义类似于关系演算的标准模型论语义。我们将在未来的工作中建立这种最小答案语义不允许虚假的属性值对，并且定义良好。2.5功能一个类似的奇怪之处是，我们的数据模型和自然查询语义允许非函数元组。应该强调的是，这不是一个问题，而是模型和语义的一个特征。然而，它阻止了DMC与关系查询语言（如FISQL）的等价性，FISQL假设元组是函数[21]。例2.8假设将考试成绩添加到G2：学生分配1分配2示例1Saori949797Yukie888988请注意，Saori在作业2和考试1中都得到了97分，Yukie在作业1和考试1中都得到了88我们可以提升成绩数据GHL Fletcher等人理论计算机科学电子笔记150（2006）3749使用以下查询将属性名称转换为：{x：t|x=Grades <$（r：s ∈ G2）（a）（v）（r= Grades不客气。学生= s. Student<$a/= Student<$v=s.a<$t.v=a<$σ（t，v））}，其中σ（t，v）：=（p）（p/=Studentp v）→ <$（w）t.p=w。 在这种情况下我们的输出数据库包括以下元组（除其他外）：{100级， {100级学生，Saori， 1994， Assignment 1}级，成绩，{成绩，{成绩，{成绩，{ . }注意，输出在2.4节的意义上是模式安全的，但包括非功能元组（例如，最后两个元组）以及预期元组，因为这些元组满足查询条件。这表明，除了模式安全性限制之外，还需要对DMC查询进行需要与关系语言等价。 还要注意，将包含第四个元组是Student属性上前三个元组的我们将在下面的2.6节中讨论这个问题。与模式安全性一样，功能可以严格地在语法上（第2.5.1节）或语义上（第2.5.2节）执行。然而，所实现的功能不允许在FISQL中可能的许多自然查询。我们将在2.5.3节中讨论第三种实现功能的方法。2.5.1句法功能功能性可以通过向DMC查询添加公式θ来在语法上强制执行，该公式坚持输出是功能性的。我们通过重新访问例2.8中的查询来说明该方法。例2.9我们可以将例2.8中的查询重写如下。{x：t|x=Grades（r：s ∈ G2）（a）（v）（r= Gradest. 学生= s. 学生a学生a学生a=v<$t.v=a<$σ（t，v））<$θ（t）}，其中θ（t）：=<$（（ta）（vv）（u）（t. a=vv vv. a=uuu/=v））。这将强制执行以下输出（合理地符合我们的期望）：{100级， {100级学生，Saori， 1994， Assignment 1}级，成绩，{成绩，{成绩，{成绩，{ . }但是，请注意，合并和未合并的元组都保留了下来。50GHL Fletcher等人理论计算机科学电子笔记150（2006）372.5.2语义功能功能性也可以通过将元组变量分层为允许为非功能性的变量和只能在功能性范围内变化的变量元组，表示为t. 在这种新的分层下，查询具有以下形式{x：t}|（x，t请注意，如果在SQL中允许任意元组变量（而不仅仅是函数变量），语言的力量更我们把这个替代方案的细节推迟到一篇更长的论文中。2.5.3操作功能当在单个DMC查询中发生多个数据到元数据的提升时，功能的语法和语义方法遇到困难。这些促销活动可能相互冲突，导致多个在输出数据库中反映的”执行的可能性“。在这种情况下，严格的功能方法将强制查询答案为空。然而，FISQL查询语言在这种情况下确实返回函数元组，因为它具有用于生成遵循查询语法的查询结果的自然操作语义。例2.10考虑数据库G1'中的以下Grades姓名分配A等级考试E等级Sanae 1 100 1 98现在假设使用以下查询将Assignment和Exam值提升为{x：t |x = Grades <$（<$r：s ∈ G1 '）（<$y1）（<$y2）（r =Grades不客气。Name= s. 名称：1= s。赋值为2= s。考试y1= s。A等级t.y2= s。E级<$σ（t））<$θ（t）}此查询的结果将是空集，这是一个不希望的结果。如果我们重新移动θ（t）子句，结果将反映属性的两个可能值1：¯等级，{显然，属性1具有两个不同的值也是不期望的结果。对于这样的查询，我们可以显式地指定一个用参数化的句法子句ω（t）。 为了与FISQL等效，重要的是，ω（t）的一般形式与语言的操作顺序兼容。例2.11在前面的例子中，ω（t）：=（y1= y2）→（t，y1= s. A级）GHL Fletcher等人理论计算机科学电子笔记150（2006）3751并且实现确定性的功能输出：˘ ¯等级，{通过这种修改，我们防止了自然DMC语义中的这种功能的操作方法自然地捕获了FISQL的行为。2.6复杂度降低如例2.8所示，查询的语义可以包括“合并”和“未合并”输出。这是一个将数据提升为属性名称的工件。通常，需要合并的输出。例如，OLAP操作PIVOT期望透视列形成一个键，以便可以输出一个定义良好的合并关系。一般来说，在动态类型化输出中合并元组的问题是NP完全的[20]。例2.12考虑一个查询映射G1到G2：{x：t|x=Grades <$（<$r：s ∈ G1）（<$y）（r= Grades不客气。学生= s. 名称：y = s。赋值y = s。百分比）}此查询的输出如下所示：˘成绩，{成绩，{年级，{年级，{Grades，{成绩，我们期望一个Student值与它所有的Assignment值相关联，“合并”成一个元组，就像查询结果的最后两个在图1中的输入联合的情况下，下面的查询完成了这一点：{x：t |x = Grades（r：s ∈ G1）（r = Grades t. 学生= s. 名称n（nr′：s′∈ G 1）（na）（r′= r r t. 学生= s′。姓名）→（a = s′. 赋值：a = s′。百分比）}需要注意的是，对于这个特定的输入联合，只有一个合并，但通常情况下不是这样。这种查询的DMC语义将反映满足查询条件的所有合并52GHL Fletcher等人理论计算机科学电子笔记150（2006）37事实上，允许像例2.12中的第二个这样的查询使我们能够在DMC中表达广义连接[18]，这是一种已知为PSPACE-complete [18]的操作。相比之下，我们的关系数据映射FISQL的范例语言是在日志空间中。因此，为了实现与FISQL的等效性，我们需要进一步限制DMC以排除此类查询。这可以通过将查询主体中的自由变量的范围限制为无负接地公式γ来在语法上完成。这种形式的一般queries是：{x：t|（r1：s1∈ c1）···（rn：sn∈ cn）（y1）···（yk）γ（x，t，r1，...， rn，s1，. sn，y1，. yk）n（r1，. rn，s1，.sn，y1，. yk）}，其中，γ是无负的，x和t在γ中都不是自由的。DMC查询的这种语法形式直接反映了FISQL查询的范围（SQL中也有类似的作用域。我们将DMC的查询子语言（具有适当的σ（模式安全性）、γ（接地 ） 和 ω （ 排 序 ） 子 句 ） 称 为 联 邦 互 操 作 关 系 演 算 （ FederatedInteroperable Relational Calculus）或FIRC。未来工作的一个目标是表明，在自然映射下，DMC的这个片段给我们的正是FISQL的表达能力。3结论和今后的工作在本文中，我们介绍了正在进行的工作，正式的基础调查到数据映射问题。在讨论了相关工作的基础上，我们提出了一种数据映射演算DMC，并说明了它对表示关系数据映射变换的适用性。然后，我们提出了一个自然的语义DMC查询，并介绍了几个棘手的安全问题与这种语义学有关最后，我们讨论了句法以及语义安全限制，着眼于开发与已知的实际元数据查询语言等效的语言片段。目前，我们正拟订这些问题的全部细节，以及为解决这些问题而对公契作出的限制。此外，DMC在手，我们现在能够清楚地形式化的DMC决策问题的数据映射问题。在这项研究中，我们的下一个主要步骤是正式陈述这些问题，并确定它们的复杂性和/或可判定性。GHL Fletcher等人理论计算机科学电子笔记150（2006）3753引用[1] Abiteboul，Serge，Richard Hull，and Victor Vianu. 数据库基础，Addison-Wesley，Reading，MA，1995年。[2] Chen，Weidong，Michael Kifer，and David Scott Warren.高阶逻辑程序设计的基础. J.逻辑程序15（3）：187-230，1993.[3] 费金河，P.G. Kolaitis和L.爸爸数据交换：到达核心。 Proc. ACM PODS，pp. 90-101，SanDiego，CA，2003.[4] Fern'and ez，M. F. ，etal. XQery1. 0和XPath2。0DataM odel. W3C，Fe b. 2005年[5] 乔治·弗莱彻和凯瑟琳M.Wyndham. Web上数据源之间的映射Proc. IEEE ICDE Workshop WIRI，Tokyo，Japan，2005.[6] 格兰特，J.，W. Litwin，N. Alkissopoulos，和T.塞利斯关系型多数据库查询语言。VLDBJournal2（2）：153-171，1993.[7] Halevy，A.是的，Z. G. Ives，D.苏丘和我。塔塔里诺夫对等数据管理系统中的模式中介。Proc.IEEE ICDE，pp. 505-516，班加罗尔，印度，2003年。[8] 贾恩，M.，A. Mendhekar和D.范·古赫特关系数据和元数据查询处理的统一数据模型。Proc.COMAD，Pune，India，1995.[9] Kalfoglou ， Yannis 和 Marco Schorlemmer 。 Ontology Mapping ： the State of the Art.TheKnowledge Engineering Review 18（1）：1-31，2003.[10] Krishnamurthy，R.，W. Litwin和W.肯特具有模式离散性的数据库互操作的语言特征。Proc.ACM SIGMOD，pp. 40-49，Denver，CO，USA，1991。[11] Lakshmanan，L.V.S.，F. Sadri和I.N.萨勃拉曼尼亚多数据库系统互操作的逻辑和代数语言 J.逻辑程序33（2）：101-149，1997.[12] Lenzerini，Maurizio.数据集成：理论视角。Proc. ACM PODS，pp. 233-246，Madison，WI，USA，2002。[13] 梅尔尼克，谢尔盖。通用模型管理：概念和算法，LNCS 2967。施普林格出版社，柏林，2004年。[14] 米勒，ReneeJ。 使用单字节存储器和其他存储器。 P roc。 ACMSI GM OD确认数据管理，pp。189-200，Seattle，WA，USA，1998。[15] 米勒，ReneeeJ。，LauraM.你好，我是马里人。 Hern'和Ez。这是一个发现。VLDB会议程序，pp. 77-88，开罗，埃及，2000年。[16] 你好，G。，Z.M. Ouzsoyyobuglu，and V. 妈的具有集值属性和聚合函数的广义代数和广义ACMTransactions on Database Systems，12（4）：566-592，1987。[17] Rahm，Erhard and Philip A.伯恩斯坦自动模式匹配方法综述。VLDB Journal10（4）：334-350，2001.[18] Rood，C.M.，D. Van Gucht和F. I. Wyndham. MD-SQL：一种在关系数据库上实现元数据查询的语言。印第安纳大学计算机科学系TR528，1999年7月。[19] Sattler，Kai-Uwe，Stefan Conrad，and Gunter Saake.交互式示例驱动的集成和协调，用于数据库联盟。信息系统28（5）：393-414，2003年7月。[20] 凯瑟琳·韦斯利爱德华·罗伯逊最佳元组合并是NP完全的。印第安纳大学计算机科学系TR599，2004年7月。[21] 凯瑟琳·韦斯利爱德华·罗伯逊元数据集成的关系语言。ACM Transactions on Database Systems，2005年6月出版。54GHL Fletcher等人理论计算机科学电子笔记150（2006）37[22] Wessels，Catharine M. George H. L. Fletcher，Fulya Erdinc，and Jeremy T. 恩格尔 MIQIS：可查询信息系统的模块化集成。 Proc. VLDB 讲习班 IIWeb，pp. 136-140，多伦多，加拿大，2004年。
我的内容管理
展开
