A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes

Autor:	Shougo Shimizu, Yasunori Ishihara, Kenji Hashimoto, Toru Fujiwara, Takuji Morimoto
Rok vydání:	2009
Předmět:	computer.internet_protocol Computer science InformationSystems_DATABASEMANAGEMENT Satisfiability Subclass Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Regular expression Sibling computer Algorithm XPath Superclass
Zdroj:	Database Programming Languages ISBN: 9783642037924 DBPL
Popis:	The paper presents a tractable subclass of DTDs, called DC-DTDs, for XPath satisfiability with sibling axes. A DC-DTD is a DTD such that each content model is in the form of a concatenation of single tag names and Kleene-starred regular expressions. DC-DTDs are a proper subclass of covering DTDs proposed by Montazerian et al., and a proper superclass of disjunction-free DTDs. In this paper, it is shown that tractability by covering DTDs is fragile against sibling axes. Then, tractability of XPath satisfiability with sibling axes under DC-DTDs is demonstrated. Finally, as a limitation of the tractability of DC-DTDs, it is shown that upward axes appearing in qualifiers bring intractability under even disjunction-free DTDs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e12284fca1e61d0a469c317fc2c5f22e https://doi.org/10.1007/978-3-642-03793-1_5 Zobrazit plný text záznamu