Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we consider the XPath satisfiability problem under restricted DTDs called "duplicate free". For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating an unsatisfiable XPath expression is meaningless, since such an expression can always be replaced by an empty set without evaluating it. However, it is shown that the XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([ ]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.
著者
-
Suzuki Nobutaka
Faculty Of Computer Science And System Engineering Okayama Prefectural University
-
FUKUSHIMA Yuji
Yahoo Japan Corporation
-
IKEDA Kosetsu
Graduate School of Library, Information and Media Studies, University of Tsukuba
関連論文
- リノレン酸メチルの自動酸化中におけるトリプシン阻害および促進物質の同時発現--トリプシン阻害物質の確認
- Accumulation of Fatty Acids in Chaetoceros gracilis (Bacillariophyceae) during Stationary Growth Phase
- Eatimation of Protein Content in Marine Microalgae Using the Lowry Method
- Complexity and a Method of Extracting a Database Schema over Semistructured Documents
- Extracting Typical Classes and a Database Schema from Semistructured Data
- Comparison of protease activity in liver among several species of squid and cuttlefish
- Virucidal effect of singlet oxygen on penaeid white spot syndrome virus
- Antioxidative Activity of Chlorophyll Derivatives, Oxygen Stress Relievers, to Superoxide Measured by Using Cypridina Luciferin analogues
- Antioxidative Activity of Amino Acids and Sulfur-containing Compounds to Superoxide : Measurement by Quenching the Chemiluminescence of a Cypridina Luciferin Analogue
- Reaction Rates for the Chemiluminescence of Cypridina Luciferin Analogues with Superoxide : A Quenching Experiment with Superoxide Dismutase(Organic Chemistry)
- Steady-State Near-infrared Detection of Singlet Molecular Oxygen : A Stern-Volmer Quenching Experiment with Luminol, Superoxide Dismutase, and Cypridina Luciferin Analogues(Organic Chemistry)
- N,N'-Dibromo-5,5-dimethylhydantoin and N-Bromosuccinimide, Chemical Sources of Singlet Molecular Oxygen : Observation of Singlet Oxygen with Ultra-sensitive Near-infrared Chemiluminescence Spectroscopy(Organic Chemistry)
- Studies on the Chemiluminescent Detection of Active Oxygen Species : 9-Acridone-2-sulfonic Acid, a Specific Probe for Superoxide(Organic Chemistry)
- Synthetic Reactions in PEG : PEG-Assisted Synthesis of 2-Cyano-6-methoxy-benzothiazole, A Key Intermediate For The Synthesis of Firefly Luciferin
- Net Profit and Marginal Net Profit in the Scoop Net Fishery of Ayu Population in Lake Biwa
- Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs