2016, Vol. 37
随着网络技术的快速发展，XML已经成为Web中数据表示和转换的标准，XML查询技术也就成为信息检索领域中一个重要的研究课题.XML关键字查询是一种用户友好的查询方式，用户只需要提交一个或者几个关键字信息即可得到相关的检索结果.基于XML数据模型，研究者们提出了许多关键字查询语义和方法，例如SLCA,XRank等[1-2]，其中SLCA(最小最低公共祖先)语义得到了学术界的广泛关注.
不精确性和不确定性广泛存在于许多Web应用中，例如信息整合、信息提取和Web数据过滤等，而XML数据模型的柔性特点可以很好地表达不精确和不确定数据[3].考虑到现实世界事物中的不确定性特征，许多研究者对概率XML数据进行了研究，设计和分析了概率XML数据模型[4].基于概率XML数据模型，一些研究者们提出了概率XML数据上的关键字查询方法，文献[5]提出一个更加广泛的概率XML数据模型PrXML{exp,ind,mux}来表达数据间的概率分布关系，给出了得到SLCA节点的相关算法，通过使用子树的关键字分布概率表kdptabs来计算点积、笛卡尔积等运算，并得出相关的概率值计算结果.
基于模糊XML数据模型，现有的研究成果主要集中在模糊XML结构查询方面[6-8].文献[6]基于模糊XML数据模型[3]提出了能处理包含复合谓词AND,NOT，OR的LTwig算法，该算法可以仅对与查询相关的数据流进行一次扫描得出相应小枝查询的结果.文献[7]提出了一种针对模糊XML文档的动态编码方案,设计了在动态环境中进行小枝查询匹配的算法DQTwig.而对于模糊XML数据的关键字查询方法的研究目前未见有报道，仅对模糊XML数据的结构查询研究很难满足非专业用户的查询需求.如何处理在模糊XML环境下的关键字查询成为亟需解决的问题，为此本文将重点研究如何针对模糊XML数据进行关键字查询.
1 模糊XML数据模型传统XML文档一般被表示为一个有向树结构，即T=(V,E)，其中，V表示节点的集合，E表示边的集合.对于一棵XML结构树t，V(t)表示树中所有节点的集合，E(t)表示树中所有边的集合，可知，E(t)∈V(t)×V(t).对于任意v∈V有一个唯一的标签Label(v).若一棵XML树T′是树T的子树，则满足以下条件: V(T′)⊆V(T)，E(T′)⊆E(T).
对于表示模糊数据信息的模糊XML结构模型，同样被定义为一个树形结构Tfuzzy，通过引入模糊集和可能性分布理论来表示和处理模糊信息[3].在XML中采用两种模糊类型，一种是将元素节点与隶属度结合来表达元素的模糊度，另一种是将可能性分布与元素节点的属性值相结合来表达属性的各个可能值的模糊度.对于可能性分布，存在两种类型，分别为析取(disjunctive)可能性分布和合取(conjunctive)可能性分布.为表达元素的隶属度，在模型中引入一个可能性属性，用Poss表示，它在[0,1]之间取值.可能性属性Poss与一个模糊结构体Val一起来表示在XML文档中给定元素的可能性大小.如图 1中的模糊XML树形结构和图 2中的模糊XML文档所示(图 1是图 2中部分XML文档的树形结构).图 2中第2行＜Val Poss = “0.8”＞表示部门department为Computer Science的可能性为0.8.而对于隶属度值为1的元素节点，它的隶属度的表达＜Val Poss = “1”>和＜/Val＞将被忽略.为了表达元素属性值的可能性分布，在XML模型中采用一个模糊结构体Dist来表示属性的各个值的可能性分布，一个Dist元素可以有多个Val元素作为孩子节点，每个Val节点关联一种可能性，Dist需对可能性分布类型(析取或者合取)加以说明.例如在图 2中，第5～18行是一个析取结构体Dist关联于元素teacher信息的可能性分布.它包含两个Val节点关联教师John Smith的两种可能性信息及其隶属度值.一种可能性信息为他的职称是教授，可能性值为0.9；另一种可能性信息为他的职称是副教授，可能性值为0.7.
|
图 1 模糊XML树形结构 Fig.1 The tree structure of fuzzy XML |
|
图 2 部分模糊XML文档片段 Fig.2 Partial fuzzy XML document fragment |
传统XML文档的关键字查询语义大多基于SLCA [1]语义进行研究.考虑对图 1中的XML文档片段进行SLCA关键字语义查询，若输入关键字{John Smith,Associate professor}，得到的SLCA结果是Val节点，此节点是模糊节点，不是一般的节点，不能作为查询结果返回.可知对模糊XML文档运用传统的关键字查询语义会导致错误.
另外由于模糊XML模型中引入了模糊集和可能性分布理论，体现出元素的存在可能性(隶属度)大小，以及属性值的可能性分布及其隶属度大小.
因而关键字查询的SLCA结果的可能性大小成为一项重要的指标，如何确定和计算查询结果的可能性值(整体可能性)λ便成为模糊XML文档上的关键字查询需要研究的重要问题.
定义1 给定一组关键字集合｛m1,m2,…,mn｝和一个模糊XML文档T，对T进行SLCA语义的关键字查询，即得出包含全部关键字｛m1,m2,…,mn｝的SLCA结果Rk及其可能性值{(R1,λ1),(R2,λ2),…,(Rk,λk)}，并且SLCA结果节点Ri(1≤i≤k)为一般节点.
对于一个SLCA节点的可能性值，记为Pwslca(v).由于模糊XML模型的特点，Pwslca(v)可以通过式(1)得出：
|
(1) |
式中，P(pathr→v)中，r是根节点，整个式子表示从根节点r到节点v路径中，节点v的存在可能性大小.假设从根节点r到节点v路径上的隶属度分布为｛1,0.8,0.5,0.6｝，则P(pathr→v)=1×0.8×0.5×0.6 = 0.24.PLslca(v)表示在以节点v为根节点的子树结构Tsub(v)中，节点v的本地可能性大小.假设以节点v为根节点的子树结构Tsub(v)中,节点v到包含关键字的节点的隶属度分布为｛0.9，0.6，0.8｝，那么PLslca(v)=0.9×0.6×0.8=0.432.故Pwslca(v)=0.24×0.432=0.104.
2.2 节点编码普通XML关键字查询处理普遍采用Dewey编码,对于模糊XML文档，Dewey编码不能将模糊节点和一般节点进行相应的区分，难以断定参与查询的节点的类型，为了更好地对模糊文档进行关键字查询，对Dewey编码进行相应的扩展以更好地适应模糊XML关键字查询.首先对模糊XML文档进行一般的Dewey编码，当遇到模糊节点Dist,Val时，采取在其节点编码的最后组成部分前添加字符“F”来表示此节点是模糊节点.相应的编码实例如图 1所示.将这种编码方式定义为CDewey.
3 模糊XML关键字查询 3.1 索引为了在模糊XML文档上面进行关键字查询，构建了3个索引，一个是记录包含各个关键字｛m1,m2,…,mn｝的节点列表｛M1,M2,…,Mn｝.模糊XML文档中与节点s相关的隶属度分布采用两个索引记录，一个是记录以节点s为根节点的子树中包含关键字的节点的隶属度分布，记为LL.图 3是简化的模糊XML 文档树形结构，其中模糊节点用矩形表示(Dist和Val的组合合并为一个模糊节点)，一般节点用椭圆表示，将元素以及属性值的隶属度大小标记在连接该节点与其父节点的边E上，未标记隶属度的边表示连接其两端的节点中孩子节点相对父节点的隶属度值默认为1.假设关键字为B2，E3，其SLCA结果节点是C1，对于LL将记录｛D(C1)：0.8，1，0.9，1｝,D(C1)是C1的CDewey编码，即包含关键字的节点到节点C1路径上的隶属度分布.此索引可用来计算节点C1的本地可能性值.用另一列表索引LE来记录节点s到根节点的路径上的隶属度分布，例如节点C1，它到根节点的隶属度值为｛0.7，1｝，故将｛D(C1)：0.7，1｝存放在索引LE中.索引LE可用来计算节点s的存在可能性值.
|
图 3 简化的模糊XML树形结构 Fig.3 A simplified tree structure of fuzzy XML |
模糊XML关键字查询不仅需要找出符合查询要求的一般SLCA结果节点，而且还需要计算其相应的可能性值.为此，提出算法FIndex Loop(见算法1)，首先按照传统SLCA语义对输入的关键字进行初步搜索产生结果集Sq，采用文献[1]中提出的基于get_slca( )的算法得到结果集Sq，对于Sq中的节点s，如果它是模糊节点，它的父节点P(s)是一般节点，将P(s)及其相关隶属度分布记录到列表LE中，P(s)作为结果节点输出.如果它的父节点P(s)仍然为模糊节点，向上寻找s的祖先节点，当Ancestor(s)为一般节点时，将Ancestor(s)及其相关隶属度分布记录到列表LE中，并作为结果节点输出.对于Sq中的一般节点，直接作为结果节点输出，执行Compute Possibility(s)功能(见算法2)，最后返回SLCA结果及其相应的可能性值.
算法1 FIndex Loop
输入：关键字集合｛m1,m2,…,mn｝，一个已编码的模糊XML数据树T.
输出：关键字查询的SLCA结果及其可能性值{(R1,λ1),(R2,λ2),…,(Rk,λk)}.
1) 下载和访问关键字节点列表M=｛Mi｝，1≤i≤n，创建和更新列表LE{u:σ};
2) 求解包含所有关键字｛m1,m2,…,mn｝的SLCA结果，即Sq=slca(m1,m2,…,mn)；
3) for 每个候选结果节点s∈Sq；
4) if s是模糊节点，find P(s)；//P(s)是s的父节点；
5) 当P(s)是一般节点时，将节点P(s)的记录更新到列表LE{P(s):σ}；
6) 当P(s)是模糊节点时，寻找s的祖先节点Ancestor(s)；
7) 当Ancestor(s)是一般节点时，将节点Ancestor(s)的记录更新到列表LE{Ancestor(s):σ}；
8) else s是一般节点,将s的记录更新到列表LE{s:σ};
9) 执行Compute Possibility(s)功能；
10) Return (Ri,λi).//返回SLCA结果及其可能性值.
算法2是计算SLCA结果的可能性值的一个功能模块.首先访问关键字节点列表M，取列表M中的最小编码的节点u，初始化一个栈stack，把u的编码压入栈stack中，取M中剩余节点最小编码的节点u′，计算节点u和u′的最长公共前缀LCP(longest common prefix)，如果LCP的长度小于栈列stack中节点u编码长度，可知节点u′与节点u不存在祖先后代关系，取结果集Ri中的最小编码节点R，得出节点u，u′与R的LCP，如果LCP(u,u′,R)≠CDewey(R)，则说明u和u′不是节点R的后代节点，将栈stack中除去LCP(stack,u′)的剩余部分弹出；如果LCP(u,u′,R)=CDewey(R)，则表明u和u′是节点R的后代节点，记录节点u和u′在列表LE{u:σ}的索引条目，将栈stack中除去LCP(stack,u′)的剩余部分弹出；当节点u和u′存在祖先后代关系时，如果LCP(stack,R)=CDewey(R)，那么u和u′是节点R的后代节点，记录节点u和u′在列表LE{u:σ}的索引条目；访问节点u′后，将D(u′)中除去LCP(stack, u′)的剩余部分压入栈并继续处理列表M中的下个节点.当结果节点R的子树中的所有包含关键字的节点及其在列表LE{u:σ}的索引条目找到时，可以得到LL{R:ξ}.重复过程4)～10),依次得出结果集｛R1,R2,…,Rk｝中Ri(1≤i≤k)的索引列表LL{Ri:ξ}.访问相关索引分别求得结果节点的本地可能性值PLslca(Ri)和存在可能性值P(pathr→Ri)，计算结果节点Ri的可能性值,最后输出所有结果及其可能性值.
算法2 Compute Possibility(s)
输入：SLCA结果集｛R1,R2,…,Rk｝.
输出：SLCA结果及其可能性值{(R1,λ1),(R2,λ2),…,(Rk,λk)}.
1) 访问关键字节点列表M=｛Mi｝，1≤i≤n,SLCA结果集｛R1,R2,…,Rk｝,创建和更新列表LE{Ri:σ};
2) 从列表M的最小CDewey编码节点u开始访问；
3) 初始化一个栈stack，将CDewey(u)设为初始值；
4) 取列表M中下一个最小编码节点，u′=GetNextNode(M)；
5) 计算节点u和u′的最长公共前缀f =LCP (stack, u′)；
6) 当stack.size > LCP.length时，If LCP(u,u′,R)≠CDewey (R)，pop entry()；// R是SLCA结果集中的最小编码节点；
7) If LCP(u,u′,R) = CDewey(R),记录节点u,u′在列表LE中的条目，and pop entry()；
8) 当stack.size = LCP.length时，If LCP(stack,R)=CDewey(R),记录节点u,u′在列表LE中的条目；
9) for(f＜j≤u′.length) stack.push(u[j])；
10) 当得到节点R的子树中的所有的关键字节点在列表LE的记录时，创建列表LL{R:ξ}.
11) 重复过程 4)～10),直到得到所有的结果节点Ri(1 ≤ i≤k)的列表 LL{Ri:ξ}；
12) 访问列表LL{Ri:ξ},计算节点Ri的本地可能性PLslca(Ri);
13) 访问列表LE{Ri:σ},计算节点Ri的存在可能性P(pathr→Ri);
14) λ=PLslca(Ri)×P(pathr→Ri)；//计算节点Ri的可能性值;
15) Return (Ri,λi).
4 实验与分析对每个关键字查询构建相应的结构查询语句，采用LTwig算法[6]求解出输入关键字查询的相应的结构查询结果.LTwig是一个能够有效求解在模糊XML 数据上面的小枝查询结果的算法，将结构查询得出的结果作为准确结果，对比FIndex Loop算法的查全率和查准率.
4.1 数据集和实验环境设置实验数据集采用合成的XML数据集XMark，随机生成大小30MB的XMark数据集，并采用文献[8]中使用的随机模糊信息产生方法将原始的XMark数据集转换为模糊XML数据集，记为FXM.所有实验测试均在Inter(R) Core(TM) i3CPU @ 2.13 GHz处理器，2 GB RAM和内置320 GB硬盘的Windows 7系统下进行.查询关键字见表 1.
|
表 1 关键字查询示例 Table 1 Keyword query examples |
对于一个关键字查询，将其相应构建的结构查询通过LTwig算法得出的结果作为准确结果，记为AR(accurate result)，通过FIndex Loop算法得出的结果作为近似结果，记为PR(approximate result)，则查全率Recall=|AR∩PR| / |AR|，查准率Precision=|AR∩PR| / |PR|.在模糊数据集FXM上面对 Q1～Q10的关键字查询进行查全率和查准率测试，如图 4所示.实验结果表明FIndex Loop具有较高的查全率和查准率.
|
图 4 FIndex Loop算法的查全率和查准率 Fig.4 Recall and precision of FIndex Loop algorithm |
本文针对模糊XML数据模型下的关键字查询方法进行了研究.首先研究并提出了模糊XML的关键字查询语义，设计了一种新型编码方法CDewey.在此基础上，提出了模糊XML关键字查询算法FIndex Loop，实现对模糊XML文档的关键字语义查询及其SLCA结果可能性值的计算.最后通过实验验证所提方法的有效性.未来工作将集中在对相关算法的优化，以及对查询结果的排序处理等领域.
| [1] |
Xu Y,Papakonstantinou Y.Efficient keyword search for smallest LCAs in XML databases[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data.Baltimore:ACM,2005:527-538. ( 0)
|
| [2] |
Guo L,Shao F,Botev C,et al.XRANK:ranked keyword search over XML documents[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data.San Diego:ACM,2003:16-27. (0)
|
| [3] |
Ma Z M, Yan L. Fuzzy XML data modeling with the UML and relational data models[J].
Data & Knowledge Engineering, 2007, 63 : 972 –996.
(0)
|
| [4] |
Nierman A,Jagadish H V.ProTDB:probabilistic data in XML[C]// Proceedings of the 28th International Conference on Very Large Data Bases.Hong Kong:VLDB Endowment,2002:646-657. (0)
|
| [5] |
Zhang C J, Chang L, Sha C F, et al.
Keywords filtering over probabilistic XML data[M]. Berlin: Springer-Verlag, 2012 : 183 -194.
(0)
|
| [6] |
Liu J, Ma Z M, Ma R Z. Efficient processing of twig query with compound predicates in fuzzy XML[J].
Fuzzy Sets and Systems, 2013, 229 : 33 –53.
(0)
|
| [7] |
Liu J, Ma Z M, Qu Q L. Dynamically querying possibilistic XML data[J].
Information Sciences, 2014, 261 : 70 –88.
(0)
|
| [8] |
Liu J,Ma Z M,Yan L.Efficient processing of twig pattern matching in fuzzy XML[C]// Proceedings of the 18th ACM Conference on Information and Knowledge Management.Hong Kong:ACM,2009:117-126. (0)
|