XAL: An algebra for XML query optimization

F. Frasincar, G.J.P.M. Houben, C.D. Pau

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


This paper proposes XAL, an XML ALgebra. Its novelty is based on the simplicity of its data model and its well-defined logical operators, which makes it suitable for composability, optimizability, and semantics definition of a query language for XML data. At the heart of the algebra resides the notion of collection, a concept similar to the mathematician's monad or functional programmer's comprehension. The operators are classified in three clusters: extraction operators retrieve the needed information from XML documents, meta-operators control the evaluation of expressions, and construction operators build new XML documents from the extracted data. The resulting algebra has optimization laws similar to the known laws for transforming relational queries. As a consequence, we propose a heuristic optimization algorithm similar to its relational algebra counterpart.
Original languageEnglish
Title of host publicationDatabase Technologies 2002 (Proceedings 13th Australasian Database Conference, ADC 2002, Melbourne, Australia, January 28-February 1, 2002)
EditorsXiaofang Zhou
PublisherAustralian Computer Society
ISBN (Print)0-909-92583-6
Publication statusPublished - 2002
Eventconference; Melbourne, Australia -
Duration: 1 Jan 2002 → …


Conferenceconference; Melbourne, Australia
Period1/01/02 → …
OtherMelbourne, Australia


Dive into the research topics of 'XAL: An algebra for XML query optimization'. Together they form a unique fingerprint.

Cite this