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

Moerkotte, Guido

MA-03-12.pdf - Veröffentlichte Version

Download (80kB)

URN: urn:nbn:de:bsz:180-madoc-7376
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2003
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Mathematik und Informatik
MADOC-Schriftenreihe: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet: 004 Informatik
Normierte Schlagwörter (SWD): XQuery , XPath , Join-Operation , Abfrageverarbeitung
Freie Schlagwörter (Deutsch): 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.
Zusätzliche Informationen:

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

+ Zitationsbeispiel und Export

Moerkotte, Guido (2003) Constructing Optimal Bushy Trees Possibly Containing Cross Products for Order Preserving Joins is in P. [Arbeitspapier]

+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detailierte Angaben

Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail

Actions (login required)

Eintrag anzeigen Eintrag anzeigen