Loading...
Please wait, while we are loading the content...
Similar Documents
Logical definability and query languages over unranked trees (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Libkin, Leonid |
| Description | Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science (LICS |
| Abstract | Unranked trees, that is, trees with no restriction on the number of children of nodes, have recently attracted much attention, primarily as an abstraction of XML documents. In this paper, we study logical definability over unranked trees, as well as collections of unranked trees, that can be viewed as databases of XML documents. The traditional approach to definability is to view each tree as a structure of a fixed vocabulary, and study the expressive power of various logics on trees. A different approach, based on model theory, considers a structure whose universe is the set of all trees, and studies definable sets and relations; this approach extends smoothly to the setting of definability over collections of trees. We study the latter, model-theoretic approach. We find sets of operations on unranked trees that define regular tree languages, and show that some natural restrictions correspond to logics studied in the context of XML pattern languages. We then look at relational calculi over collections of unranked trees, and obtain quantifierrestriction results that give us bounds on the expressive power and complexity. As unrestricted relational calculi can express problems 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 (NC 1) data complexity, that can express important XML properties like DTD validation and XPath evaluation. 1. |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Regular Tree Language Study Definable Set Expressive Power Relational Calculus Logical Definability Different Approach Xpath Evaluation Fixed Vocabulary Several Calculus Data Complexity Query Language Various Logic Model-theoretic Approach Traditional Approach Polynomial Hierarchy Natural Restriction Correspond Unranked Tree Much Attention Model Theory Xml Pattern Language Important Xml Property Xml Document Dtd Validation Quantifierrestriction Result Unrestricted Relational Calculus |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings Article |
