NULL INCLUSION DEPENDENCIES IN RELATIONAL DATABASES

Functional dependencies (FDs) and inclusion dependencies (INDs) are th e most fundamental integrity constraints that arise in practice in rel ational databases. We introduce null inclusion dependencies (NINDs) to cater for the situation when a database is incomplete and contains nu ll values. We show that the implication problem for NINDs is the same as that for INDs. We then present a sound and complete axiom system fo r null functional dependencies (NFDs) and NINDs, and prove that the im plication problem for NFDs and NINDs is decidable and EXPTIME-complete . By contrast, when no nulls are allowed, this implication problem is undecidable. This undecidability result has motivated several research ers to restrict their attention to FDs and noncircular INDs in which c ase the implication problem was shown to be EXPTIME-complete. Our resu lts imply that when considering nulls in relational database design we need not assume that NINDs are noncircular. (C) 1997 Academic Press.