基于前缀编码的模型映射改进方法研究

孙天翔

[摘要]提出基于前缀编码的模型映射改进方法，实现XML半结构化数据到关系数据库的映射，从而为将半结构化数据管理转化为传统关系数据库管理奠定基础。

[关键词]半结构化数据 关系数据库 XML 前缀编码

中图分类号：TP3 文献标识码：A 文章编号：1671－7597（2009）0120057－01

一、引言

互联网上存在着各种形式的数据，其数据结构的组织方式也各不相同，因此，半结构化数据模型应运而生，其无模式及自描述的特点适宜于描述网上数据。但传统的数据库管理系统主要用于管理结构化的数据，半结构化数据与传统的数据库管理系统的模式有很大不同。如何对半结构化数据实施有效的管理成为新的研究领域。

二、半结构化数据的描述

（一）XML半结构数据

Internet的发展使XML成为互联网上数据交换或数据浏览的转换媒介，XML数据属于半结构数据模型。专用的半结构化数据管理系统目前仍处于初步实验阶段。但是可行的方法是将半结构化数据转化为结构化数据，采用关系数据库对XML数据进行存储和操作。这样才有可能把Web上海量的半结构化信息结构化，进行统一的管理、控制和操作。

（二）半结构化数据的描述

目前对半结构化数据的自动抽取、数据模型、查询语言等一种常见的描述方法的模型是OEM模型[1]。OEM模型由表示对象的结点和带标签的有向边构成的图。在OEM模型中所有的实体均为对象，每个对象用一个四元组来表示：(ID,LBL, type, value)。其中LBL是对象的标签描述，type是对象类型。OEM模型可以用一个带根有向图G(r,V,E)来表示，其中r表示根节点；V表示对象集；E是有向边的集合，边上的标签表示对象之间的关系，记作，他表示对象I通过标签为L的边指向另一个对象J。每一个图都有一个对应的存储表示方法，邻接矩阵和邻接表是图的两种最常用的存储结构。OEM模型是一个有向图，于是就可以采用有向图的存储表示方法来表示OEM模型。

三、XML半结构化数据到关系数据库的映射

随着XML技术的出现和对XML技术的深入研究，半结构化数据和XML数据模型之间的对应关系越来越明显，因而把XML数据到关系数据库的映射为是至关重要的一步。

（一）XML文档编码

XML文档可以被描述为树模型，文档中的元素、属性和值对应于树模型中的结点，其中属性用@前缀区别，文档中元素与元素、元素与结点以及元素与值对应于树模型中的边。

将XML文档映射为关系模式存储，可以通过对XML文档树的结点进行编码，通过编码直接判断结点之间的结构关系。编码方案主要有以下几种：位向量编码、区间编码、前缀编码和哈夫曼编码等。前缀编码也称Dewey编码[2]。前缀编码直接将一个结点的双亲结点的编码作为该结点编码的前缀，这种编码方案保存了文档的结构信息。对于前缀编码，要判断一个结点v是否是另一个结点u的后裔，只需判断字符串c(u)的前缀是否是c(v)的前缀。前缀编码的一个重要性质是它们的字典有序：以结点r为根的子树中的任意一个结点u，它的前缀编码c(u)大于（小于）它的左兄弟子树（右兄弟子树）中所有结点的前缀编码。因此，前缀编码不仅能够有效的支持包含关系的计算，而且能够有效地支持文档位置的计算。本文在采用了Dewey编码的基础上，对XML文档进行关系模式存储。对XML文档树从根结点以0开始编码，作为第一层次的结点；第二层次的结点编码从00，01，02……开始，依次递增；同理，第三层次的结点编码从000，001，002，003……开始，依次递增，依次类推。但是有一点需要我们注意，如果XML文档树的度不超过10，我们可以从0到9数字进行扩充，如果XML文档树的度超过10则可以用a,b,c等字母依次排列进行编码。

（二）XML文档存储结构

对XML文档树编码工作完成之后，设计若干关系来存储XML文档树中的结点信息、结点值信息和结构信息。本文使用三个表来存储XML文档，存储XML文档的关系存储模式如下所示：

Document (DocID, XMLDoc)

Code_Path (DocID, Code, Pathexp)

Element (DocID, Code, Element, flag, value)

其中，Document表用来存储XML文档信息，DocID为XML文档的代码，XMLDoc为XML文档的保存路径；在Code_Path表中，Code为各结点对应的编码，Pathexp为采用路径方式表达的结点位置；在Element表中，Element为结点的元素名或者是属性名，flag为结点元素的类型，结点类型分为叶结点和非叶子结点，叶子结点类型分别为integer, decimal, string等，但此处在这个模式映射方法中，论文用0和1来区分，也就是说，如果为叶子结点则为0，否则为1；value为叶子结点对应的值，如果为非叶子结点的话，则该值为空。

（三）XML查询

基于关系存储的XML查询最终都要将XML查询转化为SQL查询，并将SQL查询得到的平坦表形式的结果再转化为XML文档返回给用户或应用。但是XML查询语言比SQL要复杂得多，它们一般通过路径表达式来对XML文档中的嵌套结构进行查询，而且路径表达式中可以包含各种查询轴和谓词，谓词中又可以包含路径表达式、操作符和函数等。转换XML查询为SQL查询对于基于关系的XML数据库的发展前途起到决定性的作用。

XPath是一个XML查询语言，它用来描述在一个XML文档树中的查询导航。

XML查询的核心是XPath路径表达式查询。XPath是文档之内进行信息寻址的一种方法，目的在于自动化搜索操作，方便编程用户访问信息。XML查询按照复杂程度分为3类[3]：

简单查询：只含有父子关系或祖先子孙关系的路径查询；分支查询：带有分支谓词的路径查询；带通配符的查询：包含通配符的路径查询。

四、小结

本文结合现有的OEM模型，通过对OEM模型图的遍历，把OEM模型所对应的图结构转换为相应的XML文档，生成XML数据，实现半结构化数据向XML文档的映射。基于所生成的XML文档，通过分析XML文档和数据库技术的相互映射方法，采用一种基于前缀编码的模型映射方法，实现XML数据和数据库的映射。

参考文献：

[1]蒙德龙等.半结构化数据的模式抽取[J].计算机工程与应用,2006(27):16

2-165.

[2]鲁明羽等.基于OEM模型的半结构化数据的模式抽取[J].清华大学学报（自然科学版）,2004年第44卷第9期:1264-1267.

[3]吴共庆等.一种基于XML的半结构化数据存储方法[J].计算机工程,2004年5月第30卷第10期:57-59.