Tractable Circuits in Database Theory

Amarilli, Antoine; Capelli, Florent

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1145/3685980.3685982

Title :

Tractable Circuits in Database Theory

Author(s) :

Amarilli, Antoine [Auteur]
Linking Dynamic Data [LINKS]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Capelli, Florent [Auteur]

Centre de Recherche en Informatique de Lens [CRIL]

Journal title :

SIGMOD Record

Pages :

6-20

Publisher :

ACM

Publication date :

2024-07-31

ISSN :

0163-5808

HAL domain(s) :

Informatique [cs]

English abstract : [en]

This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We then show how these tractable circuits can ...
Show more >This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We then show how these tractable circuits can be used to address database tasks. We first focus on Boolean provenance and its applications for aggregation tasks, in particular probabilistic query evaluation. We study these for Monadic Second Order (MSO) queries on trees, and for safe Conjunctive Queries (CQs) and Union of Conjunctive Queries (UCQs). We also study circuit representations of query answers, and their applications to enumeration tasks: both in the Boolean setting (for MSO) and the multivalued setting (for CQs and UCQs).Show less >

Language :

Anglais

Peer reviewed article :

Non

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

2407.01127
Open access
Access the document

Tractable Circuits in Database Theory BibTeX CSV Excel RIS

Files

Tractable Circuits in Database Theory

BibTeX

CSV

Excel

RIS