After a relation scheme R is decomposed into the set of schemes ρ={R_1,...,R_n},we may pose queries as if R existed in the database,taking a join of R_i's,when it is necessary to implement the query.Suppose a que...After a relation scheme R is decomposed into the set of schemes ρ={R_1,...,R_n},we may pose queries as if R existed in the database,taking a join of R_i's,when it is necessary to implement the query.Suppose 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 is given in the paper.展开更多
文摘After a relation scheme R is decomposed into the set of schemes ρ={R_1,...,R_n},we may pose queries as if R existed in the database,taking a join of R_i's,when it is necessary to implement the query.Suppose 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 is given in the paper.
