|
Abstract : |
Functional dependencies add semantics to a database schema ? and are useful for studying vari? ous 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 de?ne a natural class of dependencies in complex data struc? tures ? in particular they allow the speci?cation 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 ? multi?valued ? or join dependencies. This paper presents the de?nition 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 8x 2 R?P ?x ? are trivially true when R is empty. This axiomatization represents a ?rst step in reasoning about constraints on data warehouse applications ? where both the source and target databases support complex types. 1, |
