Query Optimization in the Databases Distributed by Means of Product Equivalence Relations

Article type: Research Article

Authors: Marek, W.^{a; *} | Rauszer, C.^{a; b}

Affiliations: [a] Department of Computer Science, University of Kentucky, Lexington, KY 40506, U.S.A. | [b] On leave from Warsaw University, Institute of Mathematics, Warsaw, Poland

Note: [*] Partially supported by NSF grant #DCR 8411600 and USDA grant USDNCSRS/84-CSRS-2-2524.

Abstract: In this paper, we address the problem of query optimization in distributed databases. We show that horizontal partitions of databases, generated by products of equivalence relations, induce optimization techniques for the basic database operations (i.e., the selection, projection, and join operators). In the case of selection, our method allows for restriction of the number of blocks to be searched in the selection process and subsequent simplification of the selection formula at each block. For the natural join operation, we propose an algorithm that reduces the computation of fragments. Proofs of the correctness of our algorithms are also included.

DOI: 10.3233/FI-1988-11303

Journal: Fundamenta Informaticae, vol. 11, no. 3, pp. 241-265, 1988