Codd's relational model describes just one possible world. To better cope with incomplete information, extended database models allow several possible worlds. Vague tables are one such convenient extended model where attributes accept sets of possible values (e.g., the manager is either Jill or Bob). However, conceptual database design in such cases remains an open problem. In particular, there is no canonical definition of functional dependencies (FDs) over possible worlds (e.g., each employee has just one manager). We identify several desirable properties that the semantics of such FDs should meet including Armstrong's axioms, the independence from irrelevant attributes, seamless satisfaction and implied by strong satisfaction. We show that we can define FDs such that they have all our desirable properties over vague tables. However, we also show that no notion of FD can satisfy all our desirable properties over a more general model (disjunctive tables). Our work formalizes a trade-off between having a general model and having well-behaved FDs.
The second approach, based on possibilistic and probabilistic databases, can be considered an extension of the the possible worlds framework @cite_4 @cite_6 @cite_29 . However, Link and Prade @cite_23 assign possibilities to tuples, not to values. Based on these possibilistic tuples, possible worlds are generated as a nested chain: the smallest world is the one with only fully possible tuples; the largest world contains all tuples. Certainty degrees are attached to standard FDs, based on the possibility degree of the smallest world in which they are violated.
@cite_23 @cite_29 @cite_4 @cite_6
2535582266 2006650729 1605533566
We investigate the impact of uncertainty on relational data -base schema design. Uncertainty is modeled qualitatively by assigning to tuples a degree of possibility with which they occur, and assigning to functional dependencies a degree of certainty which says to which tuples they apply. A design theory is developed for possibilistic functional dependencies, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples result in a scale of different degrees of data redundancy. Scaled versions of the classical syntactic Boyce-Codd and Third Normal Forms are established and semantically justified in terms of avoiding data redundancy of different degrees. Classical decomposition and synthesis techniques are scaled as well. Therefore, possibilistic functional dependencies do not just enable designers to control the levels of data integrity and losslessness targeted but also to balance the classical trade-off between query and update efficiency. Extensive experiments confirm the efficiency of our framework and provide original insight into relational schema design. This paper is situated in the area of fuzzy databases, i.e., databases containing imprecise information. More precisely, it deals with the notion of a functional dependency when data involved in this type of property are possibly imprecise. Contrary to previous works, the idea is not to fuzzify the concept of a functional dependency. In the view suggested here, we rather consider regular functional dependencies and we study the impact of the presence of such FDs on the insertion and handling of imprecise data. In this paper, we introduce a definition of the concept of a functional dependency (FD) in the context of databases containing ill-known attributes values represented by possibility distributions. Contrary to previous proposals, this definition is based on the possible worlds model and consists in viewing the satisfaction of an FD by a relation as an uncertain event whose possibility and necessity can be quantified. We give the principle of a method for incrementally computing the related possibility and necessity degrees and tackle the issue of tuple refinement in the presence of an FD.