Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version).
Antoine AmarilliPierre BourhisMikaël MonetPierre SenellartPublished in: CoRR (2016)
Keyphrases
- query evaluation
- tree automata
- regular expressions
- monadic second order logic
- data complexity
- query language
- query processing
- conjunctive queries
- finite automata
- data management
- transitive closure
- efficient query evaluation
- xml data
- querying xml documents
- probabilistic databases
- np complete
- tree languages
- finite state
- probabilistic xml
- expressive power
- data model
- computational complexity
- machine learning
- context free grammars
- pspace complete
- inverted lists