電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2013-01-10 13:00
DTD存在下における兄弟軸を含むPositive XPathクエリの恒真性判定問題
楠 洋平阪大)・橋本健二奈良先端大)・石原靖哲藤原 融阪大
抄録 (和) 近年,構造化データを記述可能なXMLが盛んに利用されており,XML文書の特定の要素を指定する問合せ言語としてXPath が広く用いられている.XPathは,XML文書を木構造に見立て,その根頂点からの経路を記述することで,XML文書の特定の要素を指定する問合せ言語である.与えられたXPathクエリ$p$に対してDTD $D$に従うすべてのXML文書が解をもつとき,$p$は$D$のもとで恒真であるという.この恒真性を判定することは,XMLデータマッピング等において有用であることが知られている.
本稿では,Positive XPathクエリの恒真性判定問題の計算複雑性について議論する.まず,XPathクエリが子軸,子孫軸,兄弟軸,ワイルドカードのみを含む場合にcoNP困難であることを示す.そして,子軸,兄弟軸,述語にワイルドカードを含めた場合にPTIMEに属することを示す. 
(英) In this paper, we discuss the complexity of the validity for positive XPath queries under the presence of DTDs. A given query $p$ is valid under a DTD $D$ if for each XML document conforming to $D$ the answer to $p$ is a nonempty set. Valid XPath queries are useful in XML data mapping settings.
We first show that the validity for the XPath class with only child, descendant-or-self and sibling axes, and wildcard is coNP-hard. Moreover, for the class with child and sibling axes, qualifier and wildcard, the validity is in PTIME.
キーワード (和) XML / XPath / 恒真性 / 計算複雑性 / / / /  
(英) XML / XPath / validity / complexity / / / /  
文献情報 信学技報, vol. 112, no. 373, SS2012-46, pp. 1-6, 2013年1月.
資料番号 SS2012-46 
発行日 2013-01-03 (SS) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
PDFダウンロード

研究会情報
研究会 SS  
開催期間 2013-01-10 - 2013-01-11 
開催地(和) 沖縄県石垣市民会館 
開催地(英)  
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 SS 
会議コード 2013-01-SS 
本文の言語 日本語 
タイトル(和) DTD存在下における兄弟軸を含むPositive XPathクエリの恒真性判定問題 
サブタイトル(和)  
タイトル(英) The validity problem of positive XPath queries with sibling axes in the presence of DTDs 
サブタイトル(英)  
キーワード(1)(和/英) XML / XML  
キーワード(2)(和/英) XPath / XPath  
キーワード(3)(和/英) 恒真性 / validity  
キーワード(4)(和/英) 計算複雑性 / complexity  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 楠 洋平 / Yohei Kusunoki / クスノキ ヨウヘイ
第1著者 所属(和/英) 大阪大学 (略称: 阪大)
Osaka University (略称: Osaka Univ.)
第2著者 氏名(和/英/ヨミ) 橋本 健二 / Kenji Hashimoto / ハシモト ケンジ
第2著者 所属(和/英) 奈良先端科学技術大学院大学 (略称: 奈良先端大)
Nara Institute of Science and Technology (略称: NAIST)
第3著者 氏名(和/英/ヨミ) 石原 靖哲 / Yasunori Ishihara / イシハラ ヤスノリ
第3著者 所属(和/英) 大阪大学 (略称: 阪大)
Osaka University (略称: Osaka Univ.)
第4著者 氏名(和/英/ヨミ) 藤原 融 / Toru Fujiwara / フジワラ トオル
第4著者 所属(和/英) 大阪大学 (略称: 阪大)
Osaka University (略称: Osaka Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2013-01-10 13:00:00 
発表時間 30 
申込先研究会 SS 
資料番号 IEICE-SS2012-46 
巻番号(vol) IEICE-112 
号番号(no) no.373 
ページ範囲 pp.1-6 
ページ数 IEICE-6 
発行日 IEICE-SS-2013-01-03 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会