OrientX4.0系统开发报告 XML Group July 25, 2009

XML Keyword Search Keyword: Stevens, Addison-Wesley <?xml version="1.0" encoding="GB2312"?> <bib> <book year="1994"> <title>TCP/IP Illustrated</title> <author> <last>Stevens</last> <first>W.</first> </author> <publisher>Addison-Wesley</publisher> <price>65.95</price> </book> ...... <book year="1992"> <title>Advanced Programming in the Unix environment</title> Keyword: Stevens, Addison-Wesley <book year="1994"> <title>TCP/IP Illustrated</title> <author> <last>Stevens</last> <first>W.</first> </author> <publisher>Addison-Wesley</publisher> <price>65.95</price> </book> <book year="1992"> <title>Advanced Programming in the Unix environment</title> <author> <last>Stevens</last> <first>W.</first> </author> <publisher>Addison-Wesley</publisher> <price>65.95</price> </book>

大纲 OrientX4.0已完成的工作 XML文档的SAX解析 XML文档的Dewey编码 存储和索引 SLCA 算法的实现

大纲 OrientX4.0已完成的工作 XML文档的SAX解析 XML文档的Dewey编码 存储和索引 SLCA 算法的实现

OrientX4.0系统结构 Data manager Schema Manager Index Storage XML Documents Query Result Query/ Keywords Update XPath Data Definition Address Records XQuery Element Node Keyword-search Coder Execute Engine xml文档的解析 Storage Manager

SAX简介 SAX（Simple API for XML） SAX是一种解析XML文件的技术。 SAX是一组程序接口。 使用事件基础来处理XML文件，目前大部分XML解析器除了支持DOM外，都会一并支持SAX解析。 SAX是一组程序接口。 可以将XML文件视为字符串流的数据，在读取XML元素时触发一系列事件，只需撰写所需的事件处理程序，就可以分析或取得XML元素。

SAX 图例 XML文件在经过SAX解析后，产生一系列事件，我们可以建立事件处理程序来处理这些事件。 <book> <title>TCP/IP</title> <author> Stevens</author> <publisher>Addison</publisher> <price>65.95</price> </book> SAX解析器 事件处理程序 XML 文件 startElement (book) startElement (title) characters (TCP/IP) . . . . . . . 解析文件 产生事件

SAX主要事件 startDocument事件 startElement事件 Characters事件 endElement事件 attribute a; a.getLength(); a.getQname(); a.getValue(); Characters事件 endElement事件 endDocument事件

SAX解析举例 <?xml version="1.0" encoding="GB2312"?> <bib> book title author year 1994 TCP/IP last first publisher price Addison 65.95 Stevens W. <?xml version="1.0" encoding="GB2312"?> <bib> <book year="1994"> <title>TCP/IP Illustrated</title> <author> <last>Stevens</last> <first>W.</first> </author> <publisher>Addison-Wesley</publisher> <price>65.95</price> </book> </bib>

大纲 OrientX4.0已完成的工作 XML文档的SAX解析 xml文档的Dewey编码 存储和索引 SLCA 算法的实现

OrientX4.0系统结构 Data manager Schema Manager Index Storage XML Documents Query Result Query/ Keywords Update XPath Data Definition Address Records XQuery Element Node Keyword-search Coder Execute Engine xml文档的编码 Storage Manager

Dewey编码 int dewey[51]={0,-1,-1,…,-1} 对元素、属性、属性值、文本进行编码 举例 bib book title author year 1994 TCP/IP last first publisher price Addison 65.95 Stevens W. 0.0 0.0.0 0.0.1 0.0.2 0.0.4 0.0.3 0.0.0.0 0.0.1.0 0.0.2.0 0.0.2.1 0.0.3.0 0.0.4.0 0.0.2.0.0 0.0.2.1.0

编码举例 初始情况：int dewey[51]={0,-1,-1,-1，…，-1} start: bib {1,0,………} start: book {2,0,0,……..} start: year {3,0,0,0,……} start:1994 {4,0,0,0,0,…….} end:1994 {3,0,0,0,0,-1,……} end: year {2,0,0,0,-1,-1} start: title {3,0,0,1,……} bib book title author year 1994 TCP/IP last first publisher price Addison 65.95 Stevens W. <?xml version="1.0" encoding="GB2312"?> <bib> <book year="1994"> <title>TCP/IP Illustrated</title> <author> <last>Stevens</last> <first>W.</first> </author> <publisher>Addison-Wesley</publisher> <price>65.95</price> </book> </bib> 0.0 0.0.0 0.0.1 0.0.0.0

大纲 OrientX4.0已完成的工作 XML文档的SAX解析 xml文档的Dewey编码 存储和索引 SLCA 算法的实现

OrientX4.0系统结构 Data manager Schema Manager Index Storage XML Documents Query Result Query/ Keywords Update XPath Data Definition Address Records XQuery Element Node Keyword-search Coder Execute Engine Dewey编码的存储 与索引 Storage Manager

编码的组织 目标：给出要查询的关键字迅速找到对应的Dewey编码 hash倒排表存储编码 几点要注意的问题 关键字的分割 无意义关键字

倒排表结构 图 hash inverted list

一个例子 key: Stevens; Deweycode: 0.0.2.0.0 hash(Stevens)=((S*31+t)*31+…)/Nhash=552 552 NULL Stevens 0.0.2.0.0 5

一个例子 key: Stevens; Deweycode: 0.1.2.0.0 hash(Stevens)=552 552 Stevens NULL Stevens 0.0.2.0.0 5 5 0.1.2.0.0 NULL

一个例子 key: xxx, 0.1.3.0 hash(xxx)=552 552 Stevens 5 5 0.0.2.0.0 0.1.2.0.0 NULL xxx 4 0.1.3.0 NULL NULL

一些问题 关键字的分割 意义不大的关键字 文本结点 属性值结点 选择合适的分隔符： 空格，逗号，冒号，…. 定冠词 连词 …… 可能含有多个关键字

大纲 OrientX4.0已完成的工作 XML文档的SAX解析 xml文档的Dewey编码 存储和索引 SLCA 算法的实现

OrientX4.0系统结构 Data manager Schema Manager Index Storage XML Documents Query Result Query/ Keywords Update XPath Data Definition Address Records XQuery Element Node Keyword-search Coder Execute Engine SLCA算法的实现 Storage Manager

SLCA的实现 Naïve 方法 对所有关键字的组合求LCA 从结果中去掉祖先结点 剩余的就是SLCA结点 Key S Stevens：0.0.2.0.0，0.1.2.0.0 Key A Addison-Wesley：0.0.3.0，0.1.3.0

Stack算法 Key S Stevens：0.0.2.0.0，0.1.2.0.0 Key A Addison-Wesley：0.0.3.0，0.1.3.0 S A T F 2 (a) node0.0.2.0.0 bib book author last first publisher …. Addison Stevens W. price 65.95 …… 0.0 0.1 0.0.2 0.0.3 0.0.2.0 0.0.3.0 0.1.3.0 0.0.2.0.0 0.1.2.0.0

Stack算法 Key S Stevens：0.0.2.0.0，0.1.2.0.0 Key A Addison-Wesley：0.0.3.0，0.1.3.0 S A S A T F 2 T F 2 2 T F T F (a) node0.0.2.0.0 F T 3 bib book author last first publisher …. Addison Stevens W. price 65.95 …… (b) node0.0.3.0 0.0 0.1 0.0.2 0.0.3 0.0.2.0 0.0.3.0 0.1.3.0 0.0.2.0.0 0.1.2.0.0

Stack算法 Key S Stevens：0.0.2.0.0，0.1.2.0.0 Key A Addison-Wesley：0.0.3.0，0.1.3.0 S A S A T F 2 T F 2 2 T F T F (a) node0.0.2.0.0 F T 3 T F F bib book author last first publisher …. Addison Stevens W. price 65.95 …… (b) node0.0.3.0 report 0.0 as a slca 0.0 0.1 T F 2 1 0.0.2 0.0.3 1 T F (c) node0.1.2.0.0 0.0.2.0 0.0.3.0 F T 3 1 0.1.3.0 1 T F 0.0.2.0.0 0.1.2.0.0 (d) node0.1.3.0 report 0.1 as a slca

Thanks！