Answers are grounded in this paper and cite their sources.
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 ’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, g₃ g 3 and g₅ g 5 , of strongly possible keys (spKeys), functional dependencies (spFDs), multivalued dependencies (spMVDs) and cross joins (spCJs). For spKeys and spFDs, we show that the g₃ g 3 value is always an upper bound of the g₅ 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₃-g₅=p/q g 3 - g 5 = p q for any rational number 0≤ p/q<1 0 ≤ p q < 1 . On the other hand, we show that the values of measures g₃ g 3 and g₅ g 5 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 g₃ g 3 and g₅ g 5 for spCJs are NP-complete.
No takes yet. Share an insight, caveat, or question.
Al-atar et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: