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, multi-valued, 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 forall x in 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.