Article

TAX: A Tree Algebra for XML

Authors:

H. V. Jagadish,

Laks V. S. Lakshmanan,

Divesh Srivastava,

Keith ThompsonAuthors Info & Claims

DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages

Pages 149 - 164

Published: 08 September 2001 Publication History

Abstract

Querying XML has been the subject of much recent investigation. A formal bulk algebra is essential for applying database-style optimization to XML queries. We develop such an algebra, called TAX (Tree Algebra for XML), for manipulating XML data, modeled as forests of labeled ordered trees. Motivated both by aesthetic considerations of intuitiveness, and by efficient computability and amenability to optimization, we develop TAX as a natural extension of relational algebra, with a small set of operators. TAX is complete for relational algebra extended with aggregation, and can express most queries expressible in popular XML query languages. It forms the basis for the Timber XML database system currently under development by us.

References

[1]

S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. Journal on Digital Libraries, 1(1), 1996.

[2]

S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, D. Srivastava, and Y. Wu. Structural joins: Efficient matching of XML query patterns. In Proc. ICDE, 2002.

[3]

D. Beech, A. Malhotra, and M. Rys. A formal data model and algebra for XML. W3C XML Query Working Group Note, Sep. 1999.

[4]

C. Beeri and Y. Tzaban. SAL: An algebra for Semi-Structured Data and XML. In Proc. SIGMOD WebDB workshop, June 1999.

[5]

P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In Proc. SIGMOD, June 1996.

[6]

D. Chamberlin, J. Robie, and D. Florescu. Quilt: An XML query language for heterogeneous data sources. In Proc. SIGMOD WebDB workshop, May 2000.

[7]

D. Chamberlin, D. Florescu, J. Robie, J. Simeon, and M. Stefanescu. XQuery: A query language for XML. W3C Working Draft. 15 Feb. 2001.

[8]

E. F. Codd. A relational model of data for large shared data banks. CACM 13(6), pages 377-387, 1970.

[9]

V. Christophides, S. Cluet, and J. Simeon. On wrapping query languages and efficient XML integration. In Proc. SIGMOD, pages 141-152, 2000.

[10]

M. P. Consens and A. O. Mendelzon. Graphlog: A visual formalism for real life recursion. In Proc. PODS, Apr. 1990.

[11]

A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. A query language for XML. In Proc. WWW, 1999.

[12]

M. Fernandez, J. Simeon, and P. Wadler. An algebra for XML query. In Proc. FSTTCS, Delhi, December 2000.

[13]

M. Gyssens, J. Paredaens, and D. Van Gucht. A grammar-based approach towards unifying hierarchical data models. In Proc. SIGMOD, pages 263-272, 1989.

[14]

C. M. Hoffmann and M. J. O'Donnell. Pattern-matching in trees. JACM Vol. 29, pages 68-95, 1982.

[15]

H. Hosoya and B. C. Pierce. XDuce: A Typed XML Processing Language. In Proc. SIGMOD WebDB workshop, May 2000.

[16]

B. Ludascher, Y. Papakonstantinou, and P. Velikhov. Navigation-driven evaluation of virtual mediated views. In Proc. EDBT, pp. 150-165, 2000.

[17]

Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In Proc. PODS, 2000.

[18]

J. Paradaens, J. Van den Bussche, D. Van Gucht, et al. An Overview of GOOD ACM SIGMOD Record, March 1992.

[19]

J. Shanmugasundaram, H. Gang, K. Tufte, C. Zhang, D. DeWitt, and J. Naughton. Relational databases for querying XML documents: Limitations and opportunities. In Proc. VLDB, 1999.

[20]

B. Subramanian, T. Leung, S. Vandenberg, S. Zdonik. The AQUA approach to querying lists and trees in object-oriented databases. In Proc. ICDE, 1995.

[21]

I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld. Updating XML. In Proc. SIGMOD, 2001.

[22]

World Wide Web Consortium. The document object model. http://www.w3.org/DOM/

[23]

C. Zhang, J. Naughton, D. DeWitt, Q. Luo, and G. Lohman. On supporting containment queries in relational database management systems. In Proc. SIGMOD, May 2001.

Cited By

Jamkhedkar PJohnson TKanza YShaikh AShankaranarayanan NShkapenyuk VDas GJermaine CBernstein P(2018)A Graph Database for a Virtualized Network InfrastructureProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3190653(1393-1405)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3190653
Jamkhedkar PJohnson TKanza YShaikh AShankarnarayanan NShkapenyuk VWoodhull GChirkova RYang JSuciu D(2017)Virtualized Network Service Topology Exploration Using NepalProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3058733(1611-1614)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3058733
Johnson TKanza YLakshmanan LShkapenyuk VArora ARoy SMehta S(2016)NepalProceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics10.1145/2980523.2980530(1-8)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1145/2980523.2980530
Show More Cited By

TAX: A Tree Algebra for XML

Recommendations

Expressing OLAP operators with the TAX XML algebra
DataX '08: Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web

With the rise of XML as a standard for representing business data, XML data warehouses appear as suitable solutions for Web-based decision-support applications. In this context, it is necessary to allow OLAP analyses over XML data cubes (XOLAP). Thus, ...
Mapping of bibliographical standards into XML

The most popular bibliographical standards, which prescribe the exchange of bibliographical data in machine readable form, are MARC (Machine Readable Cataloguing) and UNIMARC (Universal Machine Readable Cataloguing). This paper presents two schemas, ...
XML: Visual QuickStart Guide

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages

September 2001

341 pages

ISBN:3540440801

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 September 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jamkhedkar PJohnson TKanza YShaikh AShankaranarayanan NShkapenyuk VDas GJermaine CBernstein P(2018)A Graph Database for a Virtualized Network InfrastructureProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3190653(1393-1405)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3190653
Jamkhedkar PJohnson TKanza YShaikh AShankarnarayanan NShkapenyuk VWoodhull GChirkova RYang JSuciu D(2017)Virtualized Network Service Topology Exploration Using NepalProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3058733(1611-1614)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3058733
Johnson TKanza YLakshmanan LShkapenyuk VArora ARoy SMehta S(2016)NepalProceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics10.1145/2980523.2980530(1-8)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1145/2980523.2980530
Papakonstantinou YÖzcan FKoutrika GMadden S(2016)Semistructured Models, Queries and Algebras in the Big Data EraProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2912573(2229-2233)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2912573
Borkar VBu YCarman EOnose NWestmann TPirzadeh PCarey MTsotras VGhandeharizadeh SBalazinska MFreedman MBarahmand S(2015)AlgebricksProceedings of the Sixth ACM Symposium on Cloud Computing10.1145/2806777.2806941(422-433)Online publication date: 27-Aug-2015
https://dl.acm.org/doi/10.1145/2806777.2806941
Braganholo VMattoso M(2014)A Survey on XML FragmentationACM SIGMOD Record10.1145/2694428.269443443:3(24-35)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1145/2694428.2694434
Handoko Getta J(2014)Query Decomposition Strategy for Integration of Semistructured DataProceedings of the 16th International Conference on Information Integration and Web-based Applications & Services10.1145/2684200.2684343(459-463)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1145/2684200.2684343
Sakr SElnikety SHe Y(2014)Hybrid query execution engine for large attributed graphsInformation Systems10.1016/j.is.2013.10.00741(45-73)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.is.2013.10.007
Handoko Getta JWeippl EIndrawan-Santiago MSteinbauer MKotsis GKhalil I(2013)An XML Algebra For Online Processing of XML DocumentsProceedings of International Conference on Information Integration and Web-based Applications & Services10.1145/2539150.2539244(503-507)Online publication date: 2-Dec-2013
https://dl.acm.org/doi/10.1145/2539150.2539244
Bischof S(2012)Optimising XML---RDF data integrationProceedings of the 9th international conference on The Semantic Web: research and applications10.1007/978-3-642-30284-8_67(838-843)Online publication date: 27-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-30284-8_67
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents