2026-03-10T04:18:02Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00160381 2025-01-20T12:20:21Z 581:8417:8709

XPath充足可能性を判定する多項式時間アルゴリズムの提案と評価 Proposal and Evaluation of Polynomial-time Algorithms for Deciding XPath Satisfiability 杉村, 憲司 石原, 靖哲 藤原, 融 Kenji, Sugimura Yasunori, Ishihara Toru, Fujiwara [一般論文（推薦論文）] 問合せ解析，充足可能性，XPath，XMLデータベース XPath充足可能性判定問題は，問合せの最適化などに応用できる重要な問題であるが，一般にはNP困難であることが知られている．そのため，DTDやXPath式のクラスを制限することで，多項式時間で充足可能性を判定できるアルゴリズムを提案する研究が行われている．本論文では，多項式時間充足可能性判定アルゴリズムを提案・実装し，その有用性を評価する．実装の結果，一般的なベンチマークに対して数十ミリ秒で判定でき，SATソルバを用いた手法に比べて十分に高速であることが分かった． 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. journal article 2016-05-15 application/pdf 情報処理学会論文誌 5 57 1477 1488 1882-7764 AN00116647 https://ipsj.ixsq.nii.ac.jp/record/160381/files/IPSJ-JNL5705018.pdf jpn