Querying and maintaining ordered XML data using relational databases
Abstract
Although data stored in XML is of increasing importance, most existing data repositories are still managed by relational database systems. In light of this, recent XML database research has focused on extending relational database systems to handle XML data efficiently. While there are many issues in processing XML data efficiently, containment queries are the queries that often appear and need to be optimized. Recently, structural joins have been proposed to process containment queries efficiently. To date, structural join algorithms are mostly based on stacks and/or external B-Tree indices. Most of these prototypes have been implemented on object databases. This paper proposes an efficient structural join algorithm that can be implemented on top of existing relational databases. Experiments show that our method performs far more superior than previous work in both queries and updates.
References
[1]
Al-Khalifa, S., Jagadish, H. V., Koudas, N. & Patel, J. M. (2002), Structural Joins: A Primitive for Efficient XML Query Pattern Matching, in 'ICDE'.]]
[2]
Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M. & Zito, J. (2002), Two simplified algorithms for maintaining order in a list, in 'ESA', Vol. 2461 of Lecture Notes in Computer Science, Rome, Italy, pp. 152--164.]]
[3]
Bohannon, P., Freire, J., Roy, P. & Simeon, J. (2002), From XML schema to relations: A cost-based approach to XML storage, in 'ICDE'.]]
[4]
Bruno, N., Koudas, N. & Srivastava, D. (2002), Holistic twig joins: optimal XML pattern matching, in M. J. Franklin, B. Moon & A. Ailamaki, eds, 'SIGMOD Conference', ACM, pp. 310--321.]]
[5]
Carey, M. J., Florescu, D., Ives, Z. G., Lu, Y., Shanmugasundaram, J., Shekita, E. J. & Subramanian, S. N. (2000), XPERANTO: Publishing Object-Relational Data as XML, in 'WebDB (Informal Proceedings)', pp. 105--110.]]
[6]
Chaudhuri, S., Kaushik, R. & Naughton, J. F. (2003), On Relational Support for XML Publishing: Beyond Sorting and Tagging, in A. Y. Halevy, Z. G. Ives & A. Doan, eds, 'SIGMOD Conference', ACM, pp. 611--622.]]
[7]
Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V. J. & Zaniolo, C. (2002), Efficient structural joins on indexed XML documents, in 'VLDB Conference', Berlin, Germany, pp. 263--274.]]
[8]
Choi, B., Mahoui, M. & Wood, D. (n.d.), On the Optimality of Holistic Algorithms for Twig Queries, in 'DEXA', pp. 28--37.]]
[9]
Cohen, E., Kaplan, H. & Milo, T. (2002), Labeling Dynamic XML Trees, in 'PODS Conference', ACM Press, New York, pp. 271--281.]]
[10]
DeHaan, D., Toman, D., Consens, M. P. & zsu, M. T. (2003), A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding, in A. Y. Halevy, Z. G. Ives & A. Doan, eds, 'SIGMOD Conference', ACM, pp. 623--634.]]
[11]
Deutsch, A., Fernandez, M. & Suciu, D. (1999), Storing semistructured data with STORED, in 'SIGMOD Conference', pp. 431--442.]]
[12]
Dietz, P. F. (1982), Maintaining order in a linked list, in 'STOC', pp. 122--127.]]
[13]
ElSayed, M., Dimitrova, K. & Rundensteiner, E. A. (2003), Efficiently Supporting Order in XML Query Processing, in 'WIDM'.]]
[14]
Fernández, M., Kadiyska, Y., Suciu, D., Morishima, A. & Tan, W.-C. (2002), 'SilkRoute: A framework for publishing relational data in XML', ACM Transactions on Database Systems27(4), 438--493.]]
[15]
Florescu, D. & Kossmann, D. (1999), 'Storing and querying XML data using an RDMBS', IEEE Data Engineering Bulletin22(1), 27--34.]]
[16]
Goldman, R. & Widom, J. (1998), DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, in 'VLDB Conference', pp. 436--445.]]
[17]
Grust, T., van Keulen, M. & Teubner, J. (2003), Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps, in 'VLDB Conference', pp. 524--525.]]
[18]
Haifeng, J., Lu, H., Wei, W. & Ooi, B. C. (2003), XR-Tree: Indexing XML Data for Efficient Structural Join, in 'ICDE', IEEE Computer Society.]]
[19]
Halverson, A., Burger, J., Galanis, L., Kini, A., Krishnamurthy, R., Rao, A. N., Tian, F., Viglas, S., Wang, Y., Naughton, J. F. & DeWitt, D. J. (2003), Mixed Mode XML Query Processing, in 'VLDB Conference', pp. 225--236.]]
[20]
Jagadish, H. V., Al-Khalifa, S., Chapman, A., Lakshmanan, L. V. S., Nierman, A., Paparizos, S., Patel, J. M., Srivastava, D., Wiwatwattana, N., Wu, Y. & Yu, C. (2002), 'Timber: A native xml database', VLDB Journal11(4), 274--291.]]
[21]
Jiang, H., Wang, W., Lu, H. & Yu, J. X. (2003), Holistic Twig Joins on Indexed XML Documents, in 'VLDB Conference', pp. 273--284.]]
[22]
Krishnamurthy, R., Kaushik, R., Naughton, J. F. & Chakaravarthy, V. T. (2004), Recursive xml schemas, recursive xml queries, and relational storage: Xml-to-sql query translation, in 'ICDE'.]]
[23]
Manolescu, I., Florescu, D. & Kossmann, D. (2001), Answering XML Queries on Heterogeneous Data Sources, in 'VLDB Conference', pp. 241--250.]]
[24]
O'Neil, P. E., O'Neil, E. J., Shankar Pal, I. C., Schaller, G. & Westbury, N. (2004), ORDPATHs: Insert-Friendly XML Node Labels, in 'SIGMOD Conference', ACM, pp. 903--908.]]
[25]
Schmidt, A., Waas, F., Kersten, M. L., Carey, M. J., Manolescu, I. & Busse, R. (2003), Assessing XML data management with XMark, in S. Bressan, A. B. Chaudhri, M.-L. Lee, J. X. Yu & Z. Lacroix, eds, 'EEXTT', Vol. 2590 of Lecture Notes in Computer Science, Springer, pp. 144--145.]]
[26]
Shanmugasundaram, J., Kiernan, J., Shekita, E. J., Fan, C. & Funderburk, J. (2001), Querying XML Views of Relational Data, in 'VLDB Conference', pp. 261--270.]]
[27]
Shanmugasundaram, J., Shekita, E. J., Kiernan, J., Krishnamurthy, R., Viglas, S., Naughton, J. F. & Tatarinov, I. (2001), 'A General Techniques for Querying XML Documents using a Relational Database System', SIGMOD Record30(3), 20--26.]]
[28]
Shanmugasundaram, J., Tufte, K., Zhang, C., He, G., DeWitt, D. J. & Naughton, J. F. (1999), Relational databases for querying xml documents: Limitations and opportunities, in 'VLDB Conference', pp. 302--314.]]
[29]
Shimura, T., Yoshikawa, M. & Uemura, S. (1999), Storage and Retrieval of XML Documents Using Object-Relational Databases, in 'DEXA', pp. 206--217.]]
[30]
Tatarinov, I., Viglas, S. D., Beyer, K., Shanmugasundaram, J., Shekita, E. & Zhang, C. (2002), Storing and Querying Ordered XML Using a Relational Database System, in 'SIGMOD Conference'.]]
[31]
Wu, X., Lee, M. L. & Hsu, W. (2004), A Prime Number Labeling Scheme for Dynamic Ordered XML Trees, in 'ICDE'.]]
[32]
Yoshikawa, M., Amagasa, T., Shimura, T. & Uemura, S. (2001), 'XRel: a path-based approach to storage and retrieval of XML documents using relational databases', TOIT1(1), 110--141.]]
[33]
Zhang, C., Naughton, J. F., DeWitt, D. J., Luo, Q. & Lohman, G. M. (2001), On supporting containment queries in relational database management systems, in 'SIGMOD Conference'. *citeseer.nj.nec.com/zhang01supporting.html]]
Index Terms
- Querying and maintaining ordered XML data using relational databases
Recommendations
Storing and querying XML data using denormalized relational databases
XML database systems emerge as a result of the acceptance of the XML data model. Recent works have followed the promising approach of building XML database management systems on underlying RDBMS’s. Achieving query processing performance reduces to two ...
Querying relational databases through XSLT
XML has been accepted as a universal format for data interchange and publication. It can be applied in the applications in which the data of a database needs to be viewed in XML format so that the data being viewed takes more semantics and is easily ...
Storing and querying ordered XML using a relational database system
SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of dataXML is quickly becoming the de facto standard for data exchange over the Internet. This is creating a new set of data management requirements involving XML, such as the need to store and query XML documents. Researchers have proposed using relational ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Australian Computer Society, Inc.
Australia
Publication History
Published: 30 January 2005
Qualifiers
- Article
Conference
ADC '05
Acceptance Rates
Overall Acceptance Rate 98 of 224 submissions, 44%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 899Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)7
Reflects downloads up to 28 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in