DTD存在下における兄弟軸を含むPositive XPathクエリの恒真性判定問題(論理と形式手法)

スポンサーリンク

概要

論文の詳細を見る
近年、構造化データを記述可能なXMLが盛んに利用されており、XML文書の特定の要素を指定する問合せ言語としてXPathが広く用いられている。XPathは、XML文書を木構造に見立て、その根頂点からの経路を記述することで、XML文書の特定の要素を指定する問合せ言語である。与えられたXPathクエリpに対してDTD Dに従うすべてのXML文書が解をもつとき、pはDのもとで恒真であるという。この恒真性を判定することは、XMLデータマッピング等において有用であることが知られている。本稿では、Positive XPathクエリの恒真性判定問題の計算複雑性について議論する。まず、XPathクエリが子軸、子孫軸、兄弟軸、ワイルドカードのみを含む場合にcoNP困難であることを示す。そして、子軸、兄弟軸、述語にワイルドカードを含めた場合にPTIMEに属することを示す。
一般社団法人電子情報通信学会の論文
2013-01-03

著者

関連論文

もっと見る

スポンサーリンク