scientific article; zbMATH DE number 4001521

From MaRDI portal
Publication:4728289





[For the entire collection see Zbl 0578.00002.] This survey focuses on three major topics in the theory of dependencies: the implication problem, the universal relational model and acyclicity of database schemes. The historical-perspective section, with many classical examples and (as through the whole paper) enlightening comments, presents the development of dependency theory from the ancient functional dependencies up to the general notion of dependency. In the next section, the implication problem for full dependencies (where implication and finite implication coincide) and for embedded dependencies (where this coincidence does not hold) are presented; the main unsolvability and complexity results are given. In the section devoted to the universal relational model, the decomposition problem, the consistency problem and query answering for finite databases are treated. The last section is an exposition of the ideas on acyclicity of database schemes. The authors point out how intractable (general) problems on database schemes become efficiently solvable when acyclic schemes are considered (moreover, an original result is proved). The clarity of exposition, the revealing points of view, the rigorous presentation of different terms and approaches for the same idea or notion, the open problems mentioned in the text, make this survey extremely useful for all researchers in relational database theory.




Cited in
(22)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4728289)