The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
On the Query Evaluation in XML Databases
Abstract
With the growing importance of XML in data exchange, much research has been done in providing flexible query mechanisms to extract data from XML documents. A core operation for XML query processing is to find all occurrences of a twig pattern Q (or small tree) in a document T. Prior work has typically decomposed Q into binary structural relationships, such as parent-child and ancestor-descendant relations, or root-to-leaf paths. The twig matching is achieved by: (a) matching the binary relationships or paths against XML databases, and (b) using the join algorithms to stitch together all the matching binary relationships or paths. In the worst case, the time for doing joins can be exponential (in the number of query nodes or decomposed paths). In this chapter, we discuss a new algorithm for this task with no path joins involved. The time and space complexities of the algorithm are bounded by O (|T|·Qleaf) and O (Tleaf·Qleaf), respectively, where Tleaf stands for the number of the leaf nodes in T and Qleaf for the number of the leaf nodes in Q. Our experiments show that our method is efficient in supporting twig pattern queries.
Related Content
|
Renjith V. Ravi, Mangesh M. Ghonge, P. Febina Beevi, Rafael Kunst.
© 2022.
24 pages.
|
|
Manimaran A., Chandramohan Dhasarathan, Arulkumar N., Naveen Kumar N..
© 2022.
20 pages.
|
|
Ram Singh, Rohit Bansal, Sachin Chauhan.
© 2022.
19 pages.
|
|
Subhodeep Mukherjee, Manish Mohan Baral, Venkataiah Chittipaka.
© 2022.
17 pages.
|
|
Vladimir Nikolaevich Kustov, Ekaterina Sergeevna Selanteva.
© 2022.
23 pages.
|
|
Krati Reja, Gaurav Choudhary, Shishir Kumar Shandilya, Durgesh M. Sharma, Ashish K. Sharma.
© 2022.
18 pages.
|
|
Nwosu Anthony Ugochukwu, S. B. Goyal.
© 2022.
23 pages.
|
|
|