Relational database schema design for uncertain data

• Published in: Information systems (Oxford) 2019-09, Vol.84, p.88-110
• Main Authors: Link, Sebastian, Prade, Henri
• Format: Article
• Language: English
• Subjects: Anomalies; Artificial Intelligence; Boyce–Codd normal form; Canonical forms; Computer Science; Data redundancy; Database schema design; Decomposition; Dependence; Design; Functional dependency; Information systems; Normalization; Qualitative reasoning; Redundancy; Relational data bases; Third normal form; Uncertain data
• ISSN: 0306-4379; 1873-6076
• DOI: 10.1016/j.is.2019.04.003

Driven by the dominance of the relational model, we investigate how the requirements of applications on the certainty of functional dependencies can improve the outcomes of relational database schema design. For that purpose, we assume that tuples are assigned a degree of possibility with which they occur in a relation, and that functional dependencies are assigned a dual degree of certainty which says to which tuples they apply. A design theory is developed for functional dependencies with degrees of certainty, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples bring forward different degrees of data redundancy, caused by functional dependencies with the dual degree of certainty. Variants of the classical syntactic Boyce–Codd and Third Normal Forms are established. They are justified semantically in terms of eliminating data redundancy and update anomalies of given degrees, and minimizing data redundancy of given degrees across all dependency-preserving decompositions, respectively. As a practical outcome of our results, designers can simply fix the degree of certainty they target, and then apply classical decomposition and synthesis to the set of functional dependencies whose associated degree of certainty meets the target. Hence, by fixing the certainty degree a designer controls which integrity requirements will be enforced for the application and which data will be processed by the application. The choice of the certainty degree also balances the classical trade-off between query and update efficiency on future database instances. Our experiments confirm the effectiveness of our control parameter, and provide original insight into classical normalization strategies and their implementations. •Uncertainty in data is modeled by assigning to records a degree of possibility.•Certainty degrees of functional dependencies indicate on which records they hold.•Different degrees of data redundancy can then be defined and observed.•Refined normal forms avoid or minimize data redundancy up to a target degree.•Certainty degrees control classical trade-offs to optimize relational schema design.