Possibilistic Contextual Key

Abstract

Given a collection of entities, a key is a set of attributes whose values uniquely identify an entity in the collection. Modern developments, including big data and data integration, suffer from data quality problems that also affect the quality of insights and value derived from data. Besides data integrity, important data quality dimensions include accuracy (the degree to which data represents real-world objects) and completeness (the degree of missing information). This thesis addresses this gap by proposing possibilistic contextual keys which aim at ensuring the integrity of entities in some of the possible worlds of uncertain relations encompassing incomplete information. The associated implication problem is characterized axiomatically and algorithmically. Further applications of possibilistic contextual keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. Besides, we show how to compute for any given set of possibilistic contextual keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every contextual key in the given set and violates every possibilistic contextual key not implied by the given set. The computation of possibilistic Armstrong relations has been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size and null marker occurrences of possibilistic Armstrong relations, as well as the time to compute them. Our results support and extend recent findings by showing good computational properties are preserved, even though the expressiveness of the keys are extended over previous work.