XPath Satisfiability with Parent Axes or Qualifiers Is Tractable under Many of Real-World DTDs.
Yasunori IshiharaNobutaka SuzukiKenji HashimotoShougo ShimizuToru FujiwaraPublished in: DBPL (2013)
Keyphrases
- sibling axes
- regular expressions
- xpath queries
- query containment
- satisfiability problem
- real world
- np complete
- pattern matching
- xml data
- conjunctive queries
- xml documents
- query answering
- case study
- data sets
- wide range
- query evaluation
- matching algorithm
- data mining
- query rewriting
- synthetic data
- transitive closure
- decision procedures
- computational complexity
- xml databases
- phase transition
- temporal logic
- query optimization
- tree automata
- xml streams
- relational databases
- integrity constraints
- np hard
- datalog programs