The complexity of processing tree queries in distributed databases

Author

Wang, Chihping

Author_Institution

Dept. of Comput. Sci., California Univ., Riverside, CA, USA

fYear

1990

fDate

9-13 Dec 1990

Firstpage

604

Lastpage

611

Abstract

Semi-joins have been introduced to reduce the cost of processing distributed queries. The determine the optimal semi-join processing strategy, one must consider both the reduction effect and the transmission overhead. Researchers have studied the problem of finding the optimal semi-join strategies for processing tree queries. Although a number algorithms have been proposed, they either have a very high complexity or only solve special cases. It is conjectured that the tree query processing problem is inherently difficult. The author formally answers this question by proving it NP-hard

Keywords

computational complexity; database theory; distributed databases; information retrieval; relational databases; trees (mathematics); NP-hard; complexity; distributed databases; distributed queries; query processing; relational model; semi-join processing; tree queries; Computational complexity; Computer science; Costs; Data models; Database systems; Distributed computing; Distributed databases; Marine vehicles; Mathematical programming; Query processing;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-2087-0

Type

conf

DOI

10.1109/SPDP.1990.143612

Filename

143612