NDLI: The dichotomy of probabilistic inference for unions of conjunctive queries

Content Provider	ACM Digital Library
Author	Dalvi, Nilesh Suciu, Dan
Copyright Year	2013
Abstract	We study the complexity of computing a query on a probabilistic database. We consider unions of conjunctive queries, UCQ, which are equivalent to positive, existential First Order Logic sentences, and also to nonrecursive datalog programs. The tuples in the database are independent random events. We prove the following dichotomy theorem. For every UCQ query, either its probability can be computed in polynomial time in the size of the database, or is #P-hard. Our result also has applications to the problem of computing the probability of positive, Boolean expressions, and establishes a dichotomy for such classes based on their structure. For the tractable case, we give a very simple algorithm that alternates between two steps: applying the inclusion/exclusion formula, and removing one existential variable. A key and novel feature of this algorithm is that it avoids computing terms that cancel out in the inclusion/exclusion formula, in other words it only computes those terms whose Mobius function in an appropriate lattice is nonzero. We show that this simple feature is a key ingredient needed to ensure completeness. For the hardness proof, we give a reduction from the counting problem for positive, partitioned 2CNF, which is known to be #P-complete. The hardness proof is nontrivial, and combines techniques from logic, classical algebra, and analysis.
Starting Page	1
Ending Page	87
Page Count	87
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2395116.2395119
Journal	Journal of the ACM (JACM)
Volume Number	59
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-01-09
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mobius function Mobius inversion formula Probabilistic database
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Size and Treewidth Bounds for Conjunctive Queries

Conjunctive queries over trees

On conjunctive queries containing inequalities

On preservation under homomorphisms and unions of conjunctive queries

Probabilistic inductive inference

Probabilistic data exchange

Answering queries on embedded-complete database schemes

Deciding equivalences among conjunctive aggregate queries

Security problems on inference control for SUM, MAX, and MIN queries

The dichotomy of probabilistic inference for unions of conjunctive queries

Similar Documents

Size and Treewidth Bounds for Conjunctive Queries

Conjunctive queries over trees

On conjunctive queries containing inequalities

On preservation under homomorphisms and unions of conjunctive queries

Probabilistic inductive inference

Probabilistic data exchange

Answering queries on embedded-complete database schemes

Deciding equivalences among conjunctive aggregate queries

Security problems on inference control for SUM, MAX, and MIN queries

The dichotomy of probabilistic inference for unions of conjunctive queries