Cardinality constraints for uncertain data

Koehler, Henning, Link, Sebastian, Prade, Henri and Zhou, Xiaofang (2014). Cardinality constraints for uncertain data. In: Eric Yu, Gillian Dobbie, Matthias Jarke and Sandeep Purao, Conceptual Modeling. 33rd International Conference, ER 2014, Atlanta, GA United States, (108-121). 27-29 October 2014. doi:10.1007/978-3-319-12206-9_9

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Koehler, Henning
Link, Sebastian
Prade, Henri
Zhou, Xiaofang
Title of paper Cardinality constraints for uncertain data
Conference name 33rd International Conference, ER 2014
Conference location Atlanta, GA United States
Conference dates 27-29 October 2014
Proceedings title Conceptual Modeling   Check publisher's open access policy
Journal name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Check publisher's open access policy
Series Lecture Notes in Computer Science
Place of Publication Cham, Switzerland
Publisher Springer International Publishing
Publication Year 2014
Year available 2014
Sub-type Fully published paper
DOI 10.1007/978-3-319-12206-9_9
Open Access Status Not Open Access
ISBN 978-3-319-12205-2
ISSN 0302-9743
Editor Eric Yu
Gillian Dobbie
Matthias Jarke
Sandeep Purao
Volume 8824
Start page 108
End page 121
Total pages 14
Chapter number 9
Total chapters 40
Language eng
Abstract/Summary 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 instance, whenever possible. Even though the problem of finding an Armstrong instance is precisely exponential, our algorithm computes an Armstrong instance with conservative use of time and space. Data engineers and domain experts can jointly inspect Armstrong instances in order to consolidate the certainty by which a cardinality constraint shall hold in the underlying application domain.
Keyword Armstrong database
Cardinality constraint
Data semantics
Possibility theory
Qualitative reasoning
Uncertain data
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 5 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 17 Apr 2015, 20:40:31 EST by Caitlin Maskell on behalf of School of Information Technol and Elec Engineering