Approximate integrity constraints in incomplete databases with limited domains

Al-atar, Munqath and Sali, Attila (2025) Approximate integrity constraints in incomplete databases with limited domains. ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE. ISSN 1012-2443 (In Press)

Preview

Text s10472-025-09967-9.pdf - Published Version Available under License Creative Commons Attribution. Download (466kB) | Preview

Abstract

A strongly possible constraint is an intermediate concept between possible and certain constraints, based on the strongly possible world approach (a strongly possible world is obtained by replacing NULL’s by a value from the ones appearing in the corresponding attribute of the table). In the present paper, we introduce strongly possible versions of multivalued dependencies and cross joins, and we analyse the complexity of checking the validity of a given strongly possible cross joins. We also study two approximation measures, g3 and g5, of strongly possible keys (spKeys), functional dependencies (spFDs), multivalued dependencies (spMVDs) and cross joins (spCJs). For spKeys and spFDs, we show that the g3 value is always an upper bound of the g5 value for a given constraint in a table. However, there are tables of arbitrarily large number of tuples and a constant number of attributes that satisfy g3-g5=pq for any rational number 0≤pq<1. On the other hand, we show that the values of measures g3 and g5 are independent of each other in the case of spMVDs and spCJs. We prove that checking whether a given strongly possible cross join holds in an incomplete table is NP-complete, in sharp contrast to the fact that checking a given cross join in a complete table is easily seen to be polynomially solvable. We also treat complexity questions of determination of the approximation values, namely we show that both, determining g3 and g5 for spCJs are NP-complete. © The Author(s) 2025.

Actions (login required)

Edit Item