OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Cardinality constraints on qualitatively uncertain data

Hall, Neil and Köhler, Hemming and Link, Sebastian and Prade, Henri and Zhou, Xiaofang Cardinality constraints on qualitatively uncertain data. (2015) Data and Knowledge Engineering, 99. 126-150. ISSN 0169-023X

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1016/j.datak.2015.06.002


Modern applications require advanced techniques and tools to process large volumes of uncertain data. For that purpose we introduce cardinality constraints as a principled tool to control the occurrences of uncertain data. Uncertainty is modeled qualitatively by assigning to each object a degree of possibility by which the object occurs in an uncertain instance. Cardinality constraints are assigned a degree of certainty that stipulates on which objects they hold. Our framework empowers users to model uncertainty in an intuitive way, without the requirement to put a precise value on it. Our class of cardinality constraints enjoys a natural possible world semantics, which is exploited to establish several tools to reason about them. We characterize the associated implication problem axiomatically and algorithmically in linear input time. Furthermore, we show how to visualize any given set of our cardinality constraints in the form of an Armstrong sketch. Even though the problem of finding an Armstrong sketch is precisely exponential, our algorithm computes a sketch with conservative use of time and space. Data engineers may therefore compute Armstrong sketches that they can jointly inspect with domain experts in order to consolidate the set of cardinality constraints meaningful for a given application domain.

Item Type:Article
HAL Id:hal-03516777
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > Massey University (NEW ZEALAND)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Soochow University (CHINA)
Other partners > University of Auckland - UOA (NEW ZEALAND)
Laboratory name:
The Marsden Fund Council (Nouvelle Zélande) - The Royal Society of New Zealand (Nouvelle Zélande) - The Natural Science Foundation of China (Chine) - The Australian Research Council (Australie)
Deposited On:18 Feb 2020 10:09

Repository Staff Only: item control page