Counting the Answers to a Query

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorCroquevielle, Luis Alberto
dc.contributor.authorJayaram, Rajesh
dc.contributor.authorRiveros, Cristian
dc.date.accessioned2025-01-20T21:01:22Z
dc.date.available2025-01-20T21:01:22Z
dc.date.issued2022
dc.description.abstractCounting the answers to a query is a fundamental problem in databases, with several applications in the evaluation, optimization, and visualization of queries. Unfortunately, counting query answers is a #P-hard problem in most cases, so it is unlikely to be solvable in polynomial time. Recently, new results on approximate counting have been developed, specifically by showing that some problems in automata theory admit fully polynomial-time randomized approximation schemes. These results have several implications for the problem of counting the answers to a query; in particular, for graph and conjunctive queries. In this work, we present the main ideas of these approximation results, by using labeled DAGs instead of automata to simplify the presentation. In addition, we review how to apply these results to count query answers in different areas of databases.
dc.fuente.origenWOS
dc.identifier.eissn1943-5835
dc.identifier.issn0163-5808
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/92867
dc.identifier.wosidWOS:000887946600001
dc.issue.numero3
dc.language.isoen
dc.pagina.final17
dc.pagina.inicio6
dc.revistaSigmod record
dc.rightsacceso restringido
dc.titleCounting the Answers to a Query
dc.typeartículo
dc.volumen51
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas