Inclusion dependencies and their interaction with functional dependencies in SQL

Abstract

Driven by the SQL standard, we investigate simple and partial inclusion dependencies (INDs) with not null constraints. Implication of simple INDs and not null constraints is not finitely axiomatizable. We propose not null inclusion dependencies (NNINDs) that subsume simple and partial INDs, are finitely axiomatizable and PSPACE-complete to decide. NNINDs are fixed parameter-tractable in their arity, typed acyclic NNINDs are NP-hard, and tree-like NNINDs are decidable in linear time. We use a chase to decide implication for functional dependencies and acyclic NNINDs in exponential time, and identify a liberal condition that guarantees no interaction between functional dependencies and acyclic (NN)INDs.