Digital Symposium Collection 2000

Reasoning about Nested Functional Dependencies Carmem S. Hara and Susan B. Davidson   View Paper (PDF)   Return to Semantics Abstract Functional dependencies add semantics to a database schema, and are useful for studying various problems, such as database design, query optimization and how dependencies are carried into a view. In the context of a nested relational model, these dependencies can be extended by using path expressions instead of attribute names, resulting in a class of dependencies that we call nested functional dependencies (NFDs). NFDs define a natural class of dependencies in complex data structures; in particular they allow the specification of many useful intra- and inter-set dependencies (i.e., dependencies that are local to a set and dependencies that require consistency between sets). Such constraints cannot be captured by existing notions of functional, multivalued, or join dependencies. This paper presents the definition of NFDs and gives their meaning by translation to logic. It then presents a sound and complete set of eight inference rules for NFDs, and discusses approaches to handling the existence of empty sets in instances. Empty sets add complexity in reasoning since formulas such as for all x over R.P(x) are trivially true when R is empty. This axiomatization represents a first step in reasoning about constraints on data warehouse applications, where both the source and target databases support complex types. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Nicole Bidoit : Non First Normal Form Relations: An Algebra Allowing Data Restructuring. JCSS 33(3) : 361-393(1986) [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] Alfred V. Aho , Yehoshua Sagiv , Jeffrey D. Ullman : Equivalences Among Relational Expressions. SIAM J. Comput. 8(2) : 218-246(1979) [4] Catriel Beeri , Moshe Y. Vardi : Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1) : 76-98(1984) [5] Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138 [6] Peter P. Chen : The Entity-Relationship Model - Toward a Unified View of Data. TODS 1(1) : 9-36(1976) [7] Patrick C. Fischer , Lawrence V. Saxton , Stan J. Thomas , Dirk Van Gucht : Interactions between Dependencies and Nested Relational Structures. JCSS 31(3) : 343-354(1985) [8] ... [9] Anthony C. Klug : Calculating Constraints on Relational Expressions. TODS 5(3) : 260-290(1980) [10] Anthony C. Klug , Rod Price : Determining View Dependencies Using Tableaux. TODS 7(3) : 361-380(1982) [11] ... [12] Akifumi Makinouchi : A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977 : 447-453 [13] David Maier , Alberto O. Mendelzon , Yehoshua Sagiv : Testing Implications of Data Dependencies. TODS 4(4) : 455-469(1979) [14] David Maier : The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0 Contents [15] Z. Meral Özsoyoglu , Li-Yan Yuan : A New Normal Form for Nested Relations. TODS 12(1) : 111-136(1987) [16] ... [17] Lucian Popa , Val Tannen : An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999 : 39-57 [18] ... [19] Jeffrey D. Ullman : Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6 [20] Grant E. Weddell : A Theory of Functional Dependencies for Object-Oriented Data Models. DOOD 1989 : 165-184 [21] Grant E. Weddell : Reasoning about Functional Dependencies Generalized for Semantic Data Models. TODS 17(1) : 32-64(1992) [22] Limsoon Wong : Querying Nested Collections. Ph.D. thesis, Univ. Pennsylvania 1994 [23] Moshé M. Zloof : Query-by-Example: the Invocation and Definition of Tables and Forms. VLDB 1975 : 1-24 BIBTEX @inproceedings{DBLP:conf/pods/HaraD99,   author    = {Carmem S. Hara and                 Susan B. Davidson},    title     = {Reasoning about Nested Functional Dependencies},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {91-100},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM