Query folding

Author

Qian, Xiaolei

Author_Institution

Comput. Sci. Lab., SRI Int., USA

fYear

1996

fDate

26 Feb-1 Mar 1996

Firstpage

48

Lastpage

55

Abstract

Query folding refers to the activity of determining if and how a query can be answered using a given set of resources, which might be materialized views, cached results of previous queries, or queries answerable by other databases. We investigate query folding in the context where queries and resources are conjunctive queries. We develop an exponential time algorithm that finds all complete or partial foldings, and a polynomial time algorithm for the subclass of acyclic conjunctive queries. Our results can be applied to query optimization in centralized databases, to query processing in distributed databases, and to query answering in federated databases

Keywords

computational complexity; graph theory; query processing; acyclic conjunctive queries; cached results; centralized databases; conjunctive queries; distributed databases; exponential time algorithm; federated databases; materialized views; partial foldings; polynomial time algorithm; query answering; query folding; query optimization; query processing; Computer science; Contracts; Distributed databases; Drugs; Insurance; Intrusion detection; Laboratories; Polynomials; Query processing; Variable speed drives;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Engineering, 1996. Proceedings of the Twelfth International Conference on

Conference_Location

New Orleans, LA

ISSN

1063-6382

Print_ISBN

0-8186-7240-4

Type

conf

DOI

10.1109/ICDE.1996.492088

Filename

492088