Deferred evaluation of path queries on hierarchical data

Andrzej Sikorski, Jarosław Ciemnoczłowski


This paper is dealing with the on-line processing of queries on hierarchical data. We make use of the structural join method, that we modify so as to achieve the minimum number of I/O operations required for successful identification of the result set. Our technique along with the application server hosting model and distributed architecture allows efficient implementation of information systems extensively using hierarchical data.


multi-tier architectures; distributed computing; XML; structural join

Full Text:



Fomichev A., Grinev M., Kuznetsov S.D.: Sedna: A Native XML DBMS. In Wiedemann J., Tel G., Pokorny J., Bielikova M., & Stuller J. (eds) Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2006, January 21-27 2006, Merin, Czech Republic, Berlin: Springer, (LNCS), p. 272-281.

Pleshachkov P., Chardin P., Kuznetsov S.D.: A DataGuide-Based Concurrency Control Protocol for Cooperation on XML Data. In Eder J., Haav H.-M., Kalja A., & Penjam J. (eds) Advances in Databases and Information Systems, 9th East European Conference, ADBIS 2005, September 12-15, Tallinn, Estonia, Berlin: Springer, (LNCS), p. 268-282.

Tropashko V.: Nested Intervals for Tree Encoding in SQL, ACM SIGMOD Record, 34(2), p. 47-52.

Wu X., Lee M.L., Hsu W.: A Prime Number Labeling Scheme for Dynamic Ordered XML Trees. Proceedings of the 20th International Conference on Data Engineering, ICDE 2004, 30 March - 2 April, 2004 Boston, MA, USA. IEEE Computer Society, p.66-78.

O'Neil P., O'Neil E., Shankar P., Cseri I., Schaller G., Westbury N.: ORDPATHs: Insert-Friendly XML Node Labels, SIGMOD, Paris 2004, p. 903-908.

Al-Khalifa S., Jagadish H.V., Koudas N., Patel J., Srivastava D., Wu Y.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching. Proceedings of the 18th International Conference on Data Engineering, ICDE 2002, 26 February - 1 March 2002, San Jose, CA. IEEE Computer Society, p. 141-152.

Jagadish H.V., Al-Khalifa S., Chapman A., Lakshmanan L.V.S, Nierman A., Paparizos S., Patel J.M., Srivastava D., Wiwarwattana N., Wu Y.: A Native XML Database, VLDB Journal 11(4) 2002, p. 274-291.

Yuqing Wu, Jignesh M. Patel, H. V. Jagadish: Structural Join Order Selection for XML Query Optimization. In Umeshwar Dayal, Krithi Ramamritham, T. M. Vijayaraman (Eds.): Proceedings of the 19th International Conference on Data Engineering, ICDE 2003, March 5-8, 2003, Bangalore, India. IEEE Computer Society, p. 443-454.

Knuth D.E.: The Art of Computer Programming. Vol. 2. Seminumerical algorithms. Addison-Wesley, 1969.

Box D., Hejlsberg A: LINQ: .NET Language-Integrated Query, MSDN, Microsoft Corp., February 2007.