Constructing Optimal Bushy Trees Possibly Containing Cross Products for Order Preserving Joins is in P


Moerkotte, Guido


[img]
Preview
PDF
MA-03-12.pdf - Published

Download (80kB)

URL: http://ub-madoc.bib.uni-mannheim.de/737
URN: urn:nbn:de:bsz:180-madoc-7376
Document Type: Working paper
Year of publication: 2003
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Mathematik und Informatik
MADOC publication series: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject: 004 Computer science, internet
Subject headings (SWD): XQuery , XPath , Join-Operation , Abfrageverarbeitung
Individual keywords (German): order preserving join , query optimization , XML , XQuery , XPath
Abstract: One of the main features of XQuery compared to traditional query languages like SQL, is that it preserves the input order - unless specified otherwise. As a consequence, order-preserving algebraic operators are needed to capture the semantics of XQuery correctly. One important algebraic operator is the order-preserving join. The order-preserving join is associative but, in contrast to the traditional join operator, not commutative. Since join ordering (i.e. finding the optimal execution plan for a given set of join operators) has been an important topic of query optimization for SQL, it is expected that it will also play a major role in optimizing XQuery. The search space for ordering traditional joins is exponential in size. Although the lack of commutativity reduces the search space for ordering order-preserving joins, we show that it is still exponential. This raises the question whether the join ordering problem is also NP-hard, as in the traditional setting. We answer this question by introducing the first polynomial algorithm that produces optimal bushy trees possibly containing cross products.
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Moerkotte, Guido (2003) Constructing Optimal Bushy Trees Possibly Containing Cross Products for Order Preserving Joins is in P. Open Access [Working paper]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item