|
|||||
|
|
Path-partitioned encoding supports wildcard-awareness twig queries |
|
| Authors: | Xiao-shuang Xu Yu-cai Feng Feng Wang |
| Institution: | 1. School of Computer, Huazhong University of Science and Technology, Wuhan 430074, P. R. China;School of Computer, Huanggang Normal University, Huanggang 438000, Hubei, P. R. China 2. School of Computer, Huazhong University of Science and Technology, Wuhan 430074, P. R. China;Technic Pre-research Department, Dameng Database Company Limited, Wuhan 430074, P. R. China 3. School of Computer, Huanggang Normal University, Huanggang 438000, Hubei, P. R. China |
| Abstract: | Finding all occurrences of a twig query in an XML database is a core operation for efficient evaluation of XML queries. It is important to effectively handle twig queries with wildcards. In this paper, a novel path-partitioned encoding scheme is proposed for XML documents to capture paths of all elements, and a twig query is modeled as an XPattern extended from tree pattern. After definition, simplification, normalization, verification and initialization of the XPattern, both work sets and a join plan are generated. According to these measures, an effective algorithm to answer for a twig query, called DMTwig, is designed without unnecessary elements and invalid structural joins. The algorithm can adaptively deal with twig queries with branch(]), child edge(/), descendant edge(//), and wildcard(*)synthetically. We show that path-partitioned encoding scheme and XPattern guarantee the I/O and CPU optimality for twig queries. Experiments on representative data set indicate that the proposed solution performs significantly. |
| Keywords: | XML tree pattern structural join encoding scheme twig query |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ | |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 | |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 | |