This work reviews how database theory uses tractable circuit classes from knowledge
compilation. We present relevant query evaluation tasks, and notions of tractable circuits …

This demonstration showcases ProvSQL, an open-source module for the PostgreSQL
database management system that adds support for computation of provenance and …

Treewidth is a parameter that measures how tree-like a relational instance is, and whether it
can reasonably be decomposed into a tree. Many computation tasks are known to be …

Probabilistic data is motivated by the need to model uncertainty in large databases. Over the
last twenty years or so, both the Database community and the AI community have studied …

We review the basics of data provenance in relational databases. We describe different
provenance formalisms, from Boolean provenance to provenance semirings and beyond …

We study the problem of enumerating the satisfying valuations of a circuit while bounding
the delay, ie, the time needed to compute each successive valuation. We focus on the class …

The field of knowledge compilation establishes the tractability of many tasks by studying how
to compile them to Boolean circuit classes obeying some requirements such as …

Information in many applications, such as mobile wireless systems, social networks, and
road networks, is captured by graphs. In many cases, such information is uncertain. We …

We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs,
namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our …

The evaluation of a query over a probabilistic database boils down to computing the
probability of a suitable Boolean function, the lineage of the query over the database. The …