基于文档类型定义的XML数据流关键字搜索方法

摘要

本发明属于数据管理技术领域，具体为一种基于文档类型定义的XML数据流关键字搜索方法。本发明包括：将关键字搜索的语义定义为语义独立的最小最低公共祖先，将查询结果定义为语义独立的最小连通树，从而能够有效处理XML数据流；对纯粹关键字搜索语法进行简单扩充，每一个搜索项由一个关键字和包含该关键字的标签组成；基于文档类型定义，将关键字搜索细化为查询图，在查询图的基础上构造支持正向状态转移和状态回溯的查询状态机，对XML数据流和返回结果缓存进行单遍扫描和处理。本发明能够有效支持XML格式数据流的关键字搜索，搜索语法简单、搜索效率高，可应用于互联网内容监测、互联网信息发布与订阅、Web服务消息过滤等领域。

主权项

1.一种基于文档类型定义的XML数据流关键字搜索方法，其特征在于具体步骤如下： (1)将用户提交的关键字搜索定义为XML搜索项的集合，每一个XML搜索项由一 个关键字和包含该关键字的标签组成；将关键字搜索的语义定义为语义独立的最小最低公 共祖先，记为MISLCA，将查询结果定义为语义独立的最小连通树，记为MIMCT；从而 为用户提供友好搜索界面； (2)将XML数据流的文档类型构造为一个简化DTD图； (3)将用户提交的关键字和XML数据流的简化DTD图结合在一起，找出从DTD图 的根到关键字的所有可能的查询路径，进而通过共享所有可能查询路径的前缀，构造关键 字的查询图； (4)在查询图的基础上构造支持正向状态转移和状态回溯的查询状态机，利用查询 状态机，对XML数据流和返回结果的缓存进行单遍扫描和查询处理； (5)为了进一步提高系统性能，定义查询状态机的最终接受状态，在遇到最终接受 状态时，状态机停止执行： 其中，所述的XML关键字搜索项、XML关键字搜索语义以及返回结果定义如下： 定义1.搜索项，简称为ST：一个搜索项t是一个XML文档标签和它包含的关键字组 成的对，表示为t＝s∶w，其中，s表示XML文档标签，w表示标签s包含的关键字；关键字 可以为空；用户提交的查询Q(S)是搜索项的集合S＝t₁，t₂，…，t_n； 定义2.语义独立的最小最低公共祖先，简称为MISLCA：给定一颗XML树T，V表示 树T中所有结点的集合；n_d∈V，n_a∈V，如果n_d是n_a的后裔或等于n_a，称为n_d与n_a具有 后裔或自身关系，记为n_d≤n_a；如果n_d≠n_a，则记为n_d＜n_a；再给定一个关键字列表w₁，…，w_k， 假定用S_i表示对应关键字w_i的结点集合，S_i∈V，即S_i中元素的标记直接包含关键字w_i；将 关键字列表w₁，…，w_k的最低公共祖先(LCA)表示为LCA(S₁，…，S_k)，将最小最低公共祖先 (SLCA)表示为SLCA(S₁，…，S_k)；假定v₁，…v_k是S₁，…，S_k的所有MISLCA，记为 MISLCA(S₁，…，S_k)；开始MISLCA(S₁，…，S_k)为空，那么， (1)SLCA(S₁，…，S_k)都是S₁，…，S_k的MISLCA，即MISLCA(S₁，…，S_k)＝MISLCA(S₁，…，S_k)+ SLCA(S₁，…，S_k)； (2)另外，如果n_mislca是S₁，…，S_k的MISLCA，即MISLCA(S₁，…，S_k)＝MISLCA(S₁，…，S_k)+ n_mislca，当且仅当 ■n_mislca∈LCA(S₁，…，S_k)-MISLCA(S₁，…，S_k)，并且 ■n′∈LCA(S₁，…，S_k)-MISLCA(S₁，…，S_k)(n′≠n_mislca)，则n_mislca＜n′，并且， ■以n_mislca为根的最小连通树与SLCA(S₁，…，S_k)为根的最小连通树的交集为空； (3)重复执行步骤(2)，直到没有n_mislca满足(2)中的条件； 定义3.语义独立的最小连通树，简称为MIMCT：给定一颗XML树T以及一个关键字列表 w₁，…，w_k，w₁，…，w_k的最小连通树T_MIMCT是指以该关键字列表的MISLCA为根的、连接MISLCA 包含的所有关键字的最小子树； 所述的简化DTD图的定义如下： 定义4.简化DTD可以看作一个有根的有向图SDG＝(V，E)，称为简化DTD图，其中， V表示有向图的所有结点构成的集合，EV×V是连接结点的边； (1)r∈V是DTD图指定的根，对于任一结点v∈V，都存在惟一的从r到v的有向路径； (2)结点v∈V对应元素或属性，边e∈E表示结点之间的包含父子关系，结点的标签 名是元素或属性的名字； 所述的关键字查询图的定义、构造方法如下： 定义5.查询图QG是一个9元组QG＝(V’，E’，∑’，λ’，η，ρ’，root’，S’，W) (1)V’表示结点的有限集合； (2)∑’表示结点标签的有限集合； (3)λ’：V’→∑是标签函数；λ(n)返回结点n的标签名字； (4)ρ’：V’→∑’∪ε是父亲函数，ρ’(n)返回n的父亲结点； (5)root’∈V’是G’的根； (6)W＝w₁，…，w_n表示关键字列表； (7)S’＝s₁，…，s_m是直接包含W的结点； 查询图的构造方法为：给定一个输入XML树T的DTD，以及一个关键字查询Q(S)，Q(S) 包含的搜索项为t₁，t₂，t₃…t_n，搜索项中的关键字为w₁，…，w_n，包含关键字的标签为 s_i，…，s_mm≤n，构造查询图的步骤如下： (1)构造给定DTD的简化DTD图SDG； (2)V是SDG中的结点集合，r∈V是SDG的根，对于每一个s_i∈V，可以找出从r到 s_i的惟一有向路径P_i，从而得到一个路径集合P＝P₁，…，P_m，然后将每一个关键字w连接到 路径中包含它的标签上； (3)对每一个路径P_i∈P，通过共享它们的前缀将它们组合在一起，即可以得到查询 图； 与所述的XML关键字查询图相关的定理1和定理2如下： 定理1.查询图QG是简化DTD图SDG＝(V，E)的同根子图，其中，G’G，V’V， 并且E’E∩(V’×V’)； 定理2.给定一个输入XML树T和一个关键字列表W＝w₁，…，w_k，其中，V_T表示T中的结 点集合，S＝s₁，…，s_k是包含关键字的结点；假定XML树T的简化DTD是SDG，并且由关键字 W和SDG生成的查询图是QG；那么，如果XML树T与QG匹配，则与关键字W匹配，并且W 在QG上的MISLCA对应于W在XML树T上的MISLCA； 所述的查询状态机的定义如下： 定义6.查询状态机，简称为QSM；是根据查询图G’(V’，E’，∑’，λ’，η’，ρ’，root’， S’，W)构造的元组QSM(Q，r，q₀，F，I，δ_s，δ_e，∑，λ，ρ，S)，其中： (1)Q是有限状态标识符，包括q₀和对应于G’中结点V’的状态； (2)q₀是QSM的初始状态； (3)r是Q的一个成员，对应于G’中的root’； (4)F是Q的一个子集，表示QSM的接受状态，对应于G’中的MISLCA； (5)I是输入事件，其中tagName表示结点测试名，type表示事件类型，事件类型 有startElement和closeElement； (6)δ_s和δ_e表示转移函数，分别对应于startElement和endElement事件；这些转 移函数计算当前状态q的下一个状态q’，q称为q’的父状态，q’称为q的孩子状态； (7)∑表示有限输入符号，对应于G’中的∑’； (8)λ：Q-{q₀}→∑是名字函数，返回状态的标签名； (9)ρ：Q→∑∪ε是父亲函数，ρ(q)返回结点q的父状态； (10)W是Q的子集，对应于一系列关键字。