第3章 Index Lookup Eager算法原理与实现
成：声明、元素、注释、字符引用和处理指令，图3．1即为一个实际的XML文档的示例
bibliography On data design<／title> <authors> </p><p> <author position=0>Karen Botnich</author> <／authors> <／article> <article> </p><p> <title>face recognition<／title> <authors> </p><p> <author position=O>Cola Cohen<／author> <／authors> <／article> <／articles> <publisher> </p><p> <year>2003<／year> <address> </p><p> <country>Germany<／country> <／address> <／publisher> <／issue> <／proceedings> </p><p> </p><p>11 </p><p> </p><p>燕山大学本科生毕业设计（论文） </p><p>图3．1 XML文档举例 </p><p>在实际处理XML数据时，更为常见的是XML标签有向图模型，由XPath 规范描述。通常简化为XML标签有向树模型，G=(V，E，r，A)，其中的V表示G中所有节点的集合，E表示G中所有边的集合，r表示G的根节点，A是所有节点所带标签的集合。图2．2即为图2．1中XML文档对应的XML文档树。 </p><p> </p><p>Root Element Attribute Text String value proceedings </p><p> </p><p> publisher issue article title authors year title authors title author 2003 Bibliography author face author On data recognition design </p><p> Karen position Cola position Botnich Cohen </p><p>图3.2XML文档树 </p><p> address country Germary </p><p>3.1.2最紧致片段相关概念 </p><p>在XML关键字查询中，用户只需输入查询关键字便能得到期望的结果，</p><p> </p><p>12 </p><p> </p><p>第3章 Index Lookup Eager算法原理与实现 </p><p>这就涉及一个重要的问题：如何根据查询关键字定义查询结果。为此，提出最紧致片段的概念，最紧致片段指在XML文档树中，满足所有查询关键字组合语义的最小树片段，这样，XML关键字查询问题便转化为查找所有最紧致片段的问题。 </p><p>最早的最紧致片段定义是LCA(Lowest Common Ancestor)。LCA是图论中经常使用的一个概念，指在有向图中，两个节点的最近公共祖先节点。在将LCA的概念引入XML关键字查询中时，LCA指所有包含查询关键字的节点的最近公共祖先。为给出LCA的准确定义，首先明确XML树中的一些概念。 </p><p>在XML树中，我们用v表示一个节点。对于任意节点v，用l(v)表示该节点 的标签信息。对于任意节点u、v，u?v(u?v)表示u是v的祖先(后代)，u?v表示u?v或者u=v。u<v(u>v)表示在XML树前序遍历中，u的序列在v之前 (之后)，但u并不是v的祖先(后代)。 </p><p>下面，给出LCA的准确定义： </p><p>给定查询关键字集合K={k1,k2,．．．km }及待查询关键字文档D，L1表示D中直接包含关键字岛的节点集合。 </p><p>定义3.1：LCA，在XML文档D中，给定m个节点n1，n2，．．．，nm如</p><p>果对于?1≤i≤m，节点v是ni的祖先，且不存在节点u，v?u，u也是所有ni的祖先，则我们称v是这历个节点的一个LCA，记做 V=LCA(n1，n2，．．．，nm)。 </p><p>定义3.2：LCASet，给定查询关键字集合K={k1,k2,．．．km }及待查询</p><p>XML文档D，在D上关于K的LCASet定义为 LCASet=LCA(L1，，vi∈Li (1≤i≤m)}。 L2，?Lm)={ v|v=LCA（v1,v2,?vm）</p><p>例如，在图2．3中，用户希望查询题目中包含“IR”并且作者中有“John”的文章，则输入的关键字集合为{“IR”，“John”}，根据LCA的定义，节点paper(15) 是这两个关键字的一个LCA，所以paper(15)是查询的一个输出。 </p><p>LCA是XML关键字查询中最紧致片段的基础定义，在LCA的基础上，</p><p> </p><p>13 </p><p> </p><p>燕山大学本科生毕业设计（论文） </p><p>相继又提出了Smallest LCA（SLCA）、Valuable LCA(VLCA)、Meaningful LCA MLCA)等概念来提高XML关键字查询的性能和准确率。其中，对SLCA的研究相对较多，SLCA的发展也较为成熟，被认为是目前最好的最紧致片段的定义。 </p><p>3.1.3 SLCA概念详述 </p><p>LCA给出了XML关键字查询中最紧致片段的定义，但是LCA的概念过于 </p><p>简单，查询准确率较低。 </p><p>产生该问题的原因在于结果集中的某些LCA节点是另一些LCA节点的祖先节点，这些祖先节点与查询关键字之间的相关度明显较低。为了解决这一问题，文献提出了SLCA(Smallest—LCA)的概念。 </p><p>SLCA的基本思想是：如果XML文档树中节点v已包含所有的查询关键字，那么v的祖先节点的相关度肯定是较低的。即，SLCA给出一个最小树，该树包含了所有的关键字，且该树的任一子树都不完全包含所有关键字。因此，SLCA的问题就是求解XML文档树中所有满足如下条件的子树的根节点：(1)子树必须包含所有关键字序列，关键字序列中的任一关键字必然分布于该子树的叶节点；(2)子树中不存在更小的子树同样包含所有的关键字。下面，给出SLCA的准确定义： </p><p>定义3．3：SLCA，在XML文档D中，给定查询关键字集合</p><p>K={k1,k2,．．．km }， 节点y∈LCASet。如果，不存在节点u，v?u，u∈LCASet，则称v是关于查询关键字集合的一个SLCA。 定义3．4：SLCASet，给定查询关键字集合K={k1,k2,．．．km}及待查</p><p>询XML文档D，在D上关于K的SLCASet定义为：SLCASet=SLCA(L1，L2，?Lm)={v|v=LCA（L1，L2，?Lm），</p><p>??u |v?u，u∈LCA（L1，L2，?Lm）} </p><p>例如在图2．3中，尽管在查询关键字集合{“John”，“Ben”}下conf(2) ∈LCASet，但conf(2)并不在SLCASet中，因为paper(15) ∈LCASet并且conf(2) ?paper(15)。因此，该查询的输出为SLCASet=-{paper(12)，</p><p> </p><p>14 </p><p> </p><p></p><div class="page"><ul><li><a href=ythd_3ts4l33x1e8ojis8frem_1.html>1</a></li><li><a title=上一页 href=ythd_3ts4l33x1e8ojis8frem_5.html><<</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_3.html>3</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_4.html>4</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_5.html>5</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_6.html class="hover" >6</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_7.html>7</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_8.html>8</a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_9.html>9</a></li><li><a title=下一页 href=ythd_3ts4l33x1e8ojis8frem_7.html>>></a></li><li><a href=ythd_3ts4l33x1e8ojis8frem_13.html>13</a></li></ul></div>
<br />
<p><script type="text/javascript">s("content-m-bot");</script></p>
</div>
<div class="m-pages"></div>
<div class="down-word">
<div class="word-ico"></div>
<div class="word-tit">
<span class="docx">里仁学院论文模板2013.doc</span>
<span>将本文的Word文档下载到电脑</span>
<span><script type="text/javascript">s("content-m-down");</script></span>
</div>
<div class="word-pic"><a href="javascript:;">下载这篇word文档</a></div>
</div>
</article>
<div class="art-prenext">
搜索更多关于： <a class="title2" title="里仁学院论文模板2013" href="ys_sssfk1i1ytperlmk1zkypkfz01e01c01d01f_1.html">里仁学院论文模板2013</a> 的文档
</div>
<div class="main-tab"><a class="on" href="javascript:;">相关推荐</a></div>
<div class="tab-box">
<ul class="main-new on clearfix">
<li><a title="外科感染" href="ys_hlio29j6nkib_1.html">外科感染</a></li><li><a title="(优辅资源)人教版 小学二年级(上册)数学期末综合试卷及试题" href="ys_014fmgsclrwklu8015fjuk0pmko00wi6ni1yfikinop0n014feyg3w015k1ci1ykdbkdnp30glkrmdghjgjurmdu54_1.html">(优辅资源)人教版 小学二年级(上册)数学期末综合试卷及试题</a></li><li><a title="大众汽车管理信息系统 - 图文" href="ys_hlzfmflfhsbqof5mx2fs1j1roorp2700w01900wh6mk1z_1.html">大众汽车管理信息系统 - 图文</a></li><li><a title="高中数学第二章推理与证明2.1合情推理与演绎推理创新应用学案" href="ys_ul4ffxk1ci1yobwfiko9sjoomx2ff2rltk5q01e01a01dglkj45joomx2ff2lxwp1qjoomx2g7vk34iokn54i1yklk_1.html">高中数学第二章推理与证明2.1合情推理与演绎推理创新应用学案</a></li><li><a title="高中物理 第五章 曲线运动 第五节 向心" href="ys_ul4ffxmllmx200wobwfiso9s00wkc2p1bseogbs00wobwfisps200wgltiwz_1.html">高中物理 第五章 曲线运动 第五节 向心</a></li><li><a title="幼儿园教育活动设计与实践教案" href="ys_inwg1rh65k0ppf6lkrgbsrlqrkxff2i3is1hk0pklk_1.html">幼儿园教育活动设计与实践教案</a></li><li><a title="输血科建设与管理规范复习题" href="ys_sczqwwo29irerlqff2of5mx2r7opvnhl9fhcu54_1.html">输血科建设与管理规范复习题</a></li><li><a title="研究生教育" href="ys_npwo6un4vk0ppf6_1.html">研究生教育</a></li><li><a title="一个淘宝卖家的自白" href="ys_feoffulp4i3hggmi46nespnunel_1.html">一个淘宝卖家的自白</a></li><li><a title="生理学" href="ys_n4vmx2i1y_1.html">生理学</a></li>
</ul>
</div>
<div class="main-tab"><a class="on" href="javascript:;">相关阅读</a></div>
<div class="tab-box">
<ul class="main-new on clearfix">
<li><a title="璁＄畻鏈哄熀纭�璇曢(1--4绔犵粌涔犻) - 鐧惧害鏂囧簱" href=ythd_5e3381hijy2p7v440mc5_2.html>璁＄畻鏈哄熀纭�璇曢(1--4绔犵粌涔犻) - 鐧惧害鏂囧簱</a></li><li><a title="心血管内科诊断学试题" href=ythd_6cik221phy2cg5h8iu6u_2.html>心血管内科诊断学试题</a></li><li><a title="垦区粮食标准化复评报告模板（电气）" href=ythd_9gfg91qspm6gjog0oada_13.html>垦区粮食标准化复评报告模板（电气）</a></li><li><a title="国土政策宣讲会讲稿" href=ythd_3shtu9aect8uhsm07rq6_4.html>国土政策宣讲会讲稿</a></li><li><a title="里仁学院论文模板2013" href=ythd_3ts4l33x1e8ojis8frem_6.html>里仁学院论文模板2013</a></li><li><a title="xxxx国道改建实施施工组织设计" href=ythd_4vxep4wh2h1h1yk7prpg_10.html>xxxx国道改建实施施工组织设计</a></li><li><a title="园林绿化工程投标文件范本" href=ythd_0jm6e70ofx5uqa87qs3g_4.html>园林绿化工程投标文件范本</a></li><li><a title="中国古典园林史重点(复习资料)" href=ythd_8vfqb7ipu49o8y29wt5t6vudb8bhn000z66_1.html>中国古典园林史重点(复习资料)</a></li><li><a title="中国猕猴桃种植行业发展现状与发展前景分析报告(2015-2019)" href=ythd_1cdk850t864uc578dlvl_5.html>中国猕猴桃种植行业发展现状与发展前景分析报告(2015-2019)</a></li><li><a title="高考综合复习 带电粒子在复合场中的运动专题" href=ythd_9afu34ohfm208bi78doh_2.html>高考综合复习 带电粒子在复合场中的运动专题</a></li><li><a title="内蒙古自治区四子王旗白乃庙铜矿核查矿区Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ、Ⅺ矿段资源储量利用现状" href=ythd_3rdm71cppb9uewu2s0h44x67j2pwjr01ecz_6.html>内蒙古自治区四子王旗白乃庙铜矿核查矿区Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ、Ⅺ矿段资源储量利用现状</a></li><li><a title="地理教学中进行活动设应注意哪几个问题" href=ythd_9vnsu5dp2y3fmdy9vdbm_5.html>地理教学中进行活动设应注意哪几个问题</a></li><li><a title="压铸原理及工艺练习题及参考答案" href=ythd_0rj5l48pva4uc568dm2a_4.html>压铸原理及工艺练习题及参考答案</a></li><li><a title="当好基层政治处主任之我见" href=ythd_4nz9101beh6trx0166ci_1.html>当好基层政治处主任之我见</a></li><li><a title="网页设计 - 图文" href=ythd_3sps41q6nq0n19a8i5j0_5.html>网页设计 - 图文</a></li><li><a title="华为FusionCloud桌面云解决方案5.2高效维护技术白皮书" href=ythd_5es5c8qta110ttc0odww_8.html>华为FusionCloud桌面云解决方案5.2高效维护技术白皮书</a></li><li><a title="八年级上语文第五单元文言文练习题" href=ythd_7ptjg1aalv3j4lf875m0_2.html>八年级上语文第五单元文言文练习题</a></li><li><a title="生理学" href=ythd_3vxhe13h2v9emeo57bma_3.html>生理学</a></li><li><a title="新行政诉讼法题库" href=ythd_91gd53g0h062a888ee9m_6.html>新行政诉讼法题库</a></li><li><a title="常见汽车电器针脚定义 - 图文" href=ythd_6f1nj2o3je8qp201381d_8.html>常见汽车电器针脚定义 - 图文</a></li>
</ul>
</div>
</div>
<footer class="footer">
<p class="bt-links"><a href="https://m.yuntihai.com/">手机版</a><span class="v-line">|</span><a href="https://www.yuntihai.com/">PC版</a><span class="v-line">|</span><a href='/update.html'>最新更新</a><span class="v-line">|</span><a href='https://www.xuekeyun.com/'>学科云</a></p>
<p>Copyright © 2021-2025 云题海 版权所有<br/>
声明 :本网站尊重并保护知识产权，根据《信息网络传播权保护条例》，如果我们转载的作品侵犯了您的权利,请在一个月内通知我们，我们会及时删除。<br>客服QQ：370150219 邮箱：370150219@qq.com<br>
<a href="https://beian.miit.gov.cn/" target="_blank" rel="nofollow">苏ICP备16052595号-3</a>
</p>
<script>
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "https://hm.baidu.com/hm.js?ba4893542539f4c5d80474ef78f6ce5e";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
</script>
<script>
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https') {
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else {
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
</script>
</footer>
<div class="theme-popover">
<div class="theme-poptit">
<a href="javascript:;" title="关闭" class="close">×</a>
<b>游客快捷下载通道</b>（下载后可以自由复制和排版）
</div>
<div class="theme-popbod dform">
<p class="downtit">下载本文档需要支付 <i>10</i> 元</p>
<p class="chose"><span>支付方式：</span><span class="pay1"><img src="https://www.yuntihai.com/img/wxpay.jpg" class="over"></span> <span class="pay2"><img src="https://www.yuntihai.com/img/alipay.jpg"></span></p>
<div class="youke_pay">
<div class="wxpay"><a href="javascript:;">微信支付并下载</a></div>
<div class="alipay" style="display:none;"><a href="javascript:;">支付宝支付并下载</a>
</div>
</div>
<p class="tiaozhuan"><a href="https://www.yuntihai.com/user/index.php" style="color:blue;">开通VIP包月会员</a> 特价：<b style="color:red;">29元/月</b></p>
<p class="downtxt">注：下载文档有可能“只有目录或者内容不全”等情况，请下载之前注意辨别，如果您已付费且无法下载或内容有问题，请联系我们协助你处理。<br>微信：xuecool-com QQ：370150219</p>
</div>
</div>
<div class="theme-popover-mask"></div>
<script type="text/javascript">
//menu
$(".header .menu").on("click", function(){
$("body").append("<div class=\"mask-bg menu-mask-bg\"></div>");
$(".menu-slide").show();
$("html,body").css({height:$(window).innerHeight(), overflow:"hidden"});
setTimeout(function(){
$(".menu-slide").css({transform:"translateX(-50px)"});
},50)
});
$("body").on("click", ".menu-mask-bg", function(){
$(".menu-slide").css({transform:"translateX(-100%)"});
$(".menu-mask-bg").remove();
$("html,body").removeAttr("style");
setTimeout(function(){
$(".menu-slide").hide();
},300)
});
//search
$(".header .search").click(function(){
if($(".search-box").is(":hidden")){
$(this).children("i").removeClass("search-icon").addClass("close-icon");
$(".search-box").fadeIn("fast");
}else{
$(this).children("i").removeClass("close-icon").addClass("search-icon");
$(".search-box").fadeOut("fast");
}
});
//nav
if($(".nav").length > 0) {
var nav = new Swiper(".nav",{
slidesPerView: "auto"
});
}
</script>
<script type="text/javascript">
$(".user-login").click(function () {
$(".drop-menu").toggle();
});
</script>
<script type="text/javascript">
$(".pay1 img").click(function () {
$(".wxpay").css("display", "block");
$(".alipay").css("display", "none");
$(".pay1 img").addClass("over");
$(".pay2 img").removeClass("over");
});
$(".pay2 img").click(function () {
$(".wxpay").css("display", "none");
$(".alipay").css("display", "block");
$(".pay1 img").removeClass("over");
$(".pay2 img").addClass("over");
});
</script>
<script type="text/javascript">
var userinfo = function(data) {
if (data.code === "2" || data.code === "3") {
$(".word-pic a").click(function(){
$(".theme-popover-mask").fadeIn(100);
$(".theme-popover").slideDown(200);
var downid = "3ts4l33x1e8ojis8frem"
$(".wxpay a").click(function(){
var readurl = 'https://www.yuntihai.com/plus/view.php&psrc=';
var downurl = 'https://www.yuntihai.com/d.asp?id=';
var payurl = readurl;
payurl = payurl.replace('view.php', 'pay/pay-wx.asp?id=3ts4l33x1e8ojis8frem');
var gotourl = payurl + downurl + downid
location.href = gotourl;
})
$(".alipay a").click(function(){
var readurl = 'https://www.yuntihai.com/plus/view.php&psrc=';
var downurl = 'https://www.yuntihai.com/d.asp?id=';
var payurl = readurl;
payurl = payurl.replace('view.php', 'pay/pay-zfb.asp?id=3ts4l33x1e8ojis8frem');
var gotourl = payurl + downurl + downid
location.href = gotourl;
})
});
}
else{
$(".word-pic a").click(function(){
location.href = "https://www.yuntihai.com/d.asp?id=3ts4l33x1e8ojis8frem";
});
}
}
$(document).ready(function($) {
$(".theme-poptit .close").click(function(){
$(".theme-popover-mask").fadeOut(100);
$(".theme-popover").slideUp(200);
});
});
</script>
<script src="https://www.yuntihai.com/user/check_level_m.php?callback=userinfo"></script>
<script src="https://m.yuntihai.com/js/gobacktop.js" type="text/javascript"></script>
</body>
</html>