書換えに基づく最適化のためのXQueryの相対コストモデル

日高 宗一郎  加藤 弘之  吉川 正俊  

誌名
電子情報通信学会論文誌 D   Vol.J91-D   No.4   pp.873-888
発行日: 2008/04/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 特集論文 (フォーマルアプローチ論文特集)
専門分野: データベース
キーワード: 
問合せ言語,  プログラム変換,  コストモデル,  

本文: PDF(678.2KB)
>>論文を購入


あらまし: 
XQueryはXMLに対する関数型の問合せ言語である.本論文では,ソースレベル変換の過程での性能利得を見積もることができるXQuery向けコストモデルを提案する.本研究の目的は,様々な書換え手法を実エンジンを導入することなしに評価することを容易にすることである.本コストモデルは言語のもつ関数型の構造に従った単純な再帰関数で構成される.それらは形式的意味論やよく知られた効率的なアルゴリズムを参考に決定している.変換の前後の式のコストの解析的な比較がエンジンによらず可能となっている.モデルの相対性により,解釈不要の成分を許容することができ,また,その部分はコスト比較の形式的な証明の妨げにもならない.更に,必要であれば被演算数の評価順等のエンジン固有の評価戦略を反映させるように改変することも可能となっている.