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)
|
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.
Item Type: | Article |
---|---|
Additional Information: | ITRDC, University of Kufa, Kufa, Iraq Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Hungary Alfréd Rényi Institute of Mathematics, Budapest, Hungary Export Date: 25 February 2025; Cited By: 0; Correspondence Address: A. Sali; Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Hungary; email: sali.attila@renyi.hu |
Uncontrolled Keywords: | multivalued dependency; Data imputation; Strongly possible keys; Approximate functional dependencies; Approximate keys; Cross joins; Incomplete databases; Strongly possible functional dependencies; |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 21 Jul 2025 08:52 |
Last Modified: | 21 Jul 2025 08:52 |
URI: | https://real.mtak.hu/id/eprint/221235 |
Actions (login required)
![]() |
Edit Item |