计算机科学与技术专业论文xml查询算较系统的设计与实现.doc

毕业设计（论文）

（XML查询算较系统的设计与实现）

（XXX）

燕山大学XX学院

年 月

毕业设计（论文）

（XML查询算较系统的设计与实现）

学 院：
专 业：
学生 姓名：
学 号：
指导 教师：
答辩 日期：

燕山大学XX学院毕业设计（论文）任务书
学院： 系级教学单位：
学
号

学生
姓名

专 业
班 级

题
目
题目名称
XML查询算较系统的设计与实现
题目性质
1.理工类：工程设计 （ ）；工程技术实验研究型（ ）；
理论研究型（ ）；计算机软件型（ ）；综合型（ ）
2.文管理类（ ）；3.外语类（ ）；4.艺术类（ ）
题目类型
1.毕业设计（ ） 2.论文（ ）
题目来源
科研课题（ ） 生产实际（ ）自选题目（ ）
主
要
内
容

基
本
要
求

参
考
资
料

周 次
第 ～ 周
第 ～ 周
第 ～ 周
第 ～ 周
第 ～ 周
应
完
成
的
内
容

指导教师：
职称： 年 月 日
系级教学单位审批：
年 月 日
注：表题黑体小三号字，内容五号字，行距18磅。（此行文字阅后删除）

摘要
摘要
XML(Extensible Markup Language)即可扩展的标记语言，是一套定义语义标记的规范，其目的在于定义计算机和人都能方便识别的数据类型。随着网络应用的快速发展，XML己经被广泛应用到Internet智能信息检索、数字图书馆、数据集成、Web Service等领域，这使得XML类型的数据已成为主流的数据形式，从XML数据中提取有用的信息也就成为了当前的研究热点。
目前，XML查询根据查询请求描述特点的不同，可概括为两大类查询模式：XML结构化查询和XML关键字查询。XML结构化查询要求用户必须掌握 XML文档结构及查询语言，这对用户来说有着较大的难度，不易使用。而XML 关键字查询则相对比较灵活，它只需要用户提供简单的关键字信息，而无需懂得任何查询语言或文档结构就可方便使用，因此该模式被广泛采用，有着重要的研究价值。
使用关键字检索在万维网中查询HTML文档是证实并且容易使用的一种方法。我们建议在XML文档中使用关键字检索，建模为有标号树，并且描述有效算法。这个被提议的关键字检索返回一个包含所有关键字的最小树的集合，这里的最小树是指它所包含的子树中没有包含所有关键字的树。在这里提出Lookup Eager algorithm算法，利用最小树的关键属性使得当查询包含的关键字有着显著不同的频率时在数量级上超越之前的算法。Scan Eager是ILE、算法的另一个版本适合于关键字有相似的频率。本文也呈现了XML关键字搜索系统，利用ILE算法来实现。

关键词　XML关键字查询；最紧致片段；SLCA

I

燕山大学本科生毕业设计（论文）
Abstract
XML，stands for Extensible Markup Language，is a standard of semantic markup．It defines the data type aimed at easily recognized by both computers and users．With the fast development of network applications，XML has been widely applied to the Internet intelligent information retrieval system ,digital libraries，data integration， Web Service and SO on，which makes XML become a primary data form．So how to find the useful information from XML data has been a hot research area.
According to different features of XML Query request，We Call divide the XML Query strategy into two categories：XML Structural Query and XML Keyword Query．XML Structural Query requests users to master the XML structure and exquisite query language．It is a big challenge to users .However ,XML Keyword Query is much more flexible．Users can easily use it by only providing keyword information instead of any query language or document structures．So this strategy is widely used and valuable to study.
Keyword search is a proven, user-friendly way to query HTML documents in the World Wide Web. We propose keyword search in XML documents, modeled as labeled trees, and describe corresponding efficient algorithms. The proposed keyword search returns the set of smallest trees containing all keywords, where a tree is designated as “smallest” if it contains no tree that also contains all keywords. Our core contribution, the Indexed Lookup Eager algorithm, exploits key properties of smallest trees in order to outperform prior algorithms by orders of magnitude when the query contains keywords with significantly different frequencies. The Scan Eager variant is tuned for the case where the keywords have similar frequencies. We also present the XKSearch system, which utilizes the Indexed Lookup Eager algorithms。.

Keywords　XML Keyword Search; The Smallest Fragment; SLCA

III

目 录

摘要 I
Abstract II
第1章 绪论 1
1.1 选课目的 1
1.2选课背景和意义 1
1.3国内外研究现状 2
1.3.1最紧致片段研究现状 3
1.4论文主要研究内容 4
1.5论文组织结构 4
第2章 相关技术介绍 6
2.1开发环境与开发工具 6
2.2 Java语言介绍 6
2.3 MyEclipse介绍 7
2.4 MySQL介绍 7
2.5 JDK介绍 8
2.6本章小结 9
第3章 Index Lookup Eager算法原理与实现 10
3.1 最紧致片段及SLCA相关概念 10
3.1.1XML数据及其树结构 10
3.1.2最紧致片段相关概念 13
3.1.3 SLCA概念详述 14
3.2 ILE算法原理 15
3.2.1前缀编码 15
3.2.2 Dewey编码 16
3.2.3ILE算法基本思想 17
3.2.4 ILE算法示例及分析 18
3.3 ILE算法的实现 21
3.3.1查询左右匹配节点 23
3.3.2求解最低公共祖先LCA 24
3.3.3求解孩子节点 25
3.3.4求解节点的祖先关系 26
3.4本章小结 27
第4章 SLCA查询系统的实现 28
4.1 数据库的实现 28
4.1.1解析XML文档 28
4.1.2数据库的设计 29
4.2 配置开发环境 31
4.2.1安装JDK 31
4.2.2 安装MySQL数据库 31
4.2.3 安装MyEclipse 32
4.3 页面设计和实现方法 32
4.3.1主界面 32
4.3.2查询功能的实现 34
4.3.3数据库的连接 35
4.4本章小结 35
第5章 软件测试 36
5.1软件测试的方法和步骤 36
5.2测试用例设计与过程及结果分析 36
5.2.1 单元测试 36
5.2.2 集成测试 37
5.2.3 验收测试 37
5.3 评价 37
结论 38
参考文献 39
致谢 41
附录1 开题报告 42
附录2 中期报告 48
附录3 文献综述 52
附录4 外文原文 57
附录5 外文翻译 11

V
参考文献
第1章 绪论
1.1 选课目的
随着计算机网络和Internet的发展，在万维网上的文档资料越来越丰富。近年来，万维网已经成为资讯分享的主要平台，但是以HTML表示的网页资料，并不适合自动化处理。为此W3C制定了XML，允许使用者自己定义文件所需的标签和结构，以用来表述资料本身的涵义。现已有相当多的企业或组织，将资料以XML表示，以便网络上的资料交换与处理。
XML上的关键字检索由于不需要对XML的模式有所了解,对用户来说是简单而实用的。在XML上的关键字检索正在成为一个研究热点。XML上的关键字检索不需要用户对所查询的XML的DTD或模式、复杂的XML查询语言等相关知识有所了解，因此更容易被用户接受。通常在web上的关键字检索，比如Google或者百度，他们的返回结果是包含用户提供的关键字的整个网页，属于文档级。但如果对大XML文档上的关键字检索，由于XML文档被建模成树形，有着层次嵌套的关系，用户通常希望得到最小结果片段，此时查询的粒度不再是文档级别而是元素级。所以， 更加详细的检索出用户所需要的信息是网络的迫切需要也是用户的迫切需要。如何检索出用户最需要得到信息即如何快速有效计算出关键字之间最紧密的联系是一个有广泛应用前景的课题。
1.2选课背景和意义
XML（Extend MARKUP Language）由于其具有的子描述性、灵活的数据结构以及丰富的数据表示能力等特点，现在已经被广泛应用到Internet智能信息检索、电子商务中的数据表示和数据交换、数据集成、Web Service、数字图书馆等领域。这使得XML类型的数据成为当前流行的数据形式，对XML数据的有效管理也随之成为当前数据库领域研究的热点。
作为日渐广泛采用的数据形式，从XML数据中提取有用的信息是一个不可回避的研究内容。为了从自描述的、半结构化的XML数据中抽取用户感兴趣的信息，研究人员开发了许多查询描述形式，文献根据查询请求描述特点的不同，可概括为两大类查询模式：XML结构化查询和XML关键字查询。
XML结构查询首先定义精确的查询描述语言，用户借助它来描述自己感兴趣的模式，将用户的模式交由实际的XML数据处理系统处理，然后返回与模式相匹配的结果。这就要求用户掌握XML文档结构及查询语言。然而Internet的大多数使用者，是那些既不懂得查询语言，又不了解XML文档结构的普通用户，这时基于关键字的XML数据查询是比较方便的，他只需要用户提供简单的关键字信息，而无需要用户懂得任何查询语言或文档结构。
XML关键字查询中，主要有两种方式：一是直接将纯关键字方式不加修改的应用到XML数据查询中；二是辅助信息限定关键字所在节点的范围，例如标签或标签路径信息。由于后者引入的标签信息使得用户还要了解XML数据的实际组织，增加了用户使用的复杂性，而从本质上讲，这种扩散关键字的方式只是增加了过滤关键字节点的作用，实际处理与纯关键字方式并无本质区别。因此，大多将研究的重点放在纯关键字查询中。
XML关键字查询的基本问题是获得所有满足关键字组合语义的最紧致片段，对最紧致片段的定义及求解最紧致片段的算法性能将直接影响到XML关键字查询的性能和准确率，而这恰恰是用户最关心的方面。
分析国内外在XML最紧致片段上的研究得知，目前，定义最紧致片段的概念中最好的是SLCA(Smallest Lowest Common Ancestor),因此，本文将重点对SLCA的概念及求解SLCA的算法进行研究，以提高XML关键字查询的性能和准确率，这对用户有着重要的意义。
1.3国内外研究现状
XML关键字查询根据查询请求描述特点的不同，可概括为可概括为两大类查询模式：XML结构化查询和XML关键字查询。
XML结构查询下的算法偏向于传统的结构化查询算法，即采用了正则表达式的描述形式。XML结构查询首先定义精确的查询描述语言，用户借助它来描述自己感兴趣的数据，XML结构查询引擎返回按照用户需求的形式化描述而检索到的XML片段。目前，属于此类的查询语言有很多种，包括：Lorel ,XML-QL ,Quilt ,Xpath ,Xquery等。
目前，该类查询语言发展到现在已经出现了集中的趋势，其代表为W3C推出的Xpath和 Xquery。然而该类的查询语言的缺陷是很明显的：首先，查询语言的使用者必须学习相关的语法机制，这一点本身就加强了用户使用它的难度。而且用户即便已经掌握了相关的查询描述机制，如果不了解实际要查询的XML数据的组织情况同样不能完成查询语句的书写。
针对绝大多数用户并不了解XML文档结构和查询语言的现状，XML关键字查询提出可以根据用户提供的查询关键字得到用户期望的信息，不需要用户了解XML文档结构及查询语言，适合绝大多数用户使用。
1.3.1最紧致片段研究现状
在XML关键字查询中．，最基本的问题就是获得所有满足关键字组合语义的最紧致片段。相关研究中，最早出提出的最紧致片段的定义LCA(Lowest Common Ancestor)，LCA指在XML文档树中，包含所有查询关键字节点的最近公共祖先节点，该节点的任意子节点都不再包含所有的关键字节点。在LCA的基础上，又相继提出了Smallest LCA(SLCA)、Valuable LCA(VLCA)、Meaningful LCA(MLCA)等概念来提高XML关键字查询的性能和准确率。
SLCA是在LCA的基础上改进而来的，基本思想是，如果XML文档树节点v已包含所有的关键字，那么v的祖先节点的相关度肯定是较低的。即，SLCA给出了一个最小树，该树包含了所有的关键字，且该树的任一子树都不完全包含所有关键字。
VLCA包含满足如下条件的节点：如果一个XML节点包含至少一个关键字匹配，并且它的子节点都没有包含关键字的匹配，则称该节点为一个VLCA节点。
MLCA是在LCA求解完成以后，通过排除相关度较低的LCA而得到的。
SLCA、VLCA、MLCA等的引入，相对于简单的LCA求解，提高了XML关键字查询的性能和准确率。其中，对SLCA的研究相对较多，SLCA的发展也较为成熟，被认为是最好的最紧致片段的定义，本文将围绕SLCA展开。
在获取了所有包含给定关键字的最紧致片段后，另一个重要的问题就是XML片段相似程度的计算。由于XML片段具有结构信息，使得针对它的相似性计算可以考虑传统的相似性计算方法，即可以通过用户对于结果的反馈来进一步计算符合用户意图的最终结果。而对于结构信息的计算，很多算法引入了传统信息检索(Information Retrieval，IR)的思路，其代表有Xrank、Xseek等。
(1) XRANK是最早将XML文档的分层和超级链接结构、关键字二维接近 的概念考虑进来的XML检索系统，其设计目标是为用户提供类似Google的基于超链接的HTML搜索引擎，并且支持HTML和XML混合文档查询。
(2) XSeek区分代表实体的节点和代表属性的节点，并返回与关键字匹配的实体节点。
1.4论文主要研究内容
XML关键字查询不需要用户掌握复杂的查询语言和XIVIL文档结构，方便 普通用户使用，是XML查询中值得进一步深入探讨的方向。
XML关键字查询的基本问题是获得所有满足关键字组合语义的最紧致片段，根据目前的研究，对最紧致片段的定义最好的是SLCA，本文便是围绕SLCA展开的。
本文针对SLCA对索引查找有效算法进行研究，通过将算法逐步展开得出相应的可实现的查询程序。并对实际文档进行操作，将XML文档通过解析程序解析为倒排表的形式，进而生成相应的数据库，整个查询系统由JAVA代码实现。
1.5论文组织结构
本文设计开发一个关键字查询系统，主要完成查询关键字最低最小公共祖先的功能。本文的核心代码为Indexed Lookup Eager算法。根据用户输入的关键字有效的计算关键字的SLCA。
本论文一共包括五章内容，内容包括：绪论、相关技术介绍、Index Lookup Eager算法原理与实现、关键字SLCA查询系统的实现、软件测试，具体如下：
（1）第1章为绪论。该说明了本文的研究背景与研究意义，并对目前国内外研究现状做了概要总结，概括了本文的内容和主要创新之后，列出了全文的组织结构。
（2）第2章为相关技术介绍。该章主要包括对系统开发环境和开发工具的选择和介绍，这些技术是本系统开发的前提和保障。
（3）第3章为Index Lookup Eager算法原理与实现。为ILE算法的理论基础和编程实现。主要是对ILE算法的理论知识和编程的具体实现了具体的介绍。详细说明了程序中关于ILE算法的几个主要函数的作用和原理。
（4）第4章为关键字SLCA查询系统的实现。该章主要包括系统实现过程中数据库的实现，开发环境的配置以及主页面的设计和实现方法。在本章中实现了对整个系统的设计与实现，由于本文的重心在于实现ILE算法，而系统则起到了辅助的作用，来帮助算法得到完善。
（5）第5章为软件测试。该章主要是通过对软件进行测试，发现其中可能存在的错误，这是软件开发中最重要的环节。
最后为结论，该部分是对系统的整个开发设计过程进行了总结，包括在系统开发中应用的一些技术以及系统设计尚存在的不足和对未来的展望。

第2章 相关技术介绍
2.1开发环境与开发工具
操作系统：Microsoft Windows XP Professional SP2
开发语言：Java
数 据 库：MySQL
开发工具：MyEclipse 10
JDK版本：jdk1.6.0_20
2.2 Java语言介绍
Java程序设计语言是SUN Microsystems公司开发的面向对象的程序设计语言，它用于一般商用程序开发和基于WWW的Internet程序交互两个目的。Java程序设计语言近年来得到普及的原因，主要是它的安全性和跨平台性两大特点。
Java分为三个体系JavaSE(Java2 Platform Standard Edition，java平台标准版)，JavaEE(Java 2 Platform ,Enterprise Edition，java平台企业版)，JavaME(Java 2 Platform Micro Edition，java平台微型版)。
Java SE（Java Platform，Standard Edition）。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境和实时环境中使用的 Java 应用程序。Java SE 包含了支持 Java Web 服务开发的类，并为 Java Platform，Enterprise Edition（Java EE）提供基础。
Java EE（Java Platform，Enterprise Edition）。这个版本以前称为 J2EE。企业版本帮助开发和部署可移植、健壮、可伸缩且安全的服务器端 Java 应用程序。Java EE 是在 Java SE 的基础上构建的，它提供 Web 服务、组件模型、管理和通信 API，可以用来实现企业级的面向服务体系结构（service-oriented architecture，SOA）和 Web 2.0 应用程序。
Java ME（Java Platform，Micro Edition）。这个版本以前称为 J2ME。Java ME 为在移动设备和嵌入式设备（比如手机、PDA、电视机顶盒和打印机）上运行的应用程序提供一个健壮且灵活的环境。Java ME 包括灵活的用户界面、健壮的安全模型、许多内置的网络协议以及对可以动态下载的连网和离线应用程序的丰富支持。基于 Java ME 规范的应用程序只需编写一次，就可以用于许多设备，而且可以利用每个设备的本机功能。
Java语言具有简单的，面向对象的，分布式的，解释型的，健壮安全的，结构中立的，可移植的，性能优异、多线程的特性。它的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。
2.3 MyEclipse介绍
MyEclipse企业级工作平台（MyEclipse Enterprise Workbench ，简称MyEclipse）是对EclipseIDE的扩展，利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的JavaEE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML ,Struts ,JSP ,CSS ,Javascript ,Spring ,SQL ,Hibernate。
MyEclipse 是一个十分优秀的用于开发Java, J2EE的 Eclipse 插件集合，MyEclipse的功能非常强大，支持也十分广泛，尤其是对各种开源产品的支持十分不错。MyEclipse目前支持Java Servlet ,AJAX, JSP, JSF, Struts,Spring, Hibernate,EJB3,JDBC数据库链接工具等多项功能。可以说MyEclipse几乎囊括了目前所有主流开源产品的专属eclipse开发工具。
2.4 MySQL介绍
SQL(Structured Query Language)，结构化查询语言。SQL语言的主要功能就是同各种数据库建立联系，进行沟通。按照美国国家标准协会的规定，SQL被作为关系型数据库管理系统的标准语言。SQL语句可以用来执行各种各样的操作，例如更新数据库中的数据，从数据库中提取数据等。绝大多数流行的关系型数据库管理系统都采用了SQL语言标准。虽然很多数据库都对SQL语句进行了再开发和扩展，但是包括Select, Insert, Update, Delete, Create,以及Drop在内的标准的SQL命令仍然可以被用来完成几乎所有的数据库操作。
MySQL是一个开放源码的小型关联式数据库管理系统，开发者为瑞典MySQL AB公司。目前MySQL被广泛地应用在Internet上的中小型网站中。由于其体积小、速度快、总体拥有成本低，尤其是开放源码这一特点，许多中小型网站为了降低网站总体拥有成本而选择了MySQL作为网站数据库。
MySQL是一种关联数据库管理系统，关联数据库将数据保存在不同的表中，而不是将所有数据放在一个大仓库内，这样就增加了速度并提高了灵活性。MySQL的SQL语言是用于访问数据库的最常用标准化语言。
2.5 JDK介绍
JDK(Java Development Kit)是Sun Microsystems针对Java开发的产品。自从Java推出以来，JDK已经成为使用最广泛的Java SDK。JDK 是整个Java的核心，包括了Java运行环境，Java工具和Java基础的类库。JDK是学好Java的第一步。而专门运行在x86平台的Jrocket在服务器端运行效率也要比Sun JDK好很多。从SUN的JDK5.0开始,提供了泛型等非常实用的功能，其版本也不断更新，运行效率得到了非常大的提高。
JDK包含的基本组件包括：
javac – 编译器，将源程序转成字节码。
jar – 打包工具，将相关的类文件打包成一个文件。
javadoc – 文档生成器，从源码注释中提取文档。
jdb – debugger，查错工具。
java – 运行编译后的java程序（.class后缀的）。
appletviewer：小程序浏览器，一种执行HTML文件上的Java小程序的Java浏览器。
Javah：产生可以调用Java过程的C过程，或建立能被Java程序调用的C过程的头文件。
Javap：Java反汇编器，显示编译类文件中的可访问功能和数据，同时显示字节代码含义。
Jconsole: Java进行系统调试和监控的工具。
常用的package包括：
java.lang：这个是系统的基础类，比如String等都是这里面的，这个package是唯一一个可以不用import就可以使用的Package。
java.io: 这里面是所有输入输出有关的类，比如文件操作等。
：这里面是与网络有关的类，比如URL,URLConnection等。
java.util : 这个是系统辅助类，特别是集合类Collection,List,Map等。
java.sql: 这个是数据库操作的类，包括Connection, Statement，ResultSet等。
javax.servlet: 这个是JSP,Servlet等使用到的类。
2.6本章小结
本章介绍了本系统的开发环境。主要介绍了其中使用的主要开发工具和技术。选择MySQL做后台数据库管理系统，是因为它能够在windows XP系统下稳定运行、安全可靠，且与MyEclipse兼容性好。Java语言在MyEclipse下，使用快捷，易于上手。

第3章 Index Lookup Eager算法原理与实现
3.1 最紧致片段及SLCA相关概念
对于XML关键字查询来说，基本操作就是找到包含给定关键字的最紧致片段。目前对包含所有关键字节点的最紧致片段的描述中，SLCA最为成熟，基于 SLCA的XML关键字查询在查询性能和准确度上有较好的表现。本章将详细介绍XML关键字查询中最紧致片段及SLCA的相关概念，为后面的研究打下基础。首先，给出XML数据及XML文档树的定义。
3.1.1XML数据及其树结构
XML（Extensible Markup Language)即可扩展标记语言，与HTML一样，都是 SGML(Standard Generalized Markup Language，标准通用标记语言)的子集。XML是Internet环境中跨平台的，依赖于内容的技术，是当前处理结构化文档信息的有力工具，在Web服务、电子商务等诸多网络相关应用领域已被广泛使用，成为目前网络数据交换和表示事实上的标准。
符合XML规范的数据称作XML数据，XML规范规定了XML数据必须满足的条件。XML数据有两个基本特点：一是自描述，XML数据本身就已经包含了元数据——关于数据本身的信息，表现为不同语义的标记(例如元素、属性等等)。在所有标记中，元素标记最为重要。一个元素标记由两个起、止标签构成，起止标签所含的文本就是对应的语义单元：二是半结构化，即不同于传统关系数据库(传统的数据库都有一定的数据模型，可以根据模型来具体描述特定的数据)，XML数据的结构限制并不严格，表现为语义单元相互嵌套的层次关系。
XML数据内容的限制通常由XML模式来描述。常用的模式包括DTD和 XML Schema。文档类型定义DTD(Document Type Definition)是一种保证 XML文档格式正确的有效方法，可以通过比较XML文档和DTD文件来看文档是否符合规范，元素和标签使用是否正确。而XML SChema具有比DTD更强的描述性，能够更好的验证XML文件逻辑结构的正确性。
XML数据的基本形式为XML文档。 一个XML文档通常由5部分组成：声明、元素、注释、字符引用和处理指令，图3．1即为一个实际的XML文档的示例

<?xml version=”1．0”encoding=”UIF一8”?>
<proceedings>
<issue>
<articles>
<article>
<title>bibliography On data design<／title>
<authors>
<author position=0>Karen Botnich</author>
<／authors>
<／article>
<article>
<title>face recognition<／title>
<authors>
<author position=O>Cola Cohen<／author>
<／authors>
<／article>
<／articles>
<publisher>
<year>2003<／year>
<address>
<country>Germany<／country>
<／address>
<／publisher>
<／issue>
<／proceedings>
图3．1 XML文档举例
在实际处理XML数据时，更为常见的是XML标签有向图模型，由XPath 规范描述。通常简化为XML标签有向树模型，G=(V，E，r，A)，其中的V表示G中所有节点的集合，E表示G中所有边的集合，r表示G的根节点，A是所有节点所带标签的集合。图2．2即为图2．1中XML文档对应的XML文档树。

Root

Element

Attribute

Text

String value

proceedings

issue

article publisher

title authors year address

title authors title author 2003 country

Bibliography author face author Germary
On data recognition
design

Karen position Cola position
Botnich Cohen

图3.2XML文档树
3.1.2最紧致片段相关概念
在XML关键字查询中，用户只需输入查询关键字便能得到期望的结果，这就涉及一个重要的问题：如何根据查询关键字定义查询结果。为此，提出最紧致片段的概念，最紧致片段指在XML文档树中，满足所有查询关键字组合语义的最小树片段，这样，XML关键字查询问题便转化为查找所有最紧致片段的问题。
最早的最紧致片段定义是LCA(Lowest Common Ancestor)。LCA是图论中经常使用的一个概念，指在有向图中，两个节点的最近公共祖先节点。在将LCA的概念引入XML关键字查询中时，LCA指所有包含查询关键字的节点的最近公共祖先。为给出LCA的准确定义，首先明确XML树中的一些概念。
在XML树中，我们用v表示一个节点。对于任意节点v，用l(v)表示该节点 的标签信息。对于任意节点u、v，uv(uv)表示u是v的祖先(后代)，uv表示uv或者u=v。u<v(u>v)表示在XML树前序遍历中，u的序列在v之前 (之后)，但u并不是v的祖先(后代)。
下面，给出LCA的准确定义：
给定查询关键字集合K={,,．．． }及待查询关键字文档D，表示D中直接包含关键字岛的节点集合。
定义3.1：LCA，在XML文档D中，给定m个节点，，．．．，如果对于1≤i≤m，节点v是的祖先，且不存在节点u，vu，u也是所有的祖先，则我们称v是这历个节点的一个LCA，记做 V=LCA(，，．．．，)。
定义3.2：LCASet，给定查询关键字集合K={,,．．． }及待查询XML文档D，在D上关于K的LCASet定义为 LCASet=LCA(，，…)={ |=LCA（,,…），∈ (1≤i≤m)}。
例如，在图2．3中，用户希望查询题目中包