Armstrong axioms and Boyce-Codd-Heath Normal Form under bag semantics |
| |
Authors: | Henning Koehler |
| |
Affiliation: | a School of Information Technology & Electrical Engineering, The University of Queensland, Brisbane, Australia b School of Information Management, The Victoria University of Wellington, Wellington, New Zealand |
| |
Abstract: | The theory of functional dependencies is based on relations, i.e. sets of tuples. Over relations, the class of functional dependencies subsumes the class of keys. Commercial database systems permit the storage of bags of tuples where duplicate tuples can occur. Over bags, keys and functional dependencies interact differently from how they interact over relations.We establish finite ground axiomatizations of keys and functional dependencies over bags, and show a strong correspondence to goal and definite clauses in classical propositional logic. We define a syntactic Boyce-Codd-Heath Normal Form condition, and show that the condition characterizes schemata that will never have any redundant data value occurrences in their instances. The results close the gap between the existing set-based theory of data dependencies and database practice where bags are permitted. |
| |
Keywords: | Database Multiset Key Functional dependency Armstrong axioms Normal form |
本文献已被 ScienceDirect 等数据库收录! |
|