Expressive Power and Data Complexity of Query Languages for Trees and Lists.
Evgeny DantsinAndrei VoronkovPublished in: PODS (2000)
Keyphrases
- expressive power
- data complexity
- query language
- data model
- relational algebra
- monadic second order logic
- transitive closure
- first order logic
- recursive queries
- exptime complete
- query evaluation
- computational properties
- regular expressions
- regular path queries
- relational query languages
- database
- conjunctive queries
- tree automata
- relational calculus
- relational data model
- constraint databases
- special case
- databases