XML数据管理技术 周军锋

大纲 简介 流程 内容 总结 2018/12/6

大纲 简介 流程 内容 总结 2018/12/6

综述简介——必要性 XML数据大量涌现 XML研究如火如荼 没有系统的总结和比较 Gartner[1]预测，XML文件的使用率在 2007年达到40%， 2008年将占据支配地位 IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29％正在大量使用XML数据库 XML研究如火如荼 每年各种学术会议期刊发表XML相关论文多达300篇 没有系统的总结和比较 发表时间早：大部分出现在06年左右 内容局限性：主要涉及查询，索引 [1]http://egovstandards.gov.in/summit/eform/technical-papers/gartneruseofxml.pdf/view 2018/12/6

综述简介——信息源 要求 全面性 06-08年各种会议期刊 国际会议 国际期刊 国内会议 国内期刊 2018/12/6

综述简介——信息源 关注的会议 较好的workshop 国际会议 (ACM) SIGMOD ： (Association for Computing Machinery) Special Interest Group on Management of Data VLDB : International Conference on Very Large Data Bases ICDE : International Conference on Data Engineering EDBT : International Conference on Extending Database Technology WWW : International Conference on World Wide Web CIKM : International Conference on Information and Knowledge Management DASFAA : Database Systems for Advanced Applications ER : International Conference on the Entity Relationship Approach PODS : Symposium on Principles of Database Systems SIGIR : International Conference on Research and Development in Information Retrieval ICDT : International Conference on Database Theory DEXA : Database and Expert Systems Applications CIDR : Conference on Innovative Data Systems Research WISE : Web Information Systems Engineering WAIM : International Conference on Web-Age Information Management APWeb : Asia-Pacific Web Conference WebDB : International Workshop on the Web and Databases INEX : INitiative for the Evaluation of XML Retrieval XIME-P : Workshop on XQuery IMplementation, Experience and Perspectives XSym : International XML Database Symposium （08年不存在了） XML Conference : 应用相关的会议 较好的workshop 2018/12/6

综述简介——信息源 国际期刊 VLDBJ ：The VLDB Journal TODS ： ACM Transactions on Database Systems TKDE ： IEEE Transactions on Knowledge and Data Engineering TOIS ： ACM Transactions on Information Systems JACM ： Journal of the ACM CACM ： Communications of the ACM IS ： Information System IR ： Information Retrieval KIS： Knowledge and Information System SIGMOD-Record DKE ： Data & Knowledge Engineering JDM ： Journal of Database Management WWWJ ：World Wide Web JCST ： Journal of Computer Science and Technology 2018/12/6

综述简介——信息源 国内会议 NDBC 国内期刊 计算机学报 软件学报 计算机研究与发展 计算机科学与探索 2018/12/6

综述简介——内容提炼 2018/12/6

综述简介——内容提炼 如何压缩内容？ 已有综述中阐述的内容，直接引用并总结 对所有新内容分类整理，得到需要的类别 06-08：200/812，2005年以前的？ 已有综述中阐述的内容，直接引用并总结 对所有新内容分类整理，得到需要的类别 对每一类中的文章，去除重复文章 尽量引用大会文章 2018/12/6

综述简介——内容提炼 分类整理，去除重复：150/360/700/800 2018/12/6

大纲 简介 流程 内容 总结 2018/12/6

综述流程 建立数据库 导入/出文档 执行查询 Data Storage Manager Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

综述流程 建立数据库 Data Storage Manager Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

综述流程 建立数据库 导入/出文档 Data Storage Manager Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

People/person/profile/gender 综述流程 People/person/profile/gender 建立数据库 导入/出文档 执行查询 Query Parser Query Optimizer Query Evaluator Execute Engine Data Storage Manager Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

综述流程 研究点 存储 索引 查询 存储策略 编码方案 查询改写 查询优化 查询算法 Data Storage Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

大纲 简介 流程 内容 总结 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

存储策略 关系表 Native 方式 混合方式 问题 查询 导出文档 Benchmark 文档类型 文本 数据 2018/12/6 。。。 attributes value name id 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

仅处理tag名为a和d的元素，可以减少处理的元素数量 编码方案 为什么使用编码 导航不可行 a1 a b1 b2 b3 c1 d d1 d2 e1 f1 a a1 d d1 d2 仅处理tag名为a和d的元素，可以减少处理的元素数量 Query Document 如何判断元素之间的关系？ 2018/12/6

编码方案 为什么使用编码 已有的解决方案 区间编码 a d (start, end, level) Query Document a d (1, 18 ,1) a1 a (12, 17 ,2) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 (10, 11 ,2) d d1 d2 e1 f1 (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) (start, end, level) Query Document a d (1, 18, 1) (5, 6, 3) (7, 8, 3) 1 18 5 6 7 8 2018/12/6

编码方案 为什么使用编码 已有的解决方案 区间编码 路径编码 a d Query Document a d 1 1.1 1.2 1.3 b1 1.2 b2 1.3 b3 1.4 c1 d d1 d2 e1 f1 1.2.1 1.2.2 1.4.1 1.4.2 Query Document a d 1 1.2.1 1.2.2 2018/12/6

编码方案 为什么使用编码 已有的解决方案 实际问题 文档更新 节点编码需要更新 插入叶子节点 插入非叶子节点 a d Query (1, 18 ,1) a1 a (12, 17 ,2) (2, 3 ,2) g b1 (4, 9 ,2) b2 b3 c1 g (10, 11 ,2) d d1 d2 e1 f1 (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) Query Document 1 a1 g g 1.1 b1 1.2 b2 b3 1.4 c1 g 1.3 d1 d2 e1 f1 1.2.1 1.2.2 1.4.1 1.4.2 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 无法避免重新编码 a d Query Document (10, 180 ,1) a1 a (120, 170 ,2) (20, 30 ,2) b1 (40, 90 ,2) b2 b3 c1 (100, 110 ,2) d d1 d2 e1 f1 (50, 60 ,3) (70, 80 ,3) (130, 140 ,3) (150, 160 ,3) Query Document 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 无法避免重新编码 a d Query Document (1, 18 ,1) a1 a (12, 17 ,2) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 g1 g2 (10, 11 ,2) d d1 d2 e1 f1 (110.01, 110.11, 3) (5, 6 ,3) (110.1101, 110.1111, 3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) (101, 110, 3) (111, 1000, 3) Query Document 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码ORDPATH 代价高 1 1.2.3 1.1 1.5 b1 b2 b3 b4 c1 d1 d2 e1 f1 1 a1 b2 b2 1.2.3 1.1 b1 b4 1.5 c1 1.2.1 d1 1.2.1.1 d2 1.2.1.3 1.3 e1 f1 1.5.1 1.5.3 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 可避免更新编码 N值计算代价高 1 a1 1 2 b2 2=2*1 7 c1 7=7*1 72 3 d1 5 d2 11 e1 13 f1 d1 6=3*2 10=5*2 77=11*7 91=13*7 17 170=17*10 N 3 4 5 N N1=1523 N1=1139 N2=72 N2=6 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 二进制位串 0 size=0 (1, 18 ,1) 0 size=0 a1 (12, 17 ,2) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 g (10, 11 ,2) d1 d2 e1 f1 (010011, 0100111, 001) (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) (01, 01001, 001) (0101, 011, 001) 将整数用二进制字符串表示 将插入整数变为插入字符串 19 size=0 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码 将整数用向量表示 (1, 18 ,1) a1 (12, 17 ,2) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 (10, 11 ,2) d1 d2 e1 f1 (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) 将整数用向量表示 将插入整数变为插入向量 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码 (1, 18 ,1) a1 (12, 17 ,2) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 (10, 11 ,2) d1 d2 e1 f1 (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码 14=(1,2) 18 ,1) a1 (12, 17 ,2) 1=(1,0) 10=(1,1) (2, 3 ,2) b1 (4, 9 ,2) b2 b3 c1 14=(1,2) (10, 11 ,2) 6=(2,1) d1 d2 e1 f1 18=(0,1) (5, 6 ,3) (7, 8 ,3) (13, 14 ,3) (15, 16 ,3) ((2,5), (2,1), 3) ((5,3), (3,2), 3) 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 基于图的编码 不支持更新 2018/12/6

编码方案 为什么使用编码 已有的解决方案 已有更新方法 基于图的编码 不支持更新 支持更新 2018/12/6

编码方案 为什么使用编码 已有的解决方案 实际问题 可能的研究点 树上编码的更新 图上编码的更新 什么情况下可在两个值之间插入无穷多个值 如何将不同区间用一个值表示 a1 d1 d2 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

索引 为什么使用索引 a d Query Document a d 2018/12/6 a1 b1 b2 b3 c1 d1 d2 e1 f1

索引 为什么使用索引 索引的类型 结构索引 值索引 Tag 索引 Structural summary 倒排表 b d Query f1 Query Document b b1 d d1 d2 b2 d3 a b c d e f b b1 d d1 d2 b2 2018/12/6

索引 为什么使用索引 索引的类型 结构索引 F&B index 1-index 2018/12/6

索引 为什么使用索引 索引的类型 结构索引 F&B index 1-index B B D D C 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

查询改写 什么是查询改写 用户提交查询Q 系统处理Q’ 2018/12/6

查询改写 什么是查询改写 为什么要查询改写 用户提交的查询表达能力有限：关键字查询 用户提交的查询有误 2018/12/6 a1 b1 b2 d3 c1 d1 d2 e1 f1 2018/12/6

查询改写 什么是查询改写 为什么要查询改写 查询改写的方式 基于用户反馈 结果反馈 查询反馈 隐式反馈：无用户参与 2018/12/6

用户反馈 1 2 3 4 … XML IR index Fagin query evaluation XML not(Fagin) 1. User submits query query evaluation XML not(Fagin) 1 2 3 4 … XML IR index Fagin 2. User marks relevant and nonrelevant docs 3. System finds best terms to distinguish between relevant and nonrelevant docs Feedback for XML IR: Start with keyword query Find structural expansions Create structural query 4. System submits expanded query 2018/12/6

用户反馈 User marks relevant result Possible dimensions: Content of result Path to the result P: article/body/sec/subsec article frontmatter body backmatter Tag+Content of other elements in the document D: //author[Baeza] //citation[Abiteboul] sec sec author „Baeza-Yates“ sec „Semistructured data…“ citation „Serge Abiteboul“ User marks relevant result subsec „XML has evolved…“ subsec p p p „With the advent of XSLT…“ Content of result Possible dimensions: C: XML 2018/12/6

用户反馈 XML Search Engine Feedback Dimensions … Scoring + Reranking query XML Search Engine results query + results expanded query feedback Feedback Dimensions Content Module Path Module Doc Module … reranked results Scoring + Reranking 2018/12/6

查询改写 什么是查询改写 为什么要查询改写 查询改写的方式 基于用户反馈 伪反馈 隐式反馈 查询扩展 又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展 隐式反馈 用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索. 查询扩展 黄静的工作 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

查询优化 种类 逻辑优化 物理优化 2018/12/6

查询优化 逻辑优化 语法优化 语义优化 2018/12/6

查询优化 物理优化 代价估计 单步代价估计 执行顺序 整体代价估计 √ 查询： a b c d e f 2018/12/6

内容介绍 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法 2018/12/6

查询算法-Twig查询处理 导航式 a d Query Document 2018/12/6 a1 b1 b2 b3 c1 d1 d2 e1 f1 Query Document 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 大量中间结果 a b d c a b d c 2 3 2 1 a e1 f1 2 1 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 后代指针回指 为什么？ a d a d a3d2 a3d3 r d1 a1 a3 a5 a2 a4 f1 d2 d3 a6 d4 d5 d6 a d a d a1(7,20) a2(14,19) a3(21,28) a4(22,27) a5(29,31) a6(32,40) d1(2,4) d2(23,24) d3(25,26) d4(33,34) d5(37,38) d6(43,44) cursor Mark 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 a d a d a3d2 a3d3 a6d4 a4d2 a4d3 r d1 a1 a3 a5 a2 a4 f1 d2 d3 a6 d4 d5 d6 a d a d a1(7,20) a2(14,19) a3(21,28) a4(22,27) a5(29,31) a6(32,40) d1(2,4) d2(23,24) d3(25,26) d4(33,34) d5(37,38) d6(43,44) a1(7,20) a2(14,19) a3(21,28) a4(22,27) a5(29,31) a6(32,40) 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 Result: XML Doc Query A1 A B2 A2 SC SB SA B2 Result: A1 B1 C1 A1 B2 C1 A2 B2 C1 C1 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 2018/12/6

查询算法-Twig查询处理 导航式 结构连接 二元 Path连接 整体匹配 Stack a Result of A//C Result of A//B a7 c8 a7 b4 a7 a7 c9 a7 b5 a7 c10 b5 b4 c11 c12 c10 c9 c8 a7 c11 Stack b Stack c a7 c12 2018/12/6

大纲 简介 流程 内容 展望 总结 2018/12/6

√ √ 研究展望 编码：图上可更新的编码方案 查询 数据集成 概率XML 时态XML 数据仓库 数据挖掘 数据压缩 分布式XML 静态文档：关键字查询，近似查询 数据流：关键字查询，近似查询 数据集成 概率XML 时态XML 数据仓库 数据挖掘 数据压缩 分布式XML √ 与OrientX不冲突 2018/12/6

总结 动机及准备工作 系统架构 存储 索引 查询 研究展望 存储策略 编码方案 查询改写 查询优化 查询算法 Data Storage Manager Manager Schema Index XML Data XML Query Query Result Execute Engine Data Definition XQuery XPath … Keyword 2018/12/6

Thank you ! 2018/12/6