An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R1，…，Rn},we may pose queries as if Rexisted in the database,taking a join of Ri‘s,when it is necessary to implement the query,Suppos a query involves a set of attributes S R，we want to find the smallest subset of ρ whose union includes.S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies in given in the paper.

An efficient algorithm for processing multi-relation queries in relational databases

After a relation schemeR is decomposed into the set of schemesρ={R ₁,...,R_n}, we may pose queries as ifR existed in the database, taking a join ofR _i’s, when it is necessary to implement the query. Suppose a query involves a set of attributesS?R, we want to find the smallest subset of ρ whose union includesS. We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm. A subset of ρ whose union includesS and has a decomposition into 3NF with a lossless join and preservation of dependencies is given in the paper.