模式匹配的映射表示

模式匹配的映射表示

目前，数据集成和模型管理已成为数据库学术界的研究热点。数据集成和模型管理的核心是不同结构模式的适应。模式匹配是异构模式之间数据集成和管理的最基本的问题,两个模式匹配的结果可以用模式映射来表示。现在,很多大学和公司都在从事与模式匹配和模型管理的研究,然而目前大部分研究还只是集中在如何发现和找到模式的元素匹配对,而没有给出映射本身的形式化定义和表达。大部分的研究使用简单的关系模型来存储元素的匹配对,这样的映射表达缺乏足够的语义表现力和处理能力。在文献中,模式的映射被定义为一种模型,这种模型由映射元素以及元素的简单对应关系构成,文献中赋予映射模型两个“射”,用来表示映射元素与要匹配模式的元素之间的关系。然而,这种模型无法表达元素之间的复杂的逻辑关系,无法表达两个元素的数据对应关系等。文献中同样缺乏对映射的有效表达。文献第一次系统地讨论映射的定义和表达式,作者借用一个帮助模型(HelperModel),基于不同元素之间的公式而形式化地定义了映射的框架,并详细地讨论了映射的语义和性质。利用查询回答能力(QueryAnswerability)、映射推理(MappingInference)、映射合成(MappingComposition)等表征映射的能力和强弱,映射应该具有的性质也在文中得到了详细的讨论。然而,作者并没有讨论表达式和公式可能的形式,而且,帮助模型的选择和形式也没有给出说明。在复杂的匹配情况下,如何建立有效的表达式是非常关键的,在文献中,基于普通的关系代数,作者给出了几个扩展的操作符。但是,这些操作符有的实际上无法具体定义,还有一些匹配的情况也没有考虑。基于以上分析,这里首先在第一节中分析了匹配的几个复杂但是必须考虑的结果,讨论了模式匹配中可能的复杂匹配关系。在第二节中给出了一个映射框架的定义,该框架充分考虑了模式匹配的复杂情况和异构模式间的差异,基本可以适应目前的映射表达要求。利用定义好的框架,第三节讨论了在数据集成上如何应用映射框架。在第四节中进行了总结并说明了将来可能的研究方向和问题。1映射关联关系大部分模式匹配的算法使用关系,即简单的元素响应对来表示不同模式之间的映射(Mapping)关系,这样的表达方法使得很多复杂的匹配关系无法得到有效的表达,对数据集成、模式合并、映射的重用以及合成等带来很大的不便。下面是一些无法使用简单的元素响应对来表示的模式匹配关系:1.1条件匹配所谓条件匹配,即不同模式之间的元素是在一定的条件下匹配的。1.2一些匹配部分匹配是指源模式中的元素的部分和目标模式中的元素匹配。1.3有多个元素的匹配情况在很多情况下,由于不同的设计者可能对元素有不同理解以及应用场合不同,造成了一个模式中定义了一些元素,而目标模式的一个元素的值是这些元素的枚举选择。例如图1中学生的英语4、6级通过情况,模式1采用了两个元素来表示,而模式2则用一个元素来列举不同的等级。这样的匹配是非常难用简单的元素响应对来表示的。图1表示一个元素对值的匹配情况,模式S1的grade4和grade6是两个布尔型元素,表示学生的大学英语4、6级是否通过。模式S2则使用了字符串型元素grade来表示英语的通过级别。这样对应元素在类型和值之间的差异导致了在映射时需要根据它们的值进行转化,即将S1元素的布尔型的值转化为模式2的元素grade的值,表示英语的等级。例如,设S1的grade6为“TRUE”,则对应的S2的元素grade的值为“grade6”。1.4映射模型的建立不同的模式可能采用不同的计量单位,或者总体和部分的需求不同,在不同的模式中可能采用不同的度量单位,所以元素的匹配经常需要经过计算才能进行。例如,单价和数量可能是源模式的两个元素,而目标模式中可能只有一个总价,这样,需要计算单价和数量的积,才能和目标模式的总价匹配,这种匹配也是难以用简单的元素响应对来表达的。非匹配元素的保持也是一个非常重要的性质。在很多情况下,希望可以重用以前的匹配结果,因为重用可以提高匹配的精度。然而,如果某一个元素在目标模式中找不到对应的元素,在简单的元素响应对的表示方法下,没有匹配的元素将被去掉。这样,在重用匹配结果时,没有匹配的元素的信息无法重用。所以有必要保留非匹配的元素,如果两个匹配正好可以弥补各自的非匹配的情况,则两个元素可以再次利用。图2描述了一个比较复杂的映射。图2包含两个模式,即客户和商店的模式,其中S1是关系模型,S2采用了半结构化的XML模式。这个映射包含8个映射元素,me1～me8分别对应了模式S1和S2的不同元素。例如,在S1中,两个实体,Customer和Shop共享了Address实体,所以在Address实体中既有Customer的地址又有Shop的地址。而S2的Customer和Shop分别拥有不同的子元素Address,这样S1的Address元素包在映射元素me3和me4,映射到S2的Address时,需要根据Customer和Shop的AddID来映射到不同的S2的Address元素。从图1、2的示例可以知道,用关系来表示简单的元素的匹配对很难有效地表达现实的映射。所以,需要定义一种具有丰富语义、表达能力和推理能力的映射模型。一种良好定义的映射表示应该具有清晰的语义和适合不同的模型语言。2其他运算符和映射模型定义映射为一个模型(Model)。这个模型是第一类模型,它由元素、关系以及定义在元素上的公式组成。为了形式化地定义映射的语义,本文部分借用了描述逻辑的有关内容,描述逻辑是一阶逻辑的一个可判定子集。用L来表示一种语言,语言中的模型记为M。模型M的一个解释记为I,用M表示模型M的外延。表达式e是模型中的元素的操作有限集合。表达式e可以有输出结果。例如,一个SQL语句输出一个关系。描述逻辑的一个概念表示一个一元关系。为了语义的无二义性,我们要求:对于语言L中的模型M,模型中表达式e的输出和解释I:I|=e(a)|,其中a是一个数据实例,是否成立应该被无歧义地定义。定义1一个公式f具有如下形式:e1ope2。其中e1,e2是不同模式中的表达式,操作符op是根据e1和e2的输出结果定义。对于模型M1,M2给定解释I1,I2,{I1,I2}|=e1ope2是无二义的。不同的模型有不同元素类型和运算符,基于关系模型运算符,在文献中,给出了扩展的关系代数,但是这些运算符一是无法全部表示本文描述的匹配结果,二是有的运算符可以通过其他运算符来表示,所以,本文定义如下运算符:(1)通用运算符。根据e1,e2的输出结果定义,例如,+,*,选择(σ)等。(2)合成运算符(λ)。λ运算符具有形式λ(A1,A2,…,An),其中A1,A2,…,An是模型中的元素,λ运算符的结果是元素A1,A2,…,An的值合成为一个新的元素的值,以A1,A2,…,An的次序进行合成。(3)布尔运算符(β)。β运算符具有形式β(A),其中A是一个布尔型的属性,β运算符判断A的值,如果为真(Y),则结果为属性A的名字,如果为假(N),则结果为空。(4)应用函数运算符(φ)。φ具有形式φ(f(A1,A2,…,An)),其中f(A1,A2,…,An)是定义在元素A1,A2,…,An的用户自定义函数。φ运算符的结果为函数f的结果。常用的函数有分解函数、解布尔函数、类型转换函数等。实际上,因为文献提出的分解运算和解布尔运算必须要用户自定义运算过程,无法通过预定义的运算功能完成,所以,本文将它们归纳在φ运算符中。定义2两个模式M1,M2的映射M是一个模型,具有如下形式:M=(E,R,F)其中,E是模型的元素集合,是一个语言中的有限集合,R是元素的关系的集合,F是定义在(M1,M),(M,M),(M,M2)上的公式集合。每个映射模型M的元素e至少有一个定义在(M1,M)或(M,M2)上的公式,表明元素的来源或者去向。根据M的定义,在公式的连接下,从一个模式的元素到另外一个模式的元素,总可以找到一个路径,这样,可以有效地定义和实现数据集成和各种模型管理的代数。3映射模型生成以图1的模式为例,为了简单起见,假设S1和S2均是关系模型,但是对于其他的模型而言,集成过程可以相应地处理。设模式S1是源模式,模式S2是目标模式。根据映射定义,生成映射元素及公式,如表1所示。表1中省略了映射M的元素之间的关系,这种关系可以简单地定义为包含关系。生成了映射模型后,就可以简单地实现数据集成的任务,集成过程为:(1)根据β(S1.Grade4)=me1,β(S1.Grade2)=me1,me1=S2.grade,对于源模式S1的一个元组,如果元组的grade4的属性是真,那么S2.grade的值为grade4,同时如果grade6的属性是真,则S2.grade的值修改为grade6,这样,完成了一个元素的转化。(2)对于源模式S1的同一个元组,根据S1.name=me2,me2=S2.name,如果源模式的name属性是XXX,那么S2.name的值也为XXX,这样,完成了第二个元素的转化。由于篇幅的关系,本文没有使用更为复杂的示例来说明映射模型。但是,根据模型的公式和元素,同样可以完成相应的集成任务。4向数据集成的映射模型模式匹配在数据库研究领域是一个非常重要的方向,它在数据集成、模型管理、Web服务集成和数据仓库等方面,都起着非常基础而重要的作用。目前,许多研究只是集中在如何发现匹配而不是映射本身的表达。本文给出了一种映射框架的定义,并用数据集成说明了如何应用这个模型。示例说明了本文提出的映射模型具有较好的适应性和表达能力。衡量一个映射,需要从不同的性质来说明,例如数据集成能力(DataIntegrationability)、查询回答能力(QueryAnswe