NDLI: Query evaluation via tree-decompositions

Content Provider	ACM Digital Library
Author	Flum, Jrg Frick, Markus Grohe, Martin
Copyright Year	2002
Abstract	A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the article, we consider arbitrary formulas on tree-like structures. We generalize a theorem of Courcelle [1990] by showing that on structures of bounded tree-width a monadic second-order formula (with free first- and second-order variables) can be evaluated in time linear in the structure size plus the size of the output.In the second part, we study tree-like formulas on arbitrary structures. We generalize the notions of acyclicity and bounded tree-width from conjunctive queries to arbitrary first-order formulas in a straightforward way and analyze the complexity of evaluating formulas of these fragments. Moreover, we show that the acyclic and bounded tree-width fragments have the same expressive power as the well-known guarded fragment and the finite-variable fragments of first-order logic, respectively.
Starting Page	716
Ending Page	752
Page Count	37
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/602220.602222
Journal	Journal of the ACM (JACM)
Volume Number	49
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-11-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Acyclic conjunctive queries Combined complexity Hypergraphs Monadic second-order logic Tree-width
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

Hypertree Decompositions: Questions and Answers

Query Evaluation Via Tree-Decompositions (2000)

Query Evaluation Via Tree-Decompositions (2000)

Query Evaluation Via Tree-Decompositions (2000)

The complexity of acyclic conjunctive queries

Query Evaluation via Tree-Decompositions (2001)

Query evaluation via tree-decompositions (extended abstract).

Deciding first-order properties of locally tree-decomposable structures

Query evaluation via tree-decompositions.

Query evaluation via tree-decompositions

Similar Documents

Hypertree Decompositions: Questions and Answers

Query Evaluation Via Tree-Decompositions (2000)

Query Evaluation Via Tree-Decompositions (2000)

Query Evaluation Via Tree-Decompositions (2000)

The complexity of acyclic conjunctive queries

Query Evaluation via Tree-Decompositions (2001)

Query evaluation via tree-decompositions (extended abstract).

Deciding first-order properties of locally tree-decomposable structures

Query evaluation via tree-decompositions.

Query evaluation via tree-decompositions