Loading...
Please wait, while we are loading the content...
Similar Documents
Query Evaluation via Tree-Decompositions (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Flum, Jörg Frick, Markus Grohe, Martin |
| 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 paper we consider arbitrary formulas on tree-like structures. We generalize a theorem of Courcelle [8] 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 wellknown guarded fragment and the finite-variable fragments of first-order logic, respectively. |
| File Format | |
| Volume Number | 49 |
| Journal | JOURNAL OF THE ACM |
| Language | English |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Finite Relational Structure Second Part Finite-variable Fragment First Part Straightforward Way Conjunctive Query Structure Size Tree-width Fragment Monadic Second-order Formula Second-order Variable Arbitrary Formula Tree-like Structure Monadic-second Order Query Arbitrary Structure Arbitrary First-order Formula Time Linear Tree-like Formula Efficient Method Expressive Power First-order Logic |
| Content Type | Text |
| Resource Type | Article |
