MLCEA一种基于实体的XML关键字查询语义.ppt

MLCEA: 一种基于实体的XML关键字查询语义 黄静 徐俊劲 周军锋 孟小峰 中国人民大学WAMDM实验室 大纲 研究背景 基于实体的查询语义 查询算法 实验与分析 总结 查询XML数据 关键字查询：定义有效的查询语义 相关工作： LCA Lowest Common Ancestor SLCA Smallest LCA XSEarch VLCA Valuable LCA 本文的贡献 提出了基于实体的查询语义LCEA和MLCEA,能够避免已有方法存在的问题,有效的提高关键字查询的质量. 提出了基于LCEA和MLCEA语义的有效查询算法. 进行了全面的实验比较,实验结果表明本文的语义相比较已有的工作更加有效,所提出的算法同样能高效的运行. 大纲 研究背景 基于实体的查询语义 LCEA Lowest Common Entity Ancestor MLCEA Meaningful LCEA 查询算法 实验与分析 总结 结点分类 一个XML文档可以看成是由一些现实世界中的实体,属性,实体间关系组成,这与关系数据库中的ER模型相似. 结点分类：实体结点、属性结点、连接结点、值结点 [Liu et al 07] LCEA语义 1 实体结点作为基本语义单元，代表现实世界中实体，是用户所需的信息。 给定m个结点n1,n2,…,nm,结点v是它们的最低公共实体祖先,当且仅当: v是实体结点,且 v是ni 1≤i≤m 的祖先结点,且 不存在实体结点u, u是v的后代,且u是ni 1≤i≤m 的祖先结点. 则v LCEA n1，n2，…，nm . LCEA语义 2 LCEA语义能避免不相关的结果，能准确地返回给用户所需的结果。 MLCEA语义 一般来说,用户提交查询的时候,如果想知道两个同名实体之间的关系,查询中应该使用两个同名实体的相同属性的关键字进行查询 如果两个关键字对应同名实体的不同属性,则一般来说,用户需要的是同时满足这两个关键字的一个实体对象 给定m个结点n1,n2,…,nm, v LCEA n1,n2,…,nm . v是一个有意义的LCEA,即v MLCEA n1,n2,…,nm ,当且仅当不存在结点ni, nj 1≤i＜j≤m 使得:Attr ni ≠Attr nj LCEA ni ～LCEA nj LCEA ni ≠LCEA nj 成立. 大纲 研究背景 基于实体的查询语义 查询算法 实验与分析 总结 计算LCEA集合算法 性质1:LCEA n1,n2,…,nm LCEA LCA n1,n2,…,nm . 性质2:LCEA n1,n2,…,nm LCEA LCEA n1,n2,…,nm-1 , nm . 计算MLCEA集合算法 求LCEA结点?判断是否是MLCEA 大纲 研究背景 基于实体的查询语义 查询算法 实验与分析 总结 实验与分析 实验配置： Intel双核2.0GHz，内存1GB 实现：Java 数据集： SIGMOD Record：500KB XMark：115MB DBLP：130MB 查询：包含1-5个关键字 低频查询：关键字出现频率为1-100 中频查询：关键字出现频率为101-1000 高频查询：关键字出现频率大于1000 指标： 查询质量：查准率、查全率 查询效率：执行时间 标准结果： 将关键字查询转化成对应的XQuery查询,并在已有的XQuery查询引擎X-Hiv/DB上执行这些查询,将得到的结果作为标准结果 实验结果：查准率 实验结果：查全率 实验结果：执行时间 大纲 研究背景 基于实体的查询语义 查询算法 实验与分析 总结 结论 本文研究了XML关键字查询的有效性问题. 提出的LCEA和MLCEA语义可以在为用户提供简单易用的查询方式的同时，返回更有意义的结果. 实验结果验证了本文方法的有效性.未来工作将考虑基于实体为基本单元对结果进行排序以及结果展示的问题. 谢谢！QA * * bib 0 Mike 0 . 0 . 0 . 0 author 0 . 0 name 0 . 0 . 0 papers 0 . 0 . 1 title XML 0 . 0 . 1 . 0 . 0 0 . 0 . 1 . 0 . 0 . 0 year 2002 0 . 0 . 1 . 0 . 1 0 . 0 . 1 . 0 . 1 . 0 paper 0 . 0 . 1 . 0 paper 0 . 0 . 1 . 1 title IR 0 . 0 . 1 . 1 . 0 0 . 0 . 1 . 1 . 0 . 0 0 . 0 . 1 . 1 . 1 year 2000 0 . 0 . 1 . 1 . 1 . 0 paper 0 . 0 .