Dataciencia

Colección SciELO Chile

Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases

Indexado

WoS	WOS:000627789800010
Scopus	SCOPUS_ID:85086234342

DOI

10.1145/3375395.3387642

Año

2020

Tipo

proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras

Abstract

We consider the problem of exact probabilistic inference for Union of Conjunctive Queries (UCQs) on tuple-independent databases. For this problem, two approaches currently coexist. In the extensional method, query evaluation is performed by exploiting the structure of the query, and relies heavily on the use of the inclusion - exclusion principle. In the intensional method, one first builds a representation of the lineage of the query in a tractable formalism of knowledge compilation. The chosen formalism should then ensure that the probability can be efficiently computed using simple disjointness and independence assumptions, without the need of performing inclusion - exclusion. The extensional approach has long been thought to be strictly more powerful than the intensional approach, the reason being that for some queries, the use of inclusion - exclusion seemed unavoidable. In this paper we introduce a new technique to construct lineage representations as deterministic decomposable circuits in polynomial time. We prove that this technique applies to a class of UCQs that had been conjectured to separate the complexity of the two approaches. In essence, we show that relying on the inclusion - exclusion formula can be avoided by using negation. This result brings back hope to prove that the intensional approach can handle all tractable UCQs.

Revista

Revista	ISSN
	978-1-4503-7108-7

Métricas Externas

PlumX	Altmetric	Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Plumx: https://plumanalytics.com/learn/about-metrics/
Altmetric: https://www.altmetric.com/about-altmetrics/what-are-altmetrics/
Dimensions: https://www.dimensions.ai/why-dimensions/

Disciplinas de Investigación

WOS
Sin Disciplinas

Scopus
Sin Disciplinas

SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional

Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.

Autores - Afiliación

Ord.	Autor	Género	Institución - País
1	Monet, Mikael	Hombre	Universidad de Chile - Chile Instituto Milenio Fundamentos de los Datos - Chile
2	Assoc Comp Machinery	Corporación

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento

Fuente
Millennium Institute for Foundational Research on Data (IMFD)
IMFD

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos

Agradecimiento
I acknowledge Dan Olteanu for our initial work on the problem [26]. In particular, this joint work already contains the idea of covering the satisfying valuations of φ with mutually exclusive terms, which we reuse intensively here (see the paragraph “The difference with [26]” in the introduction for more details). I also acknowledge Guy Van den Broeck, Paul Beame and Vincent Liew, who had already worked on this problem and attempted similar approaches. Guy Van den Broeck and Dan Olteanu were the first to notice that one could use negation to attack the problem. I note here that Paul Beame and his student Vincent Liew independently found the query from Figure 1 (which was also a counterexample to one of their approaches). I am grateful to Pierre Senellart for careful proofreading of the paper. I thank the Millennium Institute for Foundational Research on Data (IMFD) for funding this research.
I acknowledge Dan Olteanu for our initial work on the problem [26]. In particular, this joint work already contains the idea of covering the satisfying valuations of f with mutually exclusive terms, which we reuse intensively here (see the paragraph "The difference with [26]" in the introduction for more details). I also acknowledge Guy Van den Broeck, Paul Beame and Vincent Liew, who had already worked on this problem and attempted similar approaches. Guy Van den Broeck and Dan Olteanu were the first to notice that one could use negation to attack the problem. I note here that Paul Beame and his student Vincent Liew independently found the query from Figure 1 (which was also a counterexample to one of their approaches). I am grateful to Pierre Senellart for careful proofreading of the paper. I thank the Millennium Institute for Foundational Research on Data (IMFD) for funding this research.

Agradecimiento

I acknowledge Dan Olteanu for our initial work on the problem [26]. In particular, this joint work already contains the idea of covering the satisfying valuations of φ with mutually exclusive terms, which we reuse intensively here (see the paragraph “The difference with [26]” in the introduction for more details). I also acknowledge Guy Van den Broeck, Paul Beame and Vincent Liew, who had already worked on this problem and attempted similar approaches. Guy Van den Broeck and Dan Olteanu were the first to notice that one could use negation to attack the problem. I note here that Paul Beame and his student Vincent Liew independently found the query from Figure 1 (which was also a counterexample to one of their approaches). I am grateful to Pierre Senellart for careful proofreading of the paper. I thank the Millennium Institute for Foundational Research on Data (IMFD) for funding this research.

I acknowledge Dan Olteanu for our initial work on the problem [26]. In particular, this joint work already contains the idea of covering the satisfying valuations of f with mutually exclusive terms, which we reuse intensively here (see the paragraph "The difference with [26]" in the introduction for more details). I also acknowledge Guy Van den Broeck, Paul Beame and Vincent Liew, who had already worked on this problem and attempted similar approaches. Guy Van den Broeck and Dan Olteanu were the first to notice that one could use negation to attack the problem. I note here that Paul Beame and his student Vincent Liew independently found the query from Figure 1 (which was also a counterexample to one of their approaches). I am grateful to Pierre Senellart for careful proofreading of the paper. I thank the Millennium Institute for Foundational Research on Data (IMFD) for funding this research.