Tree inclusion algorithm, signatures and evaluation of path-oriented queries

ABSTRACT

In this paper, a method to evaluate path-oriented queries in document databases is proposed. The main idea of this method is to handle the evaluation of a path-oriented query as a tree inclusion problem. A new algorithm for tree-inclusion is discussed, which integrates a top-down process into a bottom-up searching strategy. On the one hand, the algorithm can be arranged to access the data on disk page-wise and fits therefore within a database environment. On the other hand, the algorithm can be combined with the signature indexing technique to cut off useless subtree inclusion checking as early as possible. Experiments have been conducted to compare this method with some existing approaches, which shows that the integration of the signatures into the top-down tree inclusion is highly promising.

REFERENCES

• 1: Laurent Alonso , René Schott, On the Tree Inclusion Problem, Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science, p.211-221, August 30-September 03, 1993
• 2: Weimin Chen, More efficient algorithm for ordered tree inclusion, Journal of Algorithms, v.26 n.2, p.370-385, feb. 1998 [doi>10.1006/jagm.1997.0899 ]
• 3: S. Christodoulakis and C. Faloutsos, "Design consideration for a message file server," IEEE Trans. Software Engineering, 10(2) (1984) 201--210.
• 4: D. Florescu and D. Kossman, Storing and Querying XML Data using an RDBMS, IEEE Data Engineering Bulletin, 22(3), 1999.
• 5: Pekka Kilpelainen , Heikki Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, v.24 n.2, p.340-356, April 1995 [doi>10.1137/S0097539791218202]
• 6: Thorsten Richter, A New Algorithm for the Ordered Tree Inclusion Problem, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.150-166, June 30-July 02, 1997
• 7: Sangwon Park , Hyoung-Joo Kim, A New Query Processing Technique for XML Based on Signature, Proceedings of the 7th International Conference on Database Systems for Advanced Applications, p.22, April 18-20, 2001
• 8: C. Seo, S. Lee, and H. Kim, An Efficient Index Technique for XML Documents Using RDBMS, Information and Software Technology 45(2003) 11--22, Elsevier Science B.V.
• 9: Eleni Tousidou , Panayiotis Bozanis , Yannis Manolopoulos, Signature-based structures for objects with set-valued attributes, Information Systems, v.27 n.2, p.93-121, April 2002 [doi>10.1016/S0306-4379(01)00047-3 ]
• 10: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 11: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 12: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 13: http://www.connexor.com/demos/index.html.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Performance

Keywords:
XML document, databases, indexes, path oriented queries, signatures, tree inclusion