文摘
Simple inclusion dependencies and NOT NULL constraints are not finitely axiomatizable. The new class of not null inclusion dependencies (NNINDs) subsumes simple and partial inclusion dependencies. The implication problem for NNINDs is finitely axiomatizable, PSPACE-complete, and fixed parameter-tractable in their arity. Typed acyclic NNINDs are NP-complete, and tree-like NNINDs are linear time decidable. Super-reducedness is an efficient condition sufficient to guarantee no interaction between functional dependencies and NNINDs.