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

Vorschau

PDF
TR-96-011.pdf - Veröffentlichte Version
Download (166kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/795
URN:	urn:nbn:de:bsz:180-madoc-7958
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	1996
Titel einer Zeitschrift oder einer Reihe:	Technical Reports
Band/Volume:	96-011
Ort der Veröffentlichung:	Mannheim
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
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):	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.