XPath satisfiability with downward and sibling axes is tractable under most of real-world DTDs
Yasunori Ishihara, Kenji Hashimoto, Shogo Shimizu, Toru Fujiwara · 2012
This paper aims at finding a subclass of DTDs that covers real-world DTDs but still has non-trivial tractability for XPath satisfiability problem. Known subclasses of DTDs, such as duplicate-free DTDs proposed by Montazerian et al. and disjunction-capsuled DTDs and their extension called DC?+-DTDs proposed by Ishihara et al., have tractability against various XPath classes but are somewhat smaller than real-world DTDs. In our examination, 6 out of 27 real-world DTDs are neither duplicate-free nor disjunction-capsuled.