XPath Satisfiability with Parent Axes or Qualifiers Is Tractable under Many of Real-World DTDs

Yasunori Ishihara, Nobutaka Suzuki, Kenji Hashimoto +2

This paper aims at finding a subclass of DTDs that covers many of the real-world DTDs while offering a polynomial-time complexity for deciding the XPath satisfiability problem. In…