Approximate Integrity Constraints in Incomplete Databases With Limited Domains 

Abstract In case of incomplete database tables, a possible world is obtained by replacing any missing value by a value from the corresponding attribute's domain that can be infinite. A possible key or possible functional dependency constraint is satisfied by an incomplete table if we can obtain a possible world that satisfies the given key or functional dependency. On the other hand, a certain key or certain functional dependency holds if all possible worlds satisfy the constraint, 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 \nul's by a value from the ones appearing in the corresponding attribute of the table).A strongly possible key or functional dependency holds in an incomplete table if there exists a strongly possible world that satisfies the given constraint. 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 approximation measures of strongly possible keys (spKeys), functional dependencies (spFDs), multivalued dependencies (spMVDs) and cross joins (spCJs). $g_3$ and $g_5$ measures are used to measure how close a table $Y$ satisfies a constraint if it is violated in $T$. Where the two measures $g_3$ and $g_5$ represent the ratio of the minimum number of tuples that are required to be removed from or added to, respectively, the table so that the constraint holds. Removing tuples may remove the cases that caused the constraint violation and adding tuples can extend the values shown on an attribute. For spKeys and spFDs, We show that the $g_3$ value is always an upper bound of the $g_5$ 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 $g_3-g_5=\frac{p}{q}$ for any rational number $0\le\frac{p}{q}<1$. On the other hand, we show that the two measures values are independent of each other in the case of spMVDs and spCJs.We also treat complexity questions of determination of the approximation values.