第3章 Index Lookup Eager算法原理与实现
成:声明、元素、注释、字符引用和处理指令,图3.1即为一个实际的XML文档的示例
11
燕山大学本科生毕业设计(论文)
图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
publisher issue article title authors year title authors title author 2003 Bibliography author face author On data recognition design
Karen position Cola position Botnich Cohen
图3.2XML文档树
address country Germary
3.1.2最紧致片段相关概念
在XML关键字查询中,用户只需输入查询关键字便能得到期望的结果,
12
第3章 Index Lookup Eager算法原理与实现
这就涉及一个重要的问题:如何根据查询关键字定义查询结果。为此,提出最紧致片段的概念,最紧致片段指在XML文档树中,满足所有查询关键字组合语义的最小树片段,这样,XML关键字查询问题便转化为查找所有最紧致片段的问题。
最早的最紧致片段定义是LCA(Lowest Common Ancestor)。LCA是图论中经常使用的一个概念,指在有向图中,两个节点的最近公共祖先节点。在将LCA的概念引入XML关键字查询中时,LCA指所有包含查询关键字的节点的最近公共祖先。为给出LCA的准确定义,首先明确XML树中的一些概念。
在XML树中,我们用v表示一个节点。对于任意节点v,用l(v)表示该节点 的标签信息。对于任意节点u、v,u?v(u?v)表示u是v的祖先(后代),u?v表示u?v或者u=v。u
下面,给出LCA的准确定义:
给定查询关键字集合K={k1,k2,...km }及待查询关键字文档D,L1表示D中直接包含关键字岛的节点集合。
定义3.1:LCA,在XML文档D中,给定m个节点n1,n2,...,nm如
果对于?1≤i≤m,节点v是ni的祖先,且不存在节点u,v?u,u也是所有ni的祖先,则我们称v是这历个节点的一个LCA,记做 V=LCA(n1,n2,...,nm)。
定义3.2:LCASet,给定查询关键字集合K={k1,k2,...km }及待查询
XML文档D,在D上关于K的LCASet定义为 LCASet=LCA(L1,,vi∈Li (1≤i≤m)}。 L2,?Lm)={ v|v=LCA(v1,v2,?vm)
例如,在图2.3中,用户希望查询题目中包含“IR”并且作者中有“John”的文章,则输入的关键字集合为{“IR”,“John”},根据LCA的定义,节点paper(15) 是这两个关键字的一个LCA,所以paper(15)是查询的一个输出。
LCA是XML关键字查询中最紧致片段的基础定义,在LCA的基础上,
13
燕山大学本科生毕业设计(论文)
相继又提出了Smallest LCA(SLCA)、Valuable LCA(VLCA)、Meaningful LCA MLCA)等概念来提高XML关键字查询的性能和准确率。其中,对SLCA的研究相对较多,SLCA的发展也较为成熟,被认为是目前最好的最紧致片段的定义。
3.1.3 SLCA概念详述
LCA给出了XML关键字查询中最紧致片段的定义,但是LCA的概念过于
简单,查询准确率较低。
产生该问题的原因在于结果集中的某些LCA节点是另一些LCA节点的祖先节点,这些祖先节点与查询关键字之间的相关度明显较低。为了解决这一问题,文献提出了SLCA(Smallest—LCA)的概念。
SLCA的基本思想是:如果XML文档树中节点v已包含所有的查询关键字,那么v的祖先节点的相关度肯定是较低的。即,SLCA给出一个最小树,该树包含了所有的关键字,且该树的任一子树都不完全包含所有关键字。因此,SLCA的问题就是求解XML文档树中所有满足如下条件的子树的根节点:(1)子树必须包含所有关键字序列,关键字序列中的任一关键字必然分布于该子树的叶节点;(2)子树中不存在更小的子树同样包含所有的关键字。下面,给出SLCA的准确定义:
定义3.3:SLCA,在XML文档D中,给定查询关键字集合
K={k1,k2,...km }, 节点y∈LCASet。如果,不存在节点u,v?u,u∈LCASet,则称v是关于查询关键字集合的一个SLCA。 定义3.4:SLCASet,给定查询关键字集合K={k1,k2,...km}及待查
询XML文档D,在D上关于K的SLCASet定义为:SLCASet=SLCA(L1,L2,?Lm)={v|v=LCA(L1,L2,?Lm),
??u |v?u,u∈LCA(L1,L2,?Lm)}
例如在图2.3中,尽管在查询关键字集合{“John”,“Ben”}下conf(2) ∈LCASet,但conf(2)并不在SLCASet中,因为paper(15) ∈LCASet并且conf(2) ?paper(15)。因此,该查询的输出为SLCASet=-{paper(12),
14
相关推荐: