Relational database schema design for uncertain data. (September 2019)

• Record Type: Journal Article
• Authors: Link, Sebastian; Prade, Henri
• Is Part Of: Information systems. Volume 84(2019)
• Page Start: 88
• Page End: 110
• Publication Date: 2019-09
• Subjects: Boyce–Codd normal form -- Database schema design -- Data redundancy -- Functional dependency -- Normalization -- Qualitative reasoning -- Third normal form -- Uncertain data; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2019.04.003
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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. Highlights: 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.