XML数据的存储实现研究

作为一种信息交换的文档格式已被广泛接受，以XML 这一格式表示的数据及相关技术也获得越来越多的应用。 文档由于易于编写、易于分析而在商业、金融、医XML 疗、科技及其它方面被采用，逐渐与传统数据库技术相互渗 透，在这种情况下，数据库系统中占主导地位的模式概念被 扩展了。文档中，数据结构由它自身来描述，通过定XML 义模式和元数据让数据本身在数据库环境之外具有“含 义” 从而使信息内容与信息的解释相分离 元素标记标识数, , 据的含义，通过嵌套和引用来提供元素间的关系知识等。这 些特点不但有可能构造基于其结构的精确查询，而且使得这 种模型极易作为数据交换方式，是半结构化数据模型的一种 极具前途的应用。规范集承诺将信息集成为数据XMLWeb 库从而改变统治下的“无组织”、“无结构”的,HTMLWeb 信息库面貌。本身还可能成为一种标准语言XMLWeb 1。 另一方面，对数据库系统的研究，也伴随着的出现Web 被极大地推动，同时，信息检索领域的各种技术也在信Web 息检索中获得新生，对信息检索、数据库系统以及本身Web 的研究正在以某种方式融合2，信息库的精确的、基于Web 模式的检索研究，正是这种融合的具体表现之一。本文工作 的重点是研究如何有效地存储数据，以利于将基于内XML 容的数据查询转变为基于结构的查询。 系统简介1 DISXDBS 系统的基本结构如图 所示。用户界面是指用DISXDBS1 户使用的方式，它可以是类似于浏览器的方式或DISXDBS 应用程序方式；文档管理器提供应用程序以结点和全文档方 式存取文档的机制；管理器中的分析器对用户输入或其它来 源的文档以及模式文档进行分析；查询管理器提供基XML 于离散模式匹配查询的实现，具体做法是将匹配查询转换成 问题；模式管理器维护系统的模式集，由于CSPDISXDBS 的模式本身也可表达为树状模型，因此，它本身的存储也与 文档的存储采用一样的方式，存取管理器根据具体XML 存储策略提供对数据库和离散模式集的存取。XML X M L 文档管理器 存/ 取管理器 X M L 查询管理器 离散模式管理器 离散模式集 X M L 数据库 用户界面/ 应用程序 图系统描述图1 DISXDBS 数据的存储2 XML 现有的存储数据方式大致有 种：字节流方式XML3(1) 存储3，在此方式下，文档特有的图树结构被线性化XML 为字节流。当存储和检索整个文档时，这种方式效率较高， 但是，任何一次查询文档时都必须通过分析器处理后才能获 得结构信息，对于我们的模式匹配方式的查询显然是一个不 小的缺点。元模型方式存储(2) 4，这种方式直接保存了文档 的结构信息，它利用传统及其数据模型来存储DBMSXML 文档。例如，将结点转换成中的属性。在这种情况RDB 下，它与结构化的数据库的交互方式与相同，有许多DBMS 现成的应用程序可用。缺点是由存储构造文本视图时速度较 慢。通常的做法是：在逻辑数据与物理数据之间增加代理 层，代价是降低了查询速度。混合式存储 (3) 5，在这种方 式下，某种程度的数据细节被设置为“阈”（），threshold 比“阈”的粒度粗的结构被存储在数据库中已结构化的部 分，而更精细的部分被存储在数据库中字节化了的对象部 分，这种方式的特点是数据查询较快而数据更新较慢。 虽然上述方式各有其特点，但都不适于系统DISXDBS 基金项目：湖南省科技攻关计划资助项目( 99JZY2079 ) 作者简介：吴敏（），男，教授、博导，研究方向：计算 1963 机远程控制，智能控制；徐德智，博士生、副教授 收稿日期：2002-09-21 修回日期：2002-10-30 数据的存储实现研究XML 吴敏，徐德智 中南大学信息科学与工程学院 长沙 (, 410083) 摘要： 正在迅速成为上的信息交换、表示和存储手段之一。文章基于离散模式的数据库系统（）研发工作的存 XMLWWWXMLDISXDBS 储研究部分简明扼要地介绍了当前数据的主要存储技术，探讨了保证高效查询的数据的存储方法，最后给出了实验分析。 ,XMLXML 关键词：；数据模型；存储模型 XML Research of XML Data Storages Realization WU Min, XU Dezhi (College of Information Science and Engineering, Central South University, Changsha 410083) 【】Abstract XML is surging as one of the new approaches of information representation, tradeoff and store on WWW. The paper introduces a conception of XML data storage and three categories for XML data storage. Then, the storage approach of XML data is studied. Finally, the paper analyzes the approach performance. 【】Key words； XML Data modelStorage model 第卷 第期2915 Vol.29 15 计 算 机 工 程 Computer Engineering 年 月20039 September 2003 博士论文 中图分类号： TP393.09 文章编号：10003428(2003)15 002502文献标识码：A 25 的数据存储和基于离散模式匹配的数据查询。我们充XML 分利用数据和离散模式均以图 树作为其数据模型这一XML/ 特点，提出了一种简单实用的基于结构的数据存储模型，并 给出其具体物理存储上的查询实验结果分析。 为了叙述方便，本文采用带标记的树来表示文档XML 结构，不难看出，将一个图表示转换为树表示的XMLXML 代价是冗余存储。例如，图 表示了图 所示的对象的32XML 标记树，这种方式不损失任何文档的结构信息。实际XML 上，考虑物理存储结构时，如无特殊需要，仍将其作为图来 对待，以邻接表方式表示。作为树来对待时，图 中所示的3 存储冗余实际上只是一个指针。 D o c N o d e = R E C O R D C o n t e n t : A d j L i s t ; N e x t : P o i n t ; F l a g : 0 . . 1 ; E N D ; 其中，域中的 表示该记录存储的是一完整文档图Flag0XML 树； 表示该记录存储的是一文档子图子树。1XML 在某些情况下，可能很大，超过物理磁盘一簇的XML 容量。实际上，一个记录的内容将出现在物理磁盘的不同 簇，降低了存取数据的效率，此时，将一个逻辑记录分解为 多个物理记录。问题是：如何选择拆分图的拆分点？(1) (2) 如何拆分一个大记录为若干个小记录？树的结点拆分方法B- 给了我们启发，不同的是，树是将中间关键字上提，将左B- 右两边的关键字拆分成两个子集，基于统计观念，当记录的 体积越界时，总是可以从根结点开始拆分成平均结点数相等 而且体积差最小的两个记录，为了实现这一要求，我们在表 示结点的记录域中设置了域和域，某结点的WeightSeqNum 域记录该结点的孩子结点数目，域记录结点WeightSeqNum 的顺序号。如图 所示为一个分解示例。5 & 1 & 1 3 & 1 2 & 9 & 6 & 6 & 1 o u t 1 i n 1 & 1 3 & 1 2 & 9& 6 & 6 o u t 2 i n 2 图结点的拆分存储5 实验结果分析3 我们用上述的数据存储模型实现数据存储，为了XML 比较研究在查询下基于结构的存储方式与字节流存储方式的 效率，选取实验的环境如下：数据的实际存储处理由C/C+ 实现，奔腾 ，硬盘以及平台。-128MB RAM20GBDOS 另外，用软件方法降低了系统运行速度以放大实验效果。 在同样的查询算法下，将基于结构存储方式下的查询时 间数据规模变化与文献中的字节流方式存储下的这种3 变化作了对比，结果表明：在总体上，对基于模式匹配的查 询而言，本文的存储方法更占优势（见图 ）。除此之外，6 我们还对几种典型的存储方式的空间利用率、算法的复杂性 等方面进行了比较研究，得出了一些有益的结果。 图存储的结构方式与字节流方式效率比较6 4 结束语 实际应用中，在具体求解模式匹配（查询）问题时，我 们发展了一套将模式匹配问题转化为问题的有效方法，CSP 从而使模式匹配问题的求解有许多成熟的算法可用。 元约n 束的问题总能转化为一元和二元约束的问题，而一CSPCSP 元和二元约束总是能用约束图来表示。在约束图中，结点表 示变量，弧表示由它连接的两个变量之间的约束，一元约束 由产生及终止于代表同一变量的结点的弧表示，故约束也能 用图来存储。 本文提出的数据模型上的数据存储特点如下：XML 存储是逐个结点进行的，因而存储是无损的； (1) 数据存储与模式及约束存储相分离，且可存储任意的 (2) XML 数据； 对于大规模数据，给出了一套存储分解办法，因此，能较 (3) 好地解决大规模数据的有效存储。 26 （下转第页）47 析技术进行挖掘结果分析，从而实现优势互补。但可能会产 生以下两个问题：对于某一挖掘主题，通过不同技术进(1) 行分析得到的结果可能不尽相同，这时，会产生如何筛选最 优方案的问题；如果出现极端情况不同技术进行分(2) 析得到的结果相互矛盾，这时又如何进行取舍。因此，如何 整合不同的模式分析技术进行分析也是开发访问信息挖Web 掘系统的一个难点。 访问信息挖掘系统研究的关键技术3.2 Web 语言3.2.1 XML 如上所述，基于获得完整准确的访问信息源数据的需 要，必须结合服务器端、客户端和网络代理端的数据挖掘用 户访问模式，而且访问信息挖掘不能同网站内容信息和结构 信息完全割裂开来（如），另外，每一站点数据都Websift 是独立设计，而且数据本身具有自述性和动态可变性，这样 访问信息挖掘面临的对象就是大量的半结构化数据。对这样 的数据进行挖掘，必须以半结构化模型和半结构化数据抽取 技术为前提。目前能够解决异构数据的集成问题的是Web 语言。它是一种类似的，被设计用于描述数据的XMLHTML 语言。它能够在上实施精确查询与模型抽取。其特点Web 是：实现异构数据集成；易于作数据交换；将计(1) (2) (3) 算负载从服务器转移；根据需要过滤显示信息。Web(4) 已经采用了语言进行半结构化数WWWPal SystemXML 据抽取并建立了相应的数据库，它为如何在访问信息挖掘中 使用语言提供了有益的思路。XML 数据仓库、与3.2.2 OLAPOLAM 数据仓库与其他一般数据库截然不同的特征是：面向主 题（针对特定主题组织），集成化（将异种数据源集成在一 起），时变性（从历史角度提供信息）等。可按照访问信息 挖掘的特定主题进行数据抽取，而排除其他无用的数据，从 而提高挖掘效率。访问信息挖掘的数据来源广泛，利用Web 数据仓库能方便地将其集成在一起。技术往往同数据OLAP 仓库结合在一起使用，它们都是基于多维数据模型。在多维 数据模型中，数据组织成多维，每维包括由概念分层定义的 多个抽象层。这样就为用户从不同角度观察数据提供了灵活 性。而技术可以针对这一模型进行操作，物化这些不OLAP 同视图，允许交互查询和分析数据，因而为交互数据分析提 供了友好的环境；另外，提供了分析建模机制，能在OLAP 每一粒度级和在所有维的交叉产生汇总、聚集和分层。因 此，利用可以方便地对访问信息数据仓库进行总OLAPWeb 结性汇总性分析。结合这样的的分析结果进行数据挖OLAP 掘显然提高了工作效率。 的特点是：在线性与多维分析。在线性体现在与OLAP 用户的交互与快速响应；多维性是指在多维视图的基础上， 用户积极参与分析过程。但同数据挖掘相比，的分析OLAP 结果属于较浅的层次，数据挖掘则强调更深入地分析数据及 分析过程的自动化，它无须用户参与。但在实际应用中，用 户也希望参与数据挖掘，如只想对数据的某一子集进行挖掘 或对不同抽取、集成水平的数据进行挖掘，还有根据自己的 需要动态选择挖掘算法等。因此，在访问信息挖掘系统Web 中必须使二者协调一致，才能体现优势互补，更好地完成挖 掘任务。文献针对访问信息挖掘系统提出利用6WebOLAM 框架来解决这一问题，它包括 个部分：数据捕捉，数据仓4 库构建，模式发现和模式评价。意为联机分析挖掘，OLAM 它将与数据挖掘结合在统一的框架下。可以在不同抽OLAP 象级别上对访问信息进行交互挖掘多层次的知识。 在数据仓库中实现的关键是解决快速响应的问OLAM 题，获得快速响应要比困难，因为数据挖掘的OLAMOLAP 时间开销比大。而快速响应对于交互挖掘至关重要，OLAP 有时为了获得快速响应而不得不牺牲精度。可以采用逐渐精 化数据挖掘质量的方法：先在大数据集上用快速挖掘算法标 示出感兴趣的模式 区域，然后用时间开销大而精度高的算/ 法。另外，将引入访问信息挖掘系统，必须考虑OLAMWeb 提高服务器的执行效率和响应速度。从发展趋势看，OLAM 采用将是未来访问信息挖掘系统的必由之路。OLAMWeb 结束语4 本文介绍了访问信息挖掘系统的工作过程及研究概Web 况，并对系统开发遇到的问题进行了探讨。访问信息挖Web 掘作为挖掘的分支，其应用主要集中于个性化用户服Web 务、改进系统性能、网站设计改进、商务智能和网站特征提 取等方面。今后在蓬勃发展的电子商务方面也会有良好的应 用前景。 参考文献 1 Cooley R, Tan Pangning , Srivastava J. Discovery of Interesting Usage Patterns From Web Data. Technical Report TR 99-022, University of Minnesota, 1999 2 Baraglia R, Palmerin P. Suggest: A Web Usage Mining System. In: Proceedings of the International Conference on Information Techno- logy: Coding and Computing, IEEE,2002 3 Zaiane O, Xin M, Han J. Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs. In Advances in Digital Libraries, Santa Barbara, CA, 1998:19-29 4 Punin J R, Krishnamoorthy M S, Zaki M J. Web Usage Mining-lan- guages and Algorithms. 2001 5 Shahabi C, Kashini F B, Faruque J. A Reliable, Efficient, and Scalable System for Web Usage Data. 2001 6 Hu Xiaohua, Cercone N. An OLAM Framework for Web Usage Mining and Business Intelligence Reporting. Department of Computer Science University of Waterloo, Canada , IEEE, 2002 （上接第页）26 参考