Cardinality constraints on qualitatively uncertain data

作     者：Hall, Neil Koehler, Henning Link, Sebastian Prade, Henri Zhou, Xiaofang 

作者机构：Univ Auckland Dept Comp Sci Auckland 1 New Zealand Massey Univ Sch Engn & Adv Technol Palmerston North New Zealand Univ Toulouse 3 CNRS IRIT F-31062 Toulouse France Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia Soochow Univ Suzhou Peoples R China 

出 版 物：《DATA & KNOWLEDGE ENGINEERING》 (数据与知识工程)

年 卷 期：2015年第99卷

页      面：126-150页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Marsden Fund Council Natural Science Foundation of China Australian Research Council [DP140103171] 

主　　题：Data and knowledge visualization Data models Database semantics Management of integrity constraints Requirements engineering 

摘      要：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. (C) 2015 Elsevier B.V. All rights reserved.