NDLI: The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability

Please wait, while we are loading the content...

Datalog redux: experience and conjecture

Expressive languages for path queries over graph-structured data

The ACM PODS Alberto O. Mendelzon test-of-time-award 2010

From information to knowledge: harvesting entities and relationships from web sources

Optimal sampling from distributed streams

Optimizing linear counting queries under differential privacy

Information complexity: a tutorial

On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases

Foundations of schema mapping management

Characterizing schema mappings via data examples

Cache-oblivious hashing

Transducing Markov sequences

An optimal algorithm for the distinct elements problem

Incremental query evaluation in a ring of databases

Universally optimal privacy mechanisms for minimax agents

Capturing missing tuples and missing values

Certain answers for XML queries

Schema design for XML repositories: complexity and tractability

Understanding queries in a search database system

Performance guarantees for B-trees with different-sized atomic keys

Positive higher-order queries

Understanding cardinality estimation using entropy maximization

Fast Manhattan sketches in data streams

Towards an axiomatization of statistical privacy and utility

Computing query probability with incidence algebras

Simplifying XML schema: single-type approximations of regular tree languages

A learning algorithm for top-down XML transformations

When data dependencies over SQL tables meet the logics of paradox and S-3

Semantic query optimization in the presence of types

On probabilistic fixpoint and Markov chain query languages

The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability

The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability

Content Provider	ACM Digital Library
Author	Greco, Gianluigi Scarcello, Francesco
Abstract	Enforcing local consistency is a well-known technique to simplify the evaluation of conjunctive queries. It consists of repeatedly taking the semijion between every pair of (relations associated with) query atoms, until the procedure stabilizes. If some relation becomes empty, then the query has an empty answer. Otherwise, we cannot say anything in general, unless we have some information on the structure of the given query. In fact, a fundamental result in database theory states that the class of queries for which---on every database---local consistency entails global consistency is precisely the class of acyclic queries. In the last few years, several efforts have been made to define structural decomposition methods isolating larger classes of nearly-acyclic queries, yet retaining the same nice properties as acyclic ones. In particular, it is known that queries having bounded (generalized) hypertree-width can be evaluated in polynomial time, and that this structural property is also sufficient to guarantee that local consistency solves the problem, as for acyclic queries. However, the precise power of such an approach was an open problem: Is it the case that bounded generalized hypertree-width is also a necessary condition to guarantee that local consistency entails global consistency? In this paper, we positively answer this question, and go beyond. Firstly, we precisely characterize the power of local consistency procedures in the more general framework of tree projections, where a query Q and a set V of views (i.e., resources that can be used to answer Q) are given, and where one looks for an acyclic hypergraph covering Q and covered by Q---all known structural decomposition methods are just special cases of this framework, defining their specific set of resources. We show that the existence of tree projections of certain subqueries is a necessary and sufficient condition to guarantee that local consistency entails global consistency. In particular, tight characterizations are given not only for the decision problem, but also when answers restricted to variables covered by some view have to be computed. Secondly, we consider greedy tree-projections that are easy to compute, and we study how far they can be from arbitrary tree-projections, which are intractable in general. Finally, we investigate classes of instances not included in those having tree projections, and which can be easily recognized and define either new islands of tractability, or islands of quasi-tractability.
Starting Page	327
Ending Page	338
Page Count	12
File Format	PDF
ISBN	9781450300339
DOI	10.1145/1807085.1807127
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Local consistency Structural decomposition methods Tree projections
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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