An algorithm for servicing multi-relational queries

Abstract

Let R be a relational database containing relations {R1,R2,…,Rn}. For each relation Ri, 1 ≤ i ≤ n, let Di = {di,1,di,2,…} be its set of domains and let Ki = {ki,1,ki,2,…} ⊆ Di be its set of primary keys. Finally, let D = {D1,D2,…,Dn} and K = {K1,K2,…,Kn}. Suppose that a user of database R wishes to create a new relation, Rn+1, whose domains are Dn+1 ⊆ ? Dj. In this paper, the authors describe an algorithm which, given D K, and Dn+1, determines a sequence of joins to generate Rn+1 from R1,…,Rn (if such a sequence exists). Theoretical and empirical computing times of the algorithm are discussed. A new relational database system employing the algorithm is outlined.