Functional dependencies and constraints on null values in database relations

Database relations with incomplete information are considered. The no-information interpretation of null values is adopted, due to its characteristics of generality and naturalness. Coherently with the framework and its motivation, two meaningful classes of integrity constraints are studied: (a) functional dependencies, which have been widely investigated in the classical relational theory and (b) constraints on null values, which control the presence of nulls in the relations. Specifically, three types of constraints on null values are taken into account (nullfree subschemes, existence constraints, disjunctive existence constraints), and the interaction of each of them with functional dependencies is studied. In each of the three cases, the inference problem is solved, the complexity of the algorithms for its solution analyzed, and the existence of a complete axiomatization discussed