データベースシステムにおける列問い合わせの最適化

データベースの列における複雑で再発するパターンを検索する必要は多くのアプリケーションで共通しています。本論文では、これらのパターンを効率的に表現しサポートする方法について議論します。そのために、まずこれらのパターンを表現するためのSQLの拡張であるSQL-TSを紹介し、次にこの言語のための検索クエリを最適化する方法を検討します。我々は、Knuth、Morris、Prattの最適なテキスト検索アルゴリズムを採用し、シーケンスに対する複雑なクエリを扱うように一般化します。我々のアルゴリズムは、シーケンシャルパターンの要素間の相互依存関係を活用して、同じデータに対する繰り返しのパスを最小限に抑えます。ダブルボトムクエリなどの典型的な列クエリに関する実験結果は、我々の新しい最適化技術によって大幅な速度向上が達成されることを確認しています。