Referential Integrity under Uncertain Data


Together with domain and entity and integrity, referential integrity embodies the integrity principles of relational information systems. While relational databases address applications for data that is certain, modern day applications require the handling of uncertain data. In particular, the veracity of big data and the complex integration of data from heterogeneous sources leave referential integrity vulnerable. We apply possibility theory to introduce the class of possibilistic inclusion dependencies. We show that our class inherts good computational properties from relational inclusion dependencies. In particular, we show that the associated implication problem is PSPACE-complete, but fixed-parameter tractable in the input arity. We also establish a binary axiomatization.

06: Constraint modelling Main Track