GML模式匹配算法.doc

《GML模式匹配算法.doc》由会员分享，可在线阅读，更多相关《GML模式匹配算法.doc（6页珍藏版）》请在三一办公上搜索。

1、第 29 卷 第 2 期2004 年 2 月武 汉 大 学 学 报 信 息 科 学 版Geomatics and Information Science of Wuhan UniversityVol . 29 No . 2Feb. 2004文章编号 :167128860 (2004) 0220169206文献标识码 :AGML 模式匹配算法关佶红1为1扬1虞安(1 武汉大学空间信息与数字工程研究中心 ,武汉市珞喻路 129 号 ,430079)摘 要 :提出了一个面向空间信息集成的 GML 模式匹配算法 ,其核心思想是将 GML 模式转化成树状结构 ,通过测度两个树状结构的相似度来判断两个对应

2、模式的匹配程度 。在 GML 规范基础上 ,给出了 GML 模式的匹 配算法和匹配器结构 ,并实现了相关算法 ,进而完成 GML 文档的集成 。关键词 : GML ;模式匹配 ;空间信息集成中图法分类号 : P208 ; TP311. 12GML ( geography markup language) 1 作 为 一 种可扩展的 、标准化的地理信息编码方式 ,用于表示 地理对象的空间和非空间数据 ,为空间信息的集 成提供了一个公共的地理对象描述标准 ,从而使 得各个独立开发的应用之间的互操作成为可能 。 GML 规范允许用户在 GML 规范的基本 GML 模式 基础上 ,定义自己的应用 GM

3、L 模式 。由于空间信 息数据繁多 ,结构复杂 ,在基于 GML 的空间信息 集成中 ,用户可以在标准模式上进行扩展 ,各种自 定义模式间可能存 在 较 大 的 差 异 , 因 此 , GML 的 模式匹配也就成了基于 GML 标准进行空间信息 集成必须解决的难题 。1 . 1GML 模式树定义 1 一个 GML 模式可以定义为 树 状 结 构 ,记为 GMLTree 。模式中每个元 素 及 该 元 素 中 所包含的其他元素被看成 GMLTree 中的节点 。包 含其他元素的节点是被包含元素的父节点 ,被包含 元 素 是 包 含 这 个 元 素 的 元 素 的 子 节 点 。GMLTree 表

4、 示 为 数 据 对 象 和 数 据 关 系 的 二 元 组GMLTree = ( D , R) ,其中 ,数据对象 D 是具有相 同特性的数据元素的集合 ; 数据关系 R 定义为 : 若 D 为空集 , 则称为空树 ; 若 D 仅含一个数据元素 , 则 R 为空集 , 否则 R = H , 其中 H 是如下二 元关系 。1) 在 D 中 存 在 惟 一 的 称 为 根 的 数 据 元 素root , 它在关系 H 下无前驱 ;2) 若 D - root ,则存在 D - root 的一个GML 模式匹配相关工作1模式匹配2 操作是输入两个模式 ,找出其相关元素间的匹配关系 ,然后输出两个模式

5、元素间 的映射关系 。模式匹配广泛用于面向网络的数据 集成 、电子商务 、数据仓库 、数据库设计以及网站 的建设和管理等方面 ,但其在基于网络的地理信 息集成等领域的研究与应用还较少 。进行空间信 息集成需要把不同用户定义的关于相同的地理实 体和特征的异构模式转换成一致的 、能够同时为 各个不同用户和计算机共同识别的规范模式 ,这 需要用到模式匹配算法对两个输入模式间的相关 联的元素进行识别和匹配 。划分 D1 , D2 , Dm ( m 0) ,对任意 j k (1 j , km) 有 Dj Dk = ,且对任意 i (1 i m) , 存在惟一数据元素 xi Di ,有root , xi

6、H ;3) 对应于 D - root 的划分 , H - root , x1 , root , xm 有惟一的一个划分 ( H1 , H2 , Hm( m 0) ) , 对任意 j k (1 j , k m ) 有 Hj Hk =, 且对任意 i (1 i m ) , Hi 是 Di 上的二元关系 ,( Di , Hi ) 是一棵符合本定义的树 , 称为根 root 的 子树 。在一个 GML 模式中 ,通常包括“包含”和“被包含”两种关系 。如图 1 所示 “, Map ”元素类型是收稿日期 :2003210210 。项目来源 :国家 863 计划资助项目 (2002AA135340) ;湖

7、北省自然科学基金资助项目 (2001ABB041) ;测绘遥感信息工程国家重点实验室 开放研究基金资助项目 ( WKL (01) 0303) 。“map Type”,为一个复杂类型 ,其子元素中包含有“Layer”元素 ,称为“Map ”元素包含“Layer”元素 ,反 之 ,称“Layer”元素被包含于“Map ”元素中 。匹配结果可将一个模式中的一个或多个元素和另一个模式中的一个或多个元素相联系 ,即匹 配基 数 可 有 1 1 、1 n 、n 1 和 n m 四 种 情 况 。 另 外 ,每一个匹配映射中的元素可和两个模式中的一个或多个元素间存在内在联系 ,在基于实例 的匹配中可能存在着

8、不同匹配基数 。构建匹配器 时 ,往往不只用到输入的两个模式 ,同时还用到辅 助信息 ,如数据字典 、知识库和两个输入模式间的 匹配或不匹配的信息等 ,重用以前的匹配信息也可以有所帮助 。 关于模式匹配的研究可参见文献 2 7 , 其中给出了一些实验性的匹配器 ,如 Cupid 、SemInt 、 TranScm、Skat 、Dike 和 LSD 等 。这 些 研 究 主 要 是 在数据库 、电子商务 、数据仓库 、基于网络的数据集成等领域 ,面向空间信息集成的 GML 模式匹配 方面还少有报道 。2 GML 模式匹配算法2 . 1 GML 模式匹配过程模式匹配过程如图 2 所示 。首先 ,构

9、建相应 的匹配器 (或匹配算法) ,然后输入需要进行匹配 的两个 GML 模式 ,同时抽取两个模式中的相关信 息放入数据库中 ,通过匹配算法将两个输入模式 进行匹配 。在进行匹配时 ,需要数据库中的相关信息来确定元素间的匹配度 ,最后输出一个描述 两个输入模式中的相关元素间关系的映射表 ,同 时生成一个集成的 GML 模式 。图 1 GML 模式样例Fig. 1 GML Schema Sample1. 2 模式匹配相关工作及技术模式匹配用匹配算法构造相应的匹配器 ,找 出模式元素间的映射关系 。匹配器3 可以是单个 匹配器 ,即基于一个单独的匹配规则计算出最终的匹配映射关系 ;也可以是单个匹配

10、器的混合 ,即 在一个杂交的匹配器中运用多种匹配规则进行匹 配 ,或是应用复合的匹配器对不同匹配器计算出 的多种匹配结果进行合并 。单匹配器可以是基于 模式或基于实例的 。基于模式的匹配器仅考虑模式信息本身 ,如名称 、描述 、关系 、限制条件等 ; 基 于实例的匹配器用到从实例数据中获取的元数据 和统计数据对模式进行注解 ,或使用机器学习等 方法直接寻找模式的相关元素 。单匹配器也可按 照元素粒度或结构粒度进行划分 。匹配器可用基于语言的方法 ,如给出元素名称和上下文描述 ;或 基于约束条件的方法 ,如关系和关键字等 。图 2 GML 模式匹配过程Fig. 2 GML Schema Matc

11、hing Procedure数据库中的信息可以包括存放普通知识的一般性数据库 、包含特殊领域信息的数据字典 ,以及包含 各种知识概念的知识库和辅助信息等 ,用于计算和 查询两模式各元素间的语义相似度 ,以确定匹配元 素 。辅助信息包括各种约束信息 ,如关键字 、取值范围等 ,还可以是各种自然语言的描述信息 ,用以确定 两个输入模式间各相关元素的匹配程度 (相似度) 。 有一些匹配辅助信息可以直接从输入模式中得到 。在本文的 GML 模式匹配过程中 ,数据库包含第 2 期关佶红等 : GML 模式匹配算法171的特殊领域信息主要来自于 GML2. 0 中定义的模式和命名空间8 。知识库中包含有关

12、地理实体的 各种空间信息定义以及非空间属性的概念 ,辅助信息可以对数据字典和知识库中所包含的知识进行补充 ,也可用来对匹配结果加以限制 。通过数据库 和匹配算法 ,可自动将两个结构和语义上存在的异 构模式进行匹配 ,得到一个描述两模式间相关元素 的映射关系 ,并构建一个集成的 GML 模式 。2. 2 相似度在进行模式匹配时 ,通过比较两个输入模式 相关元素的相似性 ,找出其中相互匹配的元素 ,推 导出这些元素间的映射关系 。为了衡量相关元素 的相似性 ,用一个相似度系数即相似度描述两个 输入模式间各相关元素的匹配程度 。相似度系数行加权求和来取得两模式中相关元素间最终的相似度值 vsim ,

13、权值用 W 表示 。则有 := W L + (1 - W) Tvsim( 2)匹配者可以根据自己的需要决定在进行匹配时更注重哪一方面的相似性 。权值 W 是匹配者 根据自己需要定义的 ,具有很大的灵活性 。2 . 3匹配算法2 . 3 . 1GML 模式转换树算法如前面所述 , GML 模式 中 有“包 含”和“被 包 含”关系 ,而一般地这两种关系容易对结构相似度的计算造成歧义 。因为在计算元素的结构相似度 时 ,不仅要考虑元素本身 ,还需要根据元素的上下文 ,即元素所处的层次结构进行计算 ,而包含和被包含关系所隐含的层次关系不易直接被识别 ,由 此可能产生歧义 。故需要把包括这两种关系的结

14、构转化为一个清晰无歧义的结构 ,即一个树状结 构 。笔者用一个 GML 模式转换树算法实现这种转化 ,算法程序如下 。tree = buildtree ( schema . root ,null)buildtree ( schema . element e ,treenode t) 创立 GML 树用小数来表示 ,取值范围是 0 ,1 ,0表示两个元素完全不匹配 , 1 表示完全匹配 。相似度需要通过语义和结构两种匹配来确定 。定义 2 语义相似度是语义匹配所得到的相似系 数 ,描述两个模式中语义匹配程度 ,取值范围是0 ,1, 用 L 表示。语义匹配是从元素的名称、数据类型和命名空 间方面来

15、进行匹配的 ,包括对这些元素属性的分类和将 两个模式中的相关元素进行比较。语义匹 配 主 要 包 括 同 义 词 、近 义 词 匹 配 , 缩 写 、简写匹配 ,数据类型匹配和命名空间匹配 4 个 方面 。同义词 、近义词匹配比较两个元素名称上的同义和近义关系 ,相似度用 x syn表示 ; 缩写和简 写匹配也是从元素名称角度进行匹配 ,相似度用y bre表示 ;数据类型匹配是对两个元素的数据类型进行比较 ,相似度用 ztyp 表示 ; 命名空间匹配是从 元素所取自的命名空间上对元素进行匹配 ,相似 度用 f nsp 表示 。计算出语义 4 个方面的相似度后 , 用求几何平均数法将它们合成为一

16、个确定值 ,即 元素的语义相似度 L :int s 1. . n , p = 1 ; 建立栈 ,设置栈顶t = schema . root ; 传入 schema 的根节点s p = t ; 根节点进栈while ( e null or p 0) 传入的 schema 节点不 为空或栈不为空if e = null then p = p - 1 ; t = s p ;e = schema element corresponding to t ; 若传入节点为空 ,则退栈else对于元素 e 中的每个有包含或被包含关系的 子元素 (空元素可作为子元素) ;e = 对于元素 e 中的有包含 或 被

17、包 含 关 系 的 这个子元素 ;if ( e null) then 否则 ,生成树节点t = s p ; 弹出栈顶元素new- t = new schema tree node corresponding to e ; 生成新的树节点set new- t as a child of t 把新生成的 树节点作为弹出的节点的子节点t = new- t ;p = p + 1 ;s p = t ; 新生成的节点进栈4L =x syn y bre ztyp f nsp(1)定义 3结构相似度是结构匹配所获取的相似度系数 ,基于模式中元素的上下文以及它的父 子节点对两个模式元素进行匹配 ,确定结构相似度

18、 。结构相似度取值范围为 0 ,1 ,用 T 表示 。结构匹配是一个动态的过程 ,在进行匹配的过 程中 ,一个模式中的某一元素的父子节点和另一个 模式中的某特定元素的父子节点的结构相似度可能会发生变化 ,则这两个元素的结构相似度也会发生相应的变化 。在匹配中 ,单独用到了一个结构匹 配算法来计算相关元素间的结构相似度 。确定了语义相似度和结构相似度后 ,对其进return t 返回新生成的树的根节点 算法结束2 . 3 . 2GML 模式匹配算法GML 模式匹配算法是把两个已转换成树状结构的 GML 模式进行匹配 ,主要考虑从结构上进行匹 配 ,并遵循以下原则 :对于两棵树中的叶节点 ,如果

19、数据类型或语义上高度相似 ,则认为它们在结构上相似 ;如果叶节点的兄弟节点或父节点相似 ,也可认 为叶节点相似 ;两个非叶节点如果在语义上相似或 其子树相似 ,则认为这两个非叶节点相似 ;如果两个 非叶节点的叶节点高度相似而其直接的节点不相 似 ,仍可认为这两个非叶节点在结构上是相似的 。对于在 GML 规范定义的三个基本模式中的部分基 本类型 ,可直接进行匹配 。该算法的描述如下 。matching ( schema1 s1 , schema2 s2 )search 基本类型 ,将其下面的节点略去 ,直接看成叶节点 for each e1 为 s1 的叶子 , e2 为 s2 的叶子 设置叶

20、节点的结构相似度算法结束上 述 算 法 中 , 算 法 输 入 为 两 个 树 状 结 构 的 GML 模式 ,输出一个关于两模式间相关元素的映 射关系 mapping 。其 中 , s1 和 s2 分 别 表 示 模 式 1 和模式 2 , e1 和 e2 为模式 1 和模式 2 中的元素 , s1 和 s2 是分别对 s1 和 s2 进行逆序遍历得到的结果 。为了确定两个模式中的元素是否匹配 ,设定 一个阈值 ,只有两个相关元素的相似度值高于这 一阈值 ,才进行匹配 。在算法中 ,两个叶节点的结构相似度初始值为 它们语义相似度的值 。在进行匹配时 ,对树的遍历是采用后序遍历方法 ,同时对每

21、棵 schema 树中元素 与另一棵树中元素的相似度只确定一次 ,而不用双 向的确定方法 。这样做是为了避免在匹配过程中产 生 mn 的匹配关系 。当被比较的节点不是叶节点逆序遍历 s1 = 逆序 ( s1 ) , s2对于 s1 中的每个元素 e1 有= 逆序 ( s2 )时 通过比较两个节点的子节点相似度来确定这两,个被比较节点的相似度 ,即用其所有的子节点的相似度 除 以 所 有 的 子 节 点 数 。令 subnodes ( e1 ) 和 subnodes ( e2) 分别为以 e1 和 e2 为根节点的子树上的 节点的集合 ,sim ( x , y) 为其中一个模式中的节点 x 与另

22、一模式中节点 y 的相似度 ,则有 :对于 s2 中的每个元素 e2计算 e1 、e2 的结构相似度 按公式加权计算出它们的相似度 相似度大于阈值就可进行匹配生成匹配映射关系 mapping返回 mappingsim ( x , y) ( x , y| x subnodes ( e1) y subnodes (sim ( e1 , e2)=sim ( y , x) ( y , x|y subnodes ( e2) xsubnodes ( e1) )subnodes ( e1) subnodes ( e2)(3)对两个 GML 模式进行匹配的输出结果是一系列元素间的映射关系 。一个映射关系包含一

23、系列映 射元素 ,每一个元素描述了 schema1 中的某个特定元 素和 schema2 中的某个元素的联系 。在简单实例中 , 可能只需要叶子层次的映射关系元素 ,即 schema1 的 叶节点和 schema2 的叶节点之间的匹配 。这种映射 关系的匹配基数可能是11 ,也可能是 1n 。如果要产生非叶节点层次的映射关系 ,需要对两个模式进行二次遍历 ,因为经过叶节点的匹配后 ,非叶节点的 结构相似度可能发生变化 。2 . 3 . 3 集成 GML 模式生成算法两个 GML 模式进行匹配后 ,运用匹配算法生 成的映射 (mapping) 可生成集成的 GML 模式 ,称为集成 GML 模式

24、生成算法 。算法输入是模式匹配 算法中生成的 mapping ,根据映射关系 ,算法自动生成包含 GML 树的叶节点层次 ,并在 mapping 中 存在映射关系的元素 。这些生成的元素被包含在一个用户自定义的新 GML 模式中 ,作为算法的输出 。算法描述如下 。Creation (mapping)扫描输入的 mapping ,找出叶节点层次的映射关系 ;询问用户生成的集成 GML 文档的名称 ,把值赋给变量name ;生成新的 集 成 GML 模 式 , 名 称 为 name 的 值 , 元 素 为mapping 中叶节点层次的匹配元素 ;输出集成 GML 模式 ;算法结束 。由于各个系统

25、对生成的集成 GML 模式可能 会有不同需求 ,故本文中仅讨论生成底层元素层 次的集成 ,而将 GML 模式上层结构的定义留到具 体的系统中去做 。模式匹配实例3笔者用一个 GML 模式匹配实例来说明匹配算法的 操 作 过 程 。两 个 输 入 的 GML 模 式 分 别 是schema1 和 schema2 ,都是对同一地理实体定义的模 式 ,但在结构和语义上存在着异构 。首先 ,用 GML模式转换树算法对两个 GML 模式进行转换 ,其中 ,GML 模式文档中的实例元素在转换过程中都被略 去 ,仅对其中的类型及其子类进行了转换 。其中的“包含”和“被包含”关系被转换成为树中父子节点的继承关

26、系 。然后 ,再用 GML 模式匹配算法对其 进行自底向上的匹配 ,先计算出两个模式元素间的第 2 期关佶红等 : GML 模式匹配算法173语义相似度 ,然后再对其进行结构匹配 。如图 3 所示 ,schema1 和 schema2 中 的 linestring 类 型 还 包 括 cord 子节点 ,但由于是一种基本几何类型 ,故可将 其作为叶节点来看待 ,算法从左至右设置两个树中叶节点的结构相似度 。此时由于尚未进行匹配 ,叶 节点的相似度只能从数据类型和名称等语义上的 因素进行考虑 。逆序遍历两棵树生成相对应的 s1 和 s2 ,再通过两个循环分别算出 s1 和 s2 中的元素 间 的

27、 相 似 度 , 将 相 似 度 高 于 规定 阈值的元素进行匹配 。在进行结构匹配的过程中 ,有的非叶节点可能在结构上存在较大差异 ,如图中 schema1 的元素 Geometryproperty 和 schema2 中 的元素 Geo 。虽然它们的子结构有差异 ,但其叶节 点相同 ,都是 linestring ,故它们仍然属于匹配的关系 。匹配完成后 ,输出一个表示两模式中相关元素 间匹配关系的映射 ,这个映射包含所有关于两个模 式元素间的匹配的描述 。如 schema1 和 schema2 的 映射关系 M 中一定包含某一个映射元素 m ,可以 描述 schema1 中的 area 和

28、 schema2 中的 name 间的联系 。图 3 GML 模式匹配后的映射关系图Fig. 3 Mapping Relations of GML Schemas Matching运 用 生 成 的 mapping , 通 过 集 成 GML 模 式生 成 算 法 生 成 一 个 新 的 GML 模 式 , 如 图 4 所 示 。生成的集成 GML 模式包括匹配中生成的 mapping中的两个模式的叶节点层次的匹配元素 ,其名称 以元素在第一个输入的 GML 模式中的名称为准 则 。在具体应用中 ,用户可以自己为集成的 GML 模式中的元素命名 。参考文献1Geography Markup L

29、anguage ( GML ) . http :/ / opengis. net/gml/ 01 | 029/ GML2. html ,2000Madhavan J , Bernstein P A , Rahm E. Generic SchemaMatching with Cupid. The 27th VLDB Conference , Rome ,2001Rahm E , Bernstein P A. A Survey of Approaches to Automatic Schema Matching. The VLDB Journal , 2001 (10) : 334350Doan

30、A H , Domingos P , Levy A. Learning SourceDescriptions for Data Integration. Proc . WebDB Workshop ,2000Pottinger R A , Bernstein P A. Creating a Mediated Schema Based on Initial Correspondences. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering ,2002Li W S , Clifton C. S

31、emInt : A Tool for Identifying Attribute2345图 4 集成 GML 模式样例Fig. 4 Integrated GML Schema Sample68 Guan J H , Zhou S G , Chen J P , et al . Ontology2based GML Schema Matching for Information Integration. ICMLC03 , Xian , 2003Correspondences in Heterogeneous Databases Using NeuralNetwork. Data and Know

32、ledge Engineering , 2000 , 33 ( 1) :4984Reynaud C , Sirot J P , Vodislav D. Semantic Integration ofXML Heterogeneous Data Sources. 2001 Int . DatabaseEngineering Applications Symposium , 20017第一作者简介 :关佶红 ,博士 ,副教授 。现从事分布式 GIS 、空间数据库 、网络计算等研究 。E2mail : jhguan wtusm. edu. cnGeogra phy Markup LanguageSc

33、hema Matching AlgorithmGUAN J ihong1YU Wei1 AN Yang1(1 Research Center of Spatial Information and Digital Engineering , Wuhan University ,129 Luoyu Road , Wuhan 430079 , China)Abstract : The complexity and richness of spatial data models and geographic information systems ( GISs)together with the po

34、pularity of WWW have led to an increasing number of heterogeneous and autonomous geo2referenced information sources that spread over Internet . To integrate and publish geographic information , a challenge is to match schemas between two arbitrary GML documents. In this paper , an algorithm for auto

35、matic matching of two GML schemas is proposed , in which document schema is first transformed to a tree , and then a similarity formula is introduced to measure the semantic and structural matching degrees of two documents based on the transformed trees. The proposed algorithm is implemented in a ru

36、nning GML2based GIS.Key words : GML ; schema matching ; spatial information integrationAbout the f irst a uthor : GUAN J iho ng , Ph . D , a s so ciate prof e s sor , her major re se arch orie ntatio n s include distribute d GIS , sp atial data ba se , network co mp uting , etc .E2mail : jhgua n wtu

37、 sm. e du . cn(责任编辑 :光远)欢迎订阅武汉大学学报信息科学版武汉大学学报信息科学版即原武汉测绘科技大学学报,是以测绘为主的专业学术期刊 。其办 刊宗旨是 :立足测绘科学前沿 ,面向国际测量界 ,通过发表具有创新性和重大研究价值的测绘理论成果 , 展示中国测绘研究的最高水平 ,引导测绘学术研究的方向 。本刊为中国核心期刊 ,国家优秀科技期刊 , 并入选中国期刊方阵 。本刊主要栏目有院士论坛 、学术论文 、科技新闻等 ,内容涉及摄影测量与遥感 、大地测量与物理大地 测量 、工程测量 、地图学 、图形图像学 、地球动力学 、地理信息系统 、全球定位系统等 。收录本刊论文的著 名国际检索系统包括 EI、SCI、P 、C SA 等 ,其影响因子名列中国高校学报前列 。本刊国内外公开发行 ,读者对象为测绘及相关专业的高级研究人员 。本刊为月刊 ,A4 开本 ,96 面 ,每月 5 日出版 ,每册定价 8. 0 元 ,邮购价加 25 % 。本刊邮发代号 :382317 ,欢迎广大读者到邮局订阅 。漏 订者可与本刊编辑部联系补订 。