XPath充足可能性を判定する多項式時間アルゴリズムの提案と評価

• Item type: Journal(1)
• 公開日: 2016-05-15
• タイトル: XPath充足可能性を判定する多項式時間アルゴリズムの提案と評価
• タイトル / 言語: en
• タイトル: Proposal and Evaluation of Polynomial-time Algorithms for Deciding XPath Satisfiability
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文（推薦論文）] 問合せ解析，充足可能性，XPath，XMLデータベース
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 大阪大学
• 著者所属: 大阪大学
• 著者所属: 大阪大学
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者名: 杉村, 憲司; 石原, 靖哲; 藤原, 融
• 著者名(英): Kenji, Sugimura; Yasunori, Ishihara; Toru, Fujiwara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: XPath充足可能性判定問題は，問合せの最適化などに応用できる重要な問題であるが，一般にはNP困難であることが知られている．そのため，DTDやXPath式のクラスを制限することで，多項式時間で充足可能性を判定できるアルゴリズムを提案する研究が行われている．本論文では，多項式時間充足可能性判定アルゴリズムを提案・実装し，その有用性を評価する．実装の結果，一般的なベンチマークに対して数十ミリ秒で判定でき，SATソルバを用いた手法に比べて十分に高速であることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: XPath satisfiability is an important problem that is useful for query optimization, but it is known to be NP-hard in general. Therefore, some researches propose polynomial-time algorithms for deciding XPath satisfiability for some restricted classes of DTDs and XPath expressions. In this paper, we propose and implement polynomial-time algorithms for XPath satisfiability, and discuss their usefulness. The satisfiability of a standard benchmark can be decided in several tens of milliseconds; it is much faster than the methods based on SAT solvers.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 57, 号 5, p. 1477-1488, 発行日 2016-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764