基于RDBMS的XML数据存储研究，本文主要内容关键词为：数据存储论文,RDBMS论文,XML论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
【分类号】TP311.132
1 引言
随着大量XML数据的出现，如何有效地存储和查询这些XML数据就成为一个重要问题。目前，XML数据的存储有四种不同的方式：一是利用操作系统文件存储机制，建立平面文件数据库，这种方法简单直接，但查询文档时需要将文档解析为内存中DOM树结构，文档的大小受到内存容量的限制，且这种方法不能进行集中查询；二是利用面向对象的数据库系统，需要设计比较复杂的应用程序，其大规模集中查询的效率不太理想；三是利用关系数据库系统，把树形的XML文档分解成关系存储到关系数据库中，这种方法充分利用关系数据库系统已经非常成熟的技术，如数据存取的高效性、数据完整性约束、并发访问控制机制、强大的安全机制等，其缺点是：需要建立XML数据到关系数据的映射；查询输出时需要通过表的连接重构XML数据。四是建立一个特殊的数据库系统，或称为Native—XML数据库系统，如Tamino、TextML等商业化产品，这主要利用特殊的索引机制来进行数据查询，其技术目前还不能与关系数据库系统相比。由于关系数据库系统本身优秀的特征和目前大量的用于交换的Web数据主要存储在关系数据库中，基于RDBMS的XML数据存储技术受到众多研究者的关注[1-5]。
基于RDBMS的XML数据存储算法有多种，但大体上可分为两类方法。第一类方法是根据XML文档数据的物理结构设计关系模式，即将XML文档的图（树）形结构映射为关系模式，其算法理论主要是图（树）的结构存储；第二类方法是根据XML文档数据的逻辑结构设计关系模式，即根据XML的结构定义（DTD或XML Schema）来设计关系表，其算法理论主要是图状逻辑模型到E—R逻辑模型的转换。可见，第一类方法不需要文档本身有结构定义（DTD或XML Schema）。第一类方法还可分为基于边的存储和基于结点的存储。本文将结合XML文档实例对上述方法进行分析和探讨。
2 XML文档的物理结构和逻辑结构
XML文档由元素组成，一个元素可由一个或多个子元素组成，元素之间呈嵌套的层次结构，每个文档只有一个元素作为根结点，XML的文档实例见图1。一个XML文档的物理结构可看作是一颗树（图2），此时元素的属性和元素的子元素都被看作该元素的儿子结点。
（元素的属性和元素的子元素的主要区别是：①每种属性在元素中只能出现1次，它与该元素的关系是1对1，而子元素可以多次出现，它与该元素的关系是多对1；②属性不含有子属性，而子元素还可含有其下属元素。）
XML文档的DTD或XML Schema是文档的逻辑结构描述，可看作是文档的元数据定义。图3为图1中文档实例的DTD，其中，“＊”表示元素与子元素之间的1对0或多的基数约束，“＋”表示1对1或多，“？”表示1对0或1，“｜”表示在并列子元素中选择一个。一个符合XML标记规范文档被称为良构（Well-formed）的文档，而一个符合给定的DTD的文档被称为有效（Valid）的文档，可见，一个XML文档允许没有DTD，DTD的主要作用是规范某类文档。通过对DTD的解析，文档实例的逻辑结构可表示为图4。
3 基于文档物理结构的关系存储
3.1 基于边的关系存储
基于边的存储的主要思路是：设计若干个关系来存储数据图（图2）的边信息（称为边表），再设计若干个关系来存储图的叶节点信息（称为值表），或直接将值表内联到边表中去，也就是将树状的图结构中的边和节点都存储到二维关系表中[5]。表1为针对图2设计的内联式关系表。首先以先根次序遍历文档树中每个结点，并赋予每个结点一个惟一的标识ID。表1中的每一个元组存储文档树的一条边，边的起点标识ID存储在Source属性中，终点ID存储在Target属性中，终点的元素标记存储在Tag中，结点元素的值存放在Value中，Ordinal表示边的次序。
表1 内联式关系表
sourcetag
ordinal target value
0objects
01 null
1object02 null
1object114null
2objectID 03 object01
2type 14 Book
2book 25 null
5booktitle 06 Data Mining
5year 17 2000
5author28 null
5author312null
8name 09 Jiawei Han
8address
110Canada V5A 1S6
8email 211dmbook@cs.sfu.ca
12
name 013Micheline Kamber
14
objectID 015object02
14
type 116Article
14
article
217null
17
articletitle 018Join Indices
17
year 1191987
17
author220null
17
source322null
20
name 021P.Valduriez
22
journal
023ACM Trans.Database System
22
volume12412
22
page 225218-246
针对上述算法，可作如下改进：
（1）在关系表中增“边类型”属性，表示该边是“属性边”还是“元素边”或者“参见边”；
（2）按tag将一个关系表拆成若干个关系表，提高查询效率，毕竟属性查询的利用率较高。
3.2 基于结点的关系存储
基于结点的存储又叫基于区间编码方案的存储[1，5]，其主要思路是：对文档树中的所有结点按一种或多种遍历次序（先根遍历、后根遍历、层次遍历）进行编码，存储时不仅要把各个结点本身信息存储起来。而且还必须把树中各个结点之间的关系（父／子关系，兄／弟关系、祖先／后代关系等等）反映在存储结构中。如设计关系元组（ID，ParenrID，Depth，Nodetype，Value）表示（结点标识，父结点标识，深度、元素类型、值）。
4 基于文档逻辑结构的关系存储
基于文档逻辑结构的存储的主要思路是：将文档逻辑结构的描述DTD（本文主要讨论DTD）经过转化，生成DTD图，再将DTD图按照一定的映射方法转换成若干关系表。
4.1 生成DTD图
一个有效的XML文档必定符合它的DTD所描述的元素与其子元素和属性间的嵌套关系，而DTD正是通过其操作符“？”、“｜”、“＊”、“＋”等约束上述关系，如＜！ELEMENT（a｜b？，c）＊）＞。但在关系数据库设计时，一般不特别精确地表示“｜”、“＋”的基数约束。因此在基于文档逻辑结构的关系设计时采取一种简化DTD文法的思想，即用“＊”表示“＋”，用“，”代替“｜”，上述元素可以简化为＜！ELEMENT（a＊，b＊，c＊）＞。由此，将一个简化后DTD转化为一个有向图，见图4。图中每个结点以元素或属性的标记表示，有向边表示源结点与目标结点是元素与子元素或元素与属性的关系，边标记“＊”“？”表示元素与子元素之间是1对多和1对0或1的基数约束，不带符号的边表示元素与子元素之间是1对1的关系。DTD模型是图结构，但不一定是树结构，因为某些结点的入度大于1（如图4中的“author”结点和“year”结点），而且DTD的根节点并不一定惟一。
4.2 映射成关系表
结合文献[2]提出的三种映射技术（Basic-inlining，Share-inlining，Hybrid-inlining），设计DTD图到关系模式的映射规则：
（1）DTD图中入度为0的结点（即根结点）单独映射成关系，关系名为该结点标记，其包含的属性见规则（5）；
（2）DTD图中边标记为＊的目标结点（即多值子元素结点）映射成独立的关系，其关系名为该结点标记，其包含的属性见规则（5）；
（3）DTD图中入度大于1的结点，若为叶子结点（不含属性或子元素），则与分别列入其父元素所在关系，否则单独映射成关系，其关系名为该结点标记，其包含的属性见规则（5）；
（4）DTD图中边标记为“？”的目标结点所映射的属性，其值允许为Null；
（5）DTD图中入度等于1的结点可成为其祖先结点所生成的关系模式的属性（列），结点X成为以Y根结点的关系R的属性的条件是：Y到X的路径是可达的且这条路径中不包含规则（1）（2）（3）所述的能独立生成关系的结点；
（6）对于每个关系，设立ID和ParentID属性，ID作为该关系的主键，其值为XML文档数据图（图2）中结点标识（先根遍历），ParentID作为外键，指向其父关系。
根据上述规则解析图4，生成的关系如图5：
5 评述
对于基于RDBMS的XML数据存储方法，学界褒贬不一，但大致从以下几方面来看：
（1）从XML到RDBMS转换时，信息是否无损；
（2）各种查询（属性查询、路径查询、标记查询、集中查询等）的效率如何；
（3）从XML转换到RDBMS和从RDBMS恢复到XML的算法复杂度；
（4）插入数据操作的代价。
基于文档物理结构的关系存储包含的关系表较少，实现信息的无损转换，支持属性查询、路径查询、标记查询，插入数据操作时需重构关系。该技术由于没有充分利用RDBMS的特长，查询效率较低，比较适合较小的不含DTD的文档。
基于文档逻辑结构的关系存储包含的关系表较多，信息转换有损，表现如下：
（1）“＋”约束扩展成“＊”约束等；
（2）为尽量减少关系表的数量，规则（5）将元素化为其祖先结点关系（而不是其父结点关系）的属性；
（3）属性与子元素都映射为关系的属性。
该技术支持标记查询，大规模集中查询，查询效率较高，但不支持路径查询。另外，当关系较多时，从RDBMS恢复到XML需要多次连接关系表，影响效率。如果DTD图中没有入度大于1结点，则ID按数据出现顺序编码，插入数据操作的代价不大。基于文档逻辑结构的关系存储的改进办法有：通过建立路径索引的办法支持路径查询；进一步优化关系表，如：
（1）查询频率较高的元素及其子元素单独映射成关系；
（2）如果一个文档子片的结构比较固定，大小比较一致，能形成定长元组，将其设计在同一关系表中，能提高数据的存取效率；
（3）可采取中粒度存储方式，允许某些属性的值为含有元素标记的文档片段，减少表的数量[6]；
（4）利用RDBMS的有关模式设计理论。
总之，基于文档逻辑结构的存储比较适合有效的（含DTD）、广度较大、层次较少的大型XML文档。
标签：xml语言论文; xml数据库论文; 逻辑结构论文; xml解析论文; 内存映射论文; 数据存储论文; 叶子结点论文; 关系逻辑论文;