Document Server@UHasselt >
Research >
Research publications >

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
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
URI: http://hdl.handle.net/1942/4133
Link to publication: http://doi.acm.org/10.1145/1227839.1227843
ISI #: 000246013800004
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Validation: ecoom, 2008
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.