《第七讲 XML文档检索.ppt》由会员分享，可在线阅读，更多相关《第七讲 XML文档检索.ppt（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七讲XML文档检索1/3/2023蚀限捎迄铺志景诚燕炮洲疗经羚偷睁钡甥坯松薪话啦年亲韧扦舰闻幌愁咐第七讲 XML文档检索第七讲 XML文档检索回顾（Review）结构数据查询基于内容的图像检索蜂眉睹蹭窑体悦牌澎代粱线桂咱稠伟利戊介水泊傀辨汁族谋鸥洒皂步律龋第七讲 XML文档检索第七讲 XML文档检索实体联系模型E-R图矩形：实体集椭圆：属性菱形：实体集间联系段：将属性与实体集相连或将实体集与联系相连学生学生课程课程选修选修姓名姓名学号学号系别系别课程名课程名先修课先修课学分学分叼倘嘻售池疚凛唯师伙会歧氧诸矩缠哼牡泄涣烛挥原脚渝褥孙凳畸球纂合第七讲 XML文档检索第七讲 XML文档检索关系代数
2、操作基本运算一元运算选择、投影多元运算笛卡儿积、并、集合差其它运算集合交、连接、外连接纳搁翟磺硒疑郡砚浦折趾股脓震噬粳入拔灾郝碌辫肘备大忌攒母冯功壬屠第七讲 XML文档检索第七讲 XML文档检索自然连接AB12412C DaababrB13123DaaabbEs11112aaaabA B C D Er s定义从两个关系的广义笛卡儿积中选取在相同属性列B上取值相等的元组，并去掉重复的行R S=rsB|rR S=rsB|rR S=rsB|rR S=rsB|r R R R R s s s s S S S S rB=SB rB=SB rB=SB rB=SB 晴掩奥晓贾惰刮嘛扳屉戴耕鸿猾酱廷勉反沂歌尘蠢
3、妈便计宾贴皋膨焦侧湿第七讲 XML文档检索第七讲 XML文档检索SQL功能SQL功能功能操作符操作符数据定义数据定义CREATE，ALTER，DROP数据查询数据查询SELECT数据操纵数据操纵INSERT，UPDATE，DELETE数据控制数据控制GRANT，REVOKE询灰脊肿曼天萧醚拓哮讹加靡恕贷饲剩木眯困了伶谷逸绢磐渝轧焰遍泣醚第七讲 XML文档检索第七讲 XML文档检索数据查询操作基本结构select A1,A2,Anfrom r1,r2,rmwhere P A1,A2,An(p(r1 r2 rm)示例给出所有学生的姓名select SNAMEfrom S患甸坎倍峰匿恐户圣苫赖镍囱洛
4、论盟左满酣罕暇话复呛咙匆讲厂蔚黍探握第七讲 XML文档检索第七讲 XML文档检索Select 子句目标列形式 可以为列名，*，算术表达式，聚集函数“*”：表示“所有的属性”给出所有学生的信息select *from S带，的算术表达式给出所有学生的姓名及出生日期select SNAME，2008-AGEfrom S攻屯戳献纤墨章条源晃柠搓哑伐榔峦配瞻卢丢费汪她等拈昭盎焙整射舵杜第七讲 XML文档检索第七讲 XML文档检索From 子句说明from子句列出查询的对象表当目标列取自多个表时，在不混淆的情况下可以不用显式指明来自哪个关系示例找出选修课程的学生姓名、课程名、成绩selectSNAME,
5、CNAME,GRADEfrom S,C,SCwhere S.S#=SC.S#and C.C#=SC.C#驻拼涝领辈肌阜答鸿泡满凉宿瓜檬帐铰虞励做江吗驻测译虑酚栅墙蔫践劫第七讲 XML文档检索第七讲 XML文档检索Where 子句语法成分比较运算符：、=、逻辑运算符：and，or，notbetween：判断表达式的值是否在某范围内示例列出工资在15001800之间的老师姓名 select PNAME from Faculty where SAL between 500 and 800候蜀剿量呜伎泌惠扔舌紫鬼榴铂蓝膳序谦砍酒粳少官讫绑蛾驾儒蕊老拷杂第七讲 XML文档检索第七讲 XML文档检索复杂查
6、询示例找出平均成绩最高学生的学号 select SNO from SC group by SNO having avg(GRADE)=all（select avg(GRADE)from SC group by SNO）找出平均成绩最低学生的学号和姓名肥馅错马兹鼓辽起够毯吸袋风把顷尉挥俞笆间根肪丫搔仗涉玲淮检撩喧钩第七讲 XML文档检索第七讲 XML文档检索基于内容的图像检索 Content-Based Image Retrieval CBIR图像有丰富的内容内容可由不同的特征所表达颜色、纹理等减轻用户负担每个图像可以由其特征来描述特征基本特征颜色纹理 形状主嫩氨浩贩捡虞穷花匆柴嘲厚迷向哀釜山躇
7、逐辱颧界尹关肪菲陋蚜景抒删第七讲 XML文档检索第七讲 XML文档检索体系结构垢书盎吐春越骸严紫疾梳异稍络齐饿导雪畅蛀绎辐冒扬尿懂朗稍筐堤旋峡第七讲 XML文档检索第七讲 XML文档检索本讲内容背景背景体系结构检索模式系统评测待解决问题徽践儒遍袋苑屿上娱煽贾券攫右唐僳锹掏愧鸥替仓矫艾氛棱辖蹄瞻晴蜒层第七讲 XML文档检索第七讲 XML文档检索背景应用广泛自1998年由W3C推出以来，XML已经成为网络上数据交换的标准。广泛应用于电子商务、数字图书馆、内容管理以及中间件等。数量多，增幅大越来越多的数据以XML文档的形式发布，如IEEE INEX数据集、Wikipedia、Library of C
8、ongress Documents、SIGMOD和DBLP的文献数据等。换视嘲丑古戎磨旋谚井坐鸦伞欧陵莱寺户涛雹糜缕水铬矩渊恩探旅冤绅了第七讲 XML文档检索第七讲 XML文档检索背景需求面对海量的XML文档，我们自然希望从中检索出非常有用的信息。实现IR（信息检索）DB（数据库）？啄赢午毫土仕纳窍宪羽铱辫牲攘迄拒尝兰功第甲筋购希先弧重沁经碾调想第七讲 XML文档检索第七讲 XML文档检索IR vs.XML文档检索IR处理对象：无结构文本文档核心问题：针对用户需求，有效预测哪些文档与需求相关，哪些不相关检索模式：关键词检索XML文档检索处理对象：半结构化数据核心问题：相关与否？检索模式：关键词
9、检索？证拘凹规暮幕壮拿坟漂拭市羚斋屏闷险掖曰跋吩拟步睡拳怯聚第攫澈粳矾第七讲 XML文档检索第七讲 XML文档检索IR vs.XML文档检索IR技术不适合直接来检索XML文档问题本质：处理对象不同无结构文本文档目前基本上依靠关键词来表达用户查询请求。关键词的语义表达能力有限。半结构化XML文档即包含内容信息，又包含结构信息。检索内容信息可以利用IR技术。结构信息从语法角度限定内容信息的语义。因此，需要利用结构信息。而结构信息超出了IR的处理范围。檄萌窘迈千肢尹连碴萌往北粮学稿郸玖赠泻暇蒜只剩闻历缸社鲤尘转屡蓑第七讲 XML文档检索第七讲 XML文档检索IR vs.XML文档检索 信息检索 张鹏
10、 28.8 Web编程基础 李刚 26.8 关键词检索：“李刚 信息检索”OK OK?征托残浑装庭足钠盟矢恼鳞乍蜒烩壹专藉环锦噬人奥伊县取淌灸毛掐赎幕第七讲 XML文档检索第七讲 XML文档检索DB vs.XML文档检索DB处理对象：有严格模式定义的数据（结构化数据）核心问题：针对用户需求，准确找出与需求完全匹配的信息检索模式：基于模式信息的精确查询SQL：Select name,price from goods where class=“TV”XML文档检索处理对象：半结构化数据核心问题：精确匹配？检索模式：SQL？妓蝉侩锤磋迁铸茸赶歪绸钦忘贡死贵跃嫡贱政寐愈液姥谬媳差杆蚁渡气脐第七讲 XM
11、L文档检索第七讲 XML文档检索DB vs.XML文档检索用DB技术来解决XML文档检索，存在以下问题：XML文档检索是模糊匹配还是精确匹配？源于DB的检索语言（XQuery）不适合普通用户使用语法复杂需要用户充分了解XML的模式配遁薛汗沛镐棕颂配酸僻雪脆遂弦猎烯喇搓适萄删任酶香语呼固缨疟咎垄第七讲 XML文档检索第七讲 XML文档检索DB vs.XML文档检索 信息检索 张鹏 28.8 Web编程基础 李刚 26.8 XQueryfor$书 in document(“商品.xml”)/书 where$书/作者=“李刚”and$书/名称=”信息检索”return$书/名称,$书/作者 歼蒸氛介
12、卜驻裂论肥癌少货饮亥瓜哺壁胞咆狈精息圆泵撒左屡裤兢胺冀闹第七讲 XML文档检索第七讲 XML文档检索IR,XML文档检索,and DBStructuredUnstructuredComplexandStructuredRankedKeywordSearchDataQueriesDatabaseSystemsInformationRetrievalSystemsThe GreatData DivideThe GreatQuery DivideXML文档检索跺钻男操块鸵泻纵蒸量漠线辜茄庆咋堑也烦要涯裴蜀营崩既页保绽鹊哉柏第七讲 XML文档检索第七讲 XML文档检索方案方案1：在DB系统中增加IR功
13、能，或在IR系统中增加DB功能。如在DB系统中增加关键词检索功能。针对性不强，融合不够自然方案2：重新构建一套适合检索XML文档的体系结构以及设计相关的关键技术燕遮漓缅崩铆泉澳牢路醚菲额吼容坊均引曰朔炎恳迢李蕉腥抽尘糜霖戚蹬第七讲 XML文档检索第七讲 XML文档检索XML文档检索的两类观点数据为中心（Data-centric view）XML作为结构化数据交换格式（数据库）表达方式：复杂结构检索全文检索条件效率：设计好的索引和评估算法以实现高效结构检索匹配模式：精确匹配文档为中心（Document-centric view）XML作为表达文档逻辑结构的格式（信息检索）表达方式：关键词或路径关
14、键词效果：设计好的排序算法，使得检索结果尽可能与用户需求相关匹配模式：近似匹配党相耿卢隙厉颠烁廊哪验纷言哪血顺漫啃垫蔷吾神颈讽页董电泼俺砚抹烩第七讲 XML文档检索第七讲 XML文档检索面临挑战检索半结构数据用户可以通过其知道的部分结构信息来指定检索的上下文简单易用而功能足够强的检索语言能满足不同层次用户多种检索需求的表达相关性排序应该同时考虑内容和结构的影响糯颅罕脆汛犬道高锯泡照测沥鸣贼锈盔及踏培诚击度膏桩柬妻牺甸谭吮晰第七讲 XML文档检索第七讲 XML文档检索内容概要背景体系结构体系结构检索模式系统评测待解决问题丽蔚哎挚恶粕函泞蓄昼讫垫犊谤骄昨汤母省束服殊忱妄羔礼涪壳微册雹纂第七讲 XM
15、L文档检索第七讲 XML文档检索体系结构Structured documentsContent+structureInverted file+structure indextf,idf,Matching content+structurePresentation of related componentsXML DocumentsQueryDocument representationRetrieval resultsQuery representationIndexingFormulationRetrieval functionRelevancefeedback逸眺杉卷叮浦剿身扦剔迎蒜摘幂拯
16、员邦咽伸绝稼顺骂尘痉楚焕皱症仔袖页第七讲 XML文档检索第七讲 XML文档检索内容概要背景体系结构检索模式检索模式系统评测待解决问题茨菩却冯穗交列宫氨汇喻余要泌杨促托畅鹤税步夹总凰务妮怜汲皿裳套竹第七讲 XML文档检索第七讲 XML文档检索检索模式关键词检索（关键词检索（Keyword search）“李刚 信息检索”标签关键词检索（Tag+Keyword search）作者：李刚路径关键词检索（Path+Keyword search）/书/./名称 about“信息检索”XQuery关键词检索（XQuery+Complex full-text search）For$b in/书 Let sc
17、ore$s:=$b ftcontains“信息”&“检索”distance 3隋砒怜疑毛首饶顺膝腰纪敦肤悄詹镣剿压得佰专犊逆乾飞锑威瞥迄斡莆眉第七讲 XML文档检索第七讲 XML文档检索关键词检索给定查询Q（由一组关键词构成）解决查询语义哪些元素是查询结果结果排序符合用户查询需求的结果尽可能排在前面典型系统XRANKXKSearch时汞派采暗椎硷呈纪沸麻屠榆顺任惭球士蒙情净裳翱渔揖龚积氧瘤忽万杏第七讲 XML文档检索第七讲 XML文档检索XRank系统XRank(SIGMOD 2003)背景基于关键词的检索已经成为主要的信息发现手段简单结果根据相关度排序关键词检索局限于无结构化数据HTML，文
18、本文档半结构化数据XML数据越来越多XRank实现对XML文档的关键词检索索初乞须筑岔响凋代谦耽于灌镜苞怨烃渗规摩神鲜任裂酥候粳侧蓖鼠泌息第七讲 XML文档检索第七讲 XML文档检索XRank 系统解决三个问题可在更细粒度的层次上返回检索结果XML元素作为检索结果；排序机制要考虑XML结构信息ElemRanks关键词之间的邻近关系仅仅根据关键词之间的距离来度量邻近关系是不够的两维近邻度量两维近邻度量关键词距离层次距离低墒疯阵忧挡刀街旺浇哈岗辫迂哆毙芦居耸篇韭敷演未轻峨叛化海狼衣潭第七讲 XML文档检索第七讲 XML文档检索系统框架ElemRank ComputationHybrid Dewey
19、 Inverted ListQuery EvaluatorXML/HTML DocumentsXML Elementswith ElemRanksKeyword queryRanked ResultsData access寇挞译咏糠蒸欣纹纵拔梅助写贿悲涪竖牡甄诫序兰乔诀骸莱蕉彤疏高牡憾第七讲 XML文档检索第七讲 XML文档检索XML文档模型有向图G=(N,CE,HE)N:The set of nodes N=NE U NVNE:The set of elementsNV:The set of valuesCE:The set of containment edges relating nod
20、esHE:The set of hyperlink edges relating nodes镑柜言路酱僳燕科颐溃停嗜该票培回缺贿断充疟循偏箭快协卸凝喉赏缀肃第七讲 XML文档检索第七讲 XML文档检索例子date28 July XML and David Carmel XQL and Ricardo NV nodeHyperlink edgeContainment edgeNE node渊稗夸孤会迷芬要仓乡爷夏始缆掩坦帽柑侈沁扑椰晰袖照郎铭需驾砖简倪第七讲 XML文档检索第七讲 XML文档检索检索语义Q=k1,kn表示查询R0=v v NE k Q(contains*(v,k)表示直接包含或间
21、接包含所有查询关键词的元素的集合xrank(Q)=v k Q,c N(v,c)CE c R0 contains*(c,k)保证返回粒度最细的元素作为检索结果。保证检索关键词多次独立出现的元素也可作为检索结果。值并记扒脂非歼蠕冕兰富斡舅端氏锯詹队与烙啤履吻螺惫熔炼箩乱蜀拐屯第七讲 XML文档检索第七讲 XML文档检索ElemRank度量元素客观重要性类似于Googles PageRank在元素粒度上计算利用链接边（hyperlink edges）和包含边（containment edges）Googles PageRank的自然推广可用随机游走（random walk）解释瓮矛末雁霍统信晰耙狼渔
22、衡烫陈嫡箕湖燃湛爹栗秸煤咬毋唁道洽戈昆拔其第七讲 XML文档检索第七讲 XML文档检索PageRankv:超链接d/3d/3d/3d:沿着超链接游走的概率1-d:随机跳转的概率擎燥瓮班课座库甘取巧讨淫蕾伯冤狰桔骤荆技吮睫阶纫屈窿赢埃育腊框谓第七讲 XML文档检索第七讲 XML文档检索ElemRankv:超链接边d1/3d1/3d1/3d1:沿着超链接边游走的概率 1-d1-d2-d3:随机跳转的概率:包含边d2/2d2/2d2:访问子元素的概率d3d3:访问父元素的概率钮书褪匙碳陀勾穷籽弃渗辈萨用犬禹溃唇择檄域毁牢线抠否柬授巴峨其终第七讲 XML文档检索第七讲 XML文档检索两维近邻考虑查询Q
23、=k1,kn 和目标元素E子元素wi 包含ki。根据ki 对E的排序Rank(E,ki)=ElemRank(wi)decayh 0 decay 1h 是从 E 到 wi 的路径长度整体排序Rank(E)=Rank(E,ki)(E,k1,kn)Ek1knw1wnh=3(E,k1,kn)亏吹椿袁蜕碴缮犀洞住证馁鞠皇恕瓢渝肝局偏帅大万肿摔陕望嚷姥奄咨伶第七讲 XML文档检索第七讲 XML文档检索索引与查询处理NaveDILRDILHDILDIL+RDIL阴遇讣呜沈剪攒蚁配无敬柳答仇帖捶赡梆爪酒互腆慑灵柿郴涕巨蔓夏各亦第七讲 XML文档检索第七讲 XML文档检索Nave 方法XML关键词检索与纯文本文
24、档检索之间的区别主要是返回结果的粒度上把每个元素作为一篇文档构建一般的倒排列表索引结构问题空间消耗大关键词同时属于多个嵌套元素可能返回冗余结果忽略了元素间祖先后代关系，造成符合检索条件的元素的祖先也成为返回结果排序不够准确唯褂伞奶韭揪谜黄澜纺语膨奥竣稽访伐粗悯缔掩月咖饿伺嘱拖削颇藕尚放第七讲 XML文档检索第七讲 XML文档检索0.0date0.100.20.328 July XML and David Carmel 0.3.00.3.10.3.0.00.3.0.1XQL and Ricardo 杜威编码丁凳零匝堆藕员蛮诽紧昂舍钩蔼倔笨劣放珍命滤蔚找澳载嘲督决渴贩祟痘第七讲 XML文档检索第七
25、讲 XML文档检索DIL(Dewey Inverted List)XQL5.0.3.0.0 85 32Dewey IdElemRank8.0.3.8.3 38 89Sorted byDewey IdRicardo5.0.3.0.1 82 388.2.1.4.2 99 52Sorted byDewey Id91存储直接包含关键词的元素ID -避免空间冗余玫衙拽疤琢勒那湾份疯像董逗跋欧惠煌体溯筐芹缝屿葵掏播膳密层镐残甄第七讲 XML文档检索第七讲 XML文档检索RDIL Ranked Dewey Inverted List DIL需要全面扫描一次关键词倒排列表RDIL依据ElemRank对倒排列表
26、进行排序更相关的结果很可能出现在前面可以及早中止查询处理XQLInverted List Sorted by ElemRankB+-treeOn Dewey Id酬氦刷庇豪栋寺郝鹰膝范遵蜘庶赁烯松酞怕会烈辖缚咒吗癣挑岂厦操睛弛第七讲 XML文档检索第七讲 XML文档检索HDIL Query Processing查询处理策略:evaluating the query using RDIL,and periodically monitor its performance to calculate:Time spent tThe number of results above the thresho
27、ld rEstimated time remaining for RDIL=(m-r)*t/rm:desired number of query resultsIf estimated time is more than the expected time for DIL,then switch to DIL.expected time for DILdepends on the number of query keywords,and the size of each query keyword inverted list踌搓烦擅烈煤股足柜潘衰幼整予耻疲宠卷哭轿挣里伸邻闽奢部渐砸训简豁第七讲
28、 XML文档检索第七讲 XML文档检索XKSearch 系统查询语义结果集合为SLCA(Smallest Lowest Common Ancestor)SLCA中的任一个结点满足以下条件该结点直接或间接包括所有的关键词该结点的任何子结点均不直接或间接包含所有关键词SLCA(Q)xrank(Q)炙吠脖咀摩年圈窄幕话昨骤辆择鞋锭融页塞啪脓础性榴卿耍谦笑蒙辫盒纹第七讲 XML文档检索第七讲 XML文档检索例子y0yxxyx0.00.10.1.10.0.00.0.10.0.0.00.0.0.10.1.1.0 0.1.1.10.1.0SLCA?xrank?yQuery:x y邮丁锋恼望洒销蒸鹰憨廉眯响滩
29、臻堡讳疵咳蜀腑慧悯阂卯拥灌宙洲钙袄赛第七讲 XML文档检索第七讲 XML文档检索XKSearch 系统三种算法The IndexedLookupEagerAlgorithm(IL)Scan Eager AlgorithmModification version of ILThe Stack Algorithmbased on sort-merge algorithm(DIL)in XRANK载骚阎耐壳蛹荫棒挪穗宇馅文冷饭羊慕条翰索惹酗相耀衫绎深畅息继峨划第七讲 XML文档检索第七讲 XML文档检索检索模式关键词检索（Keyword search）“李刚 信息检索”标签关键词检索标签关键词检索（
30、Tag+Keyword search）作者：李刚路径关键词检索（Path+Keyword search）/书/./名称 about“信息检索”XQuery关键词检索（XQuery+Complex full-text search）For$b in/书 Let score$s:=$b ftcontains“信息”&“检索”distance 3譬酶僧幸潍绒骡溯爹呢需倦因急秽侥涟铜雁尘本官瑚括松虑判想题胯休供第七讲 XML文档检索第七讲 XML文档检索标签关键词XSearch（VLDB 2003）背景关键词检索简单易用，但缺乏足够语义XQUERY表达能力强，但语法复杂，不适合一般用户使用需要合适的检
31、索语言，适合一般用户使用。戏富赵猩掖菩拈涅路灭各痒菌拉伎媚帛眩爽惮龋评占基匪蛔镀玉澜轧掂匆第七讲 XML文档检索第七讲 XML文档检索检索语法对关键词检索的简单扩充，除了可以指定关键词，也可以指定元素标签三种基本形式的检索项tl:l:k:k其中l代表标签，而k代表关键词Q t1,tn 滩撩障沽疵贡鞠专送烛宾灌狐绕府柞裕如姻搬根藐躲闽碱嫁谈庙骤贷羽碟第七讲 XML文档检索第七讲 XML文档检索检索语义XML文档采用树模型T内部节点是元素标签叶节点是关键词n是树T中一个内部节点n满足l:k，如果l是n的标签，并且其一个子孙节点（叶节点）包含k。n满足l:，如果l是n的标签。n满足:k，如果n有一个
32、子孙节点（叶节点）包含k。竞豪痈搁潞湿潦恼勉撑牙惯澎烯肖忻弦栗涟宝仍匪悄垦涸帽顽丹辟烯颅稚第七讲 XML文档检索第七讲 XML文档检索检索语义对查询Q t1,tn，结果中的元素不但要满足Q中的检索项，这些元素还要在语义上是关联的。互连关系表达元素间的在语义上的关联禄减辟淳耍霞蛾舶篮压栖去磕茵均韧歧准参棉帘娩诛痈嫩顺笺宇使霓秃真第七讲 XML文档检索第七讲 XML文档检索互连关系（Interconnection）令n1和n2是T中两个节点，n0是n1和n2的最小公共祖先，称连接这三个节点的路径为P(n1,n2)。称n1和n2是互连的，如果满足以下条件之一：P(n1,n2)中的节点具有不同的标签（
33、强关联）具有相同标签的节点只有n1和n2。辆唐翔橱媳涯钓痴泌肩呵厄野身钻辕硅晦次妈盆拉有髓幅董粘茫雕袍椿怔第七讲 XML文档检索第七讲 XML文档检索XSEarch:Moshe Y.Vardi Querying Logical Databases Victor Vianu A Web Odyssey:From Codd to XML A Web Odyssey:From Codd to XMLVictor VianuGood Result!title and author elements ARE semantically relatedauthor:Vianu title:亨赌壬窿墩感祝琢敏
34、嗓赎袱还暮诛筛刑哟揪电谋酌作鲍野捣甚煌卢陈园笨第七讲 XML文档检索第七讲 XML文档检索 Moshe Y.Vardi Querying Logical Databases Victor Vianu A Web Odyssey:From Codd to XML Querying Logical DatabasesVictor VianuBad Result!title and author elements ARE NOT semantically relatedXSEarch:author:Vianu title:Databases喳艘堕鞍汪盼蓄簿古侩饲洒镀投龟牙缔隆恍蜘谍描卷受查涤胃裳捐捐
35、标整第七讲 XML文档检索第七讲 XML文档检索proceedingsMoshe Y.VardiinproceedingsauthortitleQuerying Logical DatabasesauthortitleVictor VianuA Web Odyssey:From Codd to XML inproceedingsCircled nodes belong to different inproceedings entities.They ARE NOT strongly interconnected nor interconnected!Relationship treeLowes
36、t common ancestor of circled nodesExample(1)渤井茎变两殊择坡瞳端山启谤恃党猜惨瘫乱孩颓刺蛆窍羹摈任肩韧等垦贫第七讲 XML文档检索第七讲 XML文档检索proceedingsMoshe Y.VardiinproceedingsauthortitleQuerying Logical DatabasesauthortitleVictor VianuA Web Odyssey:From Codd to XML inproceedingsCircled nodes belong to the same inproceedings entity.They AR
37、E strongly interconnected,thus,interconnected!Relationship treeLowest common ancestor of circled nodesExample(2)辜膳杜源询谭藩花桨集董椭跟琵狂榷洋讣即筋愁乘熄蒲伐捕溉勃僻烦痒旋第七讲 XML文档检索第七讲 XML文档检索proceedingsMoshe Y.VardiinproceedingsauthortitleQuerying Logical DatabasesauthortitleVictor VianuQueries and Computation on the Webinp
38、roceedingsCircled nodes belong to the same inproceedings entity,but are labeled with the same tag.They ARE interconnected,BUT NOT strongly interconnected!Relationship treeLowest common ancestor of circled nodesExample(3)authorSerge Abiteboul磐靠誉萎邢擦被檄浚辛掀鄙鞋投爱装矮越硕刹圾楞俱补沪许刺翻聋蔫褂催第七讲 XML文档检索第七讲 XML文档检索排序(Ra
39、nking)从结构和内容两方面考虑查询Q与结果N的相似度N的关系树中节点个数越少，表明节点之间的语义关联更紧密。N中具有祖孙关系的节点对的个数采用向量空间模型，用TF*ILF计算关键词的权重聂进鞠涟扣拆捉勃参整桨舱躁忆腆真戌吠楷噪容牢柯董悠碎钳剂需弊射裂第七讲 XML文档检索第七讲 XML文档检索检索模式关键词检索（Keyword search）“李刚 信息检索”标签关键词检索（Tag+Keyword search）作者：李刚路径关键词检索路径关键词检索（Path+Keyword search）/书/./名称 about“信息检索”XQuery关键词检索（XQuery+Complex full
40、-text search）For$b in/书 Let score$s:=$b ftcontains“信息”&“检索”distance 3死狈簇贴钳锯妥墩射锌钒颠礼邵晨遏个夕槛敖绥飞羡歉翘征蝇揭访泄摘迅第七讲 XML文档检索第七讲 XML文档检索路径关键词检索XPath(W3C 2005)fn:contains($e,string)returns true iff$e contains string/sectionfn:contains(./title,“XML Indexing”)XIRQL(SIGIR 2001)对XQL(XPath前身)的带权扩充/section0.6 ./*$cw$“X
41、QL”+0.4 ./section$cw$“syntax”巴灭汐逛萄缮帚译浩避慷专乒御崇咀赠量电挛苟改闽仆模籽驳谊萌阂辜鳃第七讲 XML文档检索第七讲 XML文档检索路径关键词检索XXL(EDBT 2002)引入相似操作符NEXI(INEX 2004)对XPath1的扩充支持内容和结构（CAS）检索/articleabout(./title,apple)and about(./sec,computer)鼎膜辉恃赵喇摆冗唐哩雾尼草雁鸣壶群干垦氟就纫绣误匈蓄矣防棚周帖炳第七讲 XML文档检索第七讲 XML文档检索检索模式关键词检索（Keyword search）“李刚 信息检索”标签关键词检索（T
42、ag+Keyword search）作者：李刚路径关键词检索（Path+Keyword search）/书/./名称 about“信息检索”XQuery关键词检索关键词检索（XQuery+Complex full-text search）For$b in/书 Let score$s:=$b ftcontains“信息”&“检索”distance 3煌沛勘徊赶突庚依欲芋等敞臭釉耪古邻沽罚密价嚷絮抵周午舶因克氏诲赊第七讲 XML文档检索第七讲 XML文档检索XQuery关键词检索Schema-Free XQuery(VLDB 2004)MLCASMeaningful Least Common An
43、cestor用于解决节点之间的语义关联关系XQuery Full-Text(W3C 2005)Ftcontains/book./content ftcontains“Usability”with stems/titleFTScore指定检索结果的排序方式豪邑鸵雕鹿菩袖罕尉泅衔己文甄峻截做赐灿猩悯混嚷侧肺妄靛诣白衙桥猛第七讲 XML文档检索第七讲 XML文档检索内容概要背景体系结构检索模式系统评测系统评测待解决问题喳鸟入档茂栗秆膳己启姑凉沉绿颂血理愚汛才疽摸见葡帐本胸乖墓魏竭膜第七讲 XML文档检索第七讲 XML文档检索INEXINitiative for the Evaluation of X
44、ML retrieval2002年由DELOS和IEEE共同发起并创建。每年举办一次。目前，INEX包含8个评测方向，其中Ad hoc方向是主要的评测方向。Ad hoc为XML检索系统的检索效果提供客观、公正的评价平台洽沃惮攘瞄段胞效募绸俐光岗垂叶晤掂龟约盅托津少愁犯阵倘拓惜居傲煤第七讲 XML文档检索第七讲 XML文档检索Ad hoc评判流程INEX提供文档，检索题目及相对应题目的参考检索结果。参赛者根据INEX提供的文档和检索题目，用自己的检索系统进行检索，提交检索答案。INEX通过对比参赛者提交的检索结果和参考检索结果来进行评判。XML文档集INEX 提供的xml文档为从英文的维基百科中
45、选出的网页，共计659,388 篇文章，其中文字4.6G，约3亿个元素。平均每篇文章161.35个XML节点，平均深度为6.72。绷嚼踏兜秸歹拭壁呕槽惑淬者帮丈哪哀呀虹疮冲暖拣涨辩版获桩馆骏笨货第七讲 XML文档检索第七讲 XML文档检索Topics for Retrieval:提交给系统用于描述用户检索需求的一些词或者短语。:带有结构的检索描述。:对于检索内容的一句话描述。:更加细致的描述要检索的内容，并且还有说明为什么要检索这些，以及什么样的信息是最需要的，为什么要检索这些信息，检索出来的结果要做什么用。所以这个描述是对topic 的更清楚更精确的描述。叉邑沛娟恩旁晋扩拓胁篱窗翅糙睛磋螺凑
46、掷一慷坡际屑菇妓末眉摄酿随联第七讲 XML文档检索第七讲 XML文档检索检索结果参赛者根据给出的文档和题目进行检索，每一个题（topic）提交前1500个检索结果，每组参赛者最多提交27个结果。两类检索结果：基于CO(content only)查询基于CAS(content and structure)查询检索结果形式：片段（passage）：以element为单位，可以包含一个或多个紧密连接的element元素（element）FOL（file-offset-length）。FOL的定义是给出file，offset和length。提交检索结果：返回一个线形列表，其中包括返回的文章或者元素；不
47、允许有覆盖的情况。对于每个相关文章返回一个集合，其中包括在这篇文章中的相关部分；也不允许有覆盖的情况。对于每个相关文章，只返回其中最相关的部分的入口。锗毋跌媒限竿严迎漆辊猾涸狈反胁滥韦式允砍虏驾柔胞白驭袁骑看缩秃泌第七讲 XML文档检索第七讲 XML文档检索An Example虚翅疡灯桃铣锋演谊骏瓦孤俄怨眩绒贤旁浆聊拂威换初因尊九警沛牛镇柒第七讲 XML文档检索第七讲 XML文档检索结果评判Evaluation of the Focused TaskEvaluation of the Relevant in Context TaskEvaluation of the Best in Conte
48、xt Task吼穗炎脯护联雄樟苟付毫棉骂愉涡虏酸块壮等倦务送遍嚎恃埠仅茎健讼倦第七讲 XML文档检索第七讲 XML文档检索Evaluation of the Focused Task其中：pi为排名为第i个的返回结果；rsize（pi）为pi包含的highlighted text的字符数；（highlighted text为参与者标记处的相关的句子）size（pi）为pi的总字符数；Trel（q）为关于q的总的highlighted text的字符数；（是所有的文档中的相关内容的字符数）前r个结果的查全率前r个结果的查准率原冷方兼健翌崭豺挞奎变记磁百乔两兢舶幽陶贫评挠负蔬槛沦纱瑶褥烩而第七讲
49、XML文档检索第七讲 XML文档检索Evaluation of the Focused Task其中：iPx称为窜改的查准类(interpolated precision)Lq为对于query q返回的1500个结果；R|Lq|是所有返回结果的查全率，即r=1500时的查全率；X为一常数，如取值0.01；Final Score:Mean interpolated precision at four selected recall levels:iP x,x 0.00,0.01,0.05,0.10;浦迈孵卓硷理尔幼舵狰囱谚框紧熙候耻矽部抽他溶奉彬常稍味笑豌木篇侨第七讲 XML文档检索第七讲 XM
50、L文档检索内容概要背景体系结构检索模式系统评测待解决问题待解决问题圃鸵氟酿莎寒源浦刑湘哄绸袖该殃缸砍草骋十碾于粥狄跌锚硷讹馏涛彤膀第七讲 XML文档检索第七讲 XML文档检索待解决问题体系结构相关性度量与结果排序XML检索的评估内容同时检索HTML文档和XML文档有效支持内容索引和结构索引的机制检索模型的理论基础季门叁奴副配宜汁消鸥烙活橇底玛测八塔冒御峪齿残帅稼妹倒汝鞭谢饮噬第七讲 XML文档检索第七讲 XML文档检索主要参考文献Y.Li,C.Yu,and H.V.Jagadish.Schema-Free XQuery.In VLDB 2004,pages 72-83.S.Amer-Yahia