Possibilistic keys - Université Toulouse - Jean Jaurès Accéder directement au contenu
Article Dans Une Revue Fuzzy Sets and Systems Année : 2019

Possibilistic keys

Résumé

Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. Using extremal combinatorics, we then characterize the families of non-redundant possibilistic keys that attain maximum cardinality. In addition, we show how to compute for any given set of possibilistic keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every key in the given set and violates every possibilistic key not implied by the given set. We also establish an algorithm for the discovery of all possibilistic keys that are satisfied by a given possibilistic relation. It is shown that the computational complexity of computing possibilistic Armstrong relations is precisely exponential in the input, and the decision variant of the discovery problem is NP-complete as well as W[2]-complete in the size of the possibilistic key. Further applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. The computation of possibilistic Armstrong relations and discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size of possibilistic Armstrong relations and the time to compute them, as well as the time it takes to compute a cover of the possibilistic keys that hold on a possibilistic relation, and the time it takes to remove any redundant possibilistic keys from this cover.
Fichier principal
Vignette du fichier
balamuralikrishna_25041.pdf (2.46 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02397255 , version 1 (06-12-2019)

Identifiants

Citer

Nishita Balamuralikrishna, Yingnan Jiang, Hemming Köhler, Uwe Leck, Sebastian Link, et al.. Possibilistic keys. Fuzzy Sets and Systems, 2019, 376 (Theme: Computer Science), pp.1-36. ⟨10.1016/j.fss.2019.01.008⟩. ⟨hal-02397255⟩
73 Consultations
55 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More