The Complexity of Counting Problems Over Incomplete Databases

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorBarcelO, Pablo
dc.contributor.authorMonet, Mikael
dc.date.accessioned2024-01-10T13:10:19Z
dc.date.available2024-01-10T13:10:19Z
dc.date.issued2021
dc.description.abstractWe study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query q, we consider the following two problems: Given as input an incomplete database D, (a) return the number of completions of D that satisfy q; or (b) return the number of valuations of the nulls of D yielding a completion that satisfies q. We obtain dichotomies between #P-hardness and polynomial-time computability for these problems when q is a self-join-free conjunctive query and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in D (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: For instance, while the latter is always in #P, we prove that the former is not in #P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes.
dc.description.funderANID -Millennium Science Initiative Program
dc.description.funderFondecyt
dc.fechaingreso.objetodigital2024-05-14
dc.format.extent52 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1145/3461642
dc.identifier.eissn1557-945X
dc.identifier.issn1529-3785
dc.identifier.urihttps://doi.org/10.1145/3461642
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/77834
dc.identifier.wosidWOS:000749583700001
dc.information.autorucFacultad de Ingeniería; Arenas Saavedra, Marcelo Alejandro; S/I; 81488
dc.issue.numero4
dc.language.isoen
dc.nota.accesocontenido parcial
dc.publisherASSOC COMPUTING MACHINERY
dc.revistaACM TRANSACTIONS ON COMPUTATIONAL LOGIC
dc.rightsacceso restringido
dc.subjectIncomplete databases
dc.subjectclosed-world assumption
dc.subjectcounting complexity
dc.subjectFully Polynomial-time Randomized Approximation Scheme (FPRAS)
dc.subjectCOMPUTATIONAL-COMPLEXITY
dc.subjectGRAPH
dc.subjectSETS
dc.titleThe Complexity of Counting Problems Over Incomplete Databases
dc.typeartículo
dc.volumen22
sipa.codpersvinculados81488
sipa.indexWOS
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
The complexity of counting problems over incomplete databases.pdf
Size:
3.01 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas