Algorithmic Perspective of Strongly Possible Keys and Functional Dependencies

Abstract

It is common to encounter missing values in database tables. For an incomplete table, a possible world can be obtained by replacing any missed value with a value from the attribute (infinite) domain. A possible key (possible functional dependency) is satisfied in an incomplete table ”T” if there exists a possible world of ”T” that satisfies the key (the functional dependency) constraint. If all possible worlds of ”T” satisfy the key (functional dependency), then we say that ”T” satisfies a certain key (functional dependency). The concept of strongly possible worlds was introduced recently that considers only the active domain (the set of values that are already appearing in each attribute in the table), in a way that a strongly possible world
is obtained by replacing any missing value with a value from the corresponding attributes active domain. So, a strongly possible key spKey (functional dependency spFD) is satisfied by a table ”T” if there exists a strongly possible world that satisfies the key (functional dependency). In this paper, we investigate the approximation measures of spKeys and spFDs when the strongly possible constraint is not satisfied by a given table. We introduce the g5 measures which is the ratio of the minimum number of tuples that need to be added so that the constraint is satisfied. The measure g3 represent the ratio of the minimum number of tuples that need to be removed so that the table satisfies the constraint. We introduce a new measure
g5, which is the ratio of the minimum number of tuples to be added to the table so the result satisfies the constraint. Where adding new tuples with new values will extend the active domain. We prove that g3 is an upper bound of g5 for a constraint in a table. Furthermore, g3 and g5 are independent of each other, where there exist tables of some large number of tuples that satisfy g3 − g5 = p/q for any rational number 0 ≤ p/q < 1. We study the complexity of determining these approximate measures.