Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/4133
Title: | Logical definability and query languages over ranked and unranked trees | Authors: | Benedikt, Michael Libkin, Leonid NEVEN, Frank |
Issue Date: | 2007 | Publisher: | ASSOC COMPUTING MACHINERY | Source: | ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 8(2) | Abstract: | We study relations on trees defined by first-order constraints over a vocabulary that includes the tree extension relation T < T' (holding if and only if every branch of T extends to a branch of T'), unary node-tests, and a binary relation checking whether the domains of two trees are equal. We consider both ranked and unranked trees. These are trees with and without a restriction on the number of children of nodes. We adopt the model-theoretic approach to tree relations and study relations definable over the structure consisting of the set of all trees and the aforementioned predicates. We relate definability of sets and relations of trees to computability by tree automata. We show that some natural restrictions correspond to familiar logics in the more classical setting where every tree is a structure over a fixed vocabulary, and to logics studied in the context of XML pattern languages. We then look at relational calculi over collections of trees, and obtain quantifier-restriction results that give us bounds on the expressive power and complexity. As unrestricted relational calculi can express problems that are complete for each level of the polynomial hierarchy, we look at their restrictions, corresponding to the restricted logics over the family of all unranked trees, and find several calculi with low (NC1) data complexity which still express properties important for database and document applications. We also give normal forms for safe queries in the calculus. | Notes: | Univ Edinburgh, Sch Informat, Edinburgh EH8 9LE, Midlothian, Scotland. Bell Labs, Naperville, IL 60566 USA. Hasselt Univ, Sch Informat Technol, B-3590 Diepenbeek, Belgium. Transnat Univ Limburg, B-3590 Diepenbeek, Belgium.Benedikt, M, Univ Edinburgh, Sch Informat, Edinburgh EH8 9LE, Midlothian, Scotland.benedikt@research.bell-labs.com libkin@inf.ed.ac.uk frank.neven@uhasselt.be | Document URI: | http://hdl.handle.net/1942/4133 | Link to publication/dataset: | http://doi.acm.org/10.1145/1227839.1227843 | ISSN: | 1529-3785 | e-ISSN: | 1557-945X | ISI #: | 000246013800004 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2008 |
Appears in Collections: | Research publications |
Show full item record
WEB OF SCIENCETM
Citations
5
checked on Oct 14, 2024
Page view(s)
74
checked on May 30, 2023
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.