Constructing Optimal Bushy Processing Trees for Join Queries is NP-hard

Moerkotte, Guido ; Scheufele, Wolfgang

TR-96-011.pdf - Published

Download (166kB)

URN: urn:nbn:de:bsz:180-madoc-7958
Document Type: Working paper
Year of publication: 1996
The title of a journal, publication series: Technical Reports
Volume: 96-011
Place of publication: Mannheim
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
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): Join-Operation , Baum <Mathematik> , NP-hartes Problem
Abstract: We show that constructing optimal bushy processing trees for join queriesis NP-hard. More specifically, we show that even the construction of optimal bushy trees for computing the cross product for a set of relations is NP-hard.

Dieser Eintrag ist Teil der Universitätsbibliographie.

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

Metadata export


+ 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