無料スクリプト配布のPHP.TO   PHPの実用的なtips PHPマニュアル MySQLマニュアル Apacheマニュアル PostgreSQLマニュアル マニュアル検索    

F.21. ltree

本モジュールは階層ツリーを模擬した構造に格納されたデータのラベルを表現する ltree データ型を実装します。 ラベルツリー全体を検索する高度な機能を提供します。

F.21.1. 定義

ラベル は、アルファベット文字とアンダースコア(例えばCロケールでは A-Za-z0-9_ 文字が許されます。)の並びです。 ラベルの長さは256バイト未満でなければなりません。

例えば 42 Personal_Services です。

ラベル経路 は、例えば L1.L2.L3 のようなドットで区切られた0個以上のラベルの並びであり、階層ツリーのルートから特定のノードまでの経路を表します。 ラベル経路の長さは65キロバイトまでに制限されていますが、2キロバイト以下のサイズがよく使われます。 実際のところこれは主要な制限ではありません。 例えばDMOZカタログ( http://www.dmoz.org )における最大ラベル経路はおよそ240バイトです。

例: 'Top.Countries.Europe.Russia'

ltree モジュールは以下の複数のデータ型を提供します。

  • ltree はラベル経路を格納します。

  • lquery は、 ltree 値に一致する正規表現のようなパターンを表現します。 単一の単語は経路内のラベルに一致します。 スター記号( * )は0個以上のラベルに一致します。 以下に例を示します。

    foo         
    正確に
    foo
    というラベル経路に一致します。
    
    *.foo.*     
    
    foo
    というラベルを含むラベル経路すべてに一致します。
    
    *.foo       
    
    foo
    というラベルで終わるラベル経路すべてに一致します。
    

    スター印は一致可能なラベル数を制限するために量指定を行うことができます。

    *{
    
    n
    
    }        
    正確に
    
    n
    
    個のラベルに一致します。
    
    *{
    
    n
    
    ,}       
    少なくとも
    
    n
    
    個のラベルに一致します。
    
    *{
    
    n
    
    ,
    
    m
    
    }      
    少なくとも
    
    n
    
    個に一致し、多くても
    
    m
    
    個を超えないラベルに一致します。
    
    *{,
    
    m
    
    }       
    最大
    
    m
    
    個のラベルに一致します。つまり
     *{0,
    
    m
    
    }と同じです。

    単なる正確な一致以上の一致を行うために、 lquery の非スターラベルの終端に記述することができる複数の修飾子が存在します。

    @           
    大文字小文字を区別しない一致。例えば
    a@
    A
    に一致します。
    
    *           
    この接頭辞を持つすべてのラベルに一致。例えば
    foo*
    foobar
    に一致します。
    
    %           
    最初のアンダースコアで区切られた単語に一致。
    

    % の動作は多少複雑です。 ラベル全体ではなく単語一致を試みます。 例えば foo_bar% foo_bar_baz に一致しますが foo_barbaz に一致しません。 * と組み合わせる場合、接頭辞一致が各単語ごとに適用されます。 例えば foo_bar%* foo1_bar2_baz に一致しますが、 foo1_br2_baz に一致しません。

    また、ラベルのいずれかに一致させるために | (論理和)で区切って、複数のおそらく修飾子が付いたラベルを記述することもできます。 さらに、先頭に ! (否定)を記述して選択肢のいずれかにも一致しないすべてのラベルに一致させることもできます。

    以下に注釈付きの lquery の例を示します。

    Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain
    a.  b.     c.      d.               e.

    この問い合わせは以下のようなラベルに一致します。

    1. Top ラベルから始まる。

    2. 次いで0から2個のラベルを持つ。

    3. 直後に sport 接頭辞(大文字小文字の区別無)から始まるラベルを持つ。

    4. そして、 football tennis に一致しないラベルを持つ。

    5. Russ から始まる、または、正確に Spain に一致するラベルで終わる。

  • ltxtquery ltree 値に対する全文検索のようなパターンを表します。 ltxtquery 値は、おそらく最後に @ * % 修飾子を持った単語からなります。 修飾子の意味は lquery と同じです。 単語は & (論理積)、 | (論理和)、 ! (否定)、括弧を組み合わせることが可能です。 主な lquery との違いは、 ltxtquery はラベル経路上の位置を考慮せずに単語に一致することです。

    ltxtquery の例を示します。

    Europe & Russia*@ & !Transportation

    これは Europe ラベルと Russia (大文字小文字の区別無)から始まるラベルを含む経路に一致します。 しかし、 Transportation ラベルを含む経路は一致しません。 経路内の単語の位置は重要ではありません。 また、 % が使用された場合、位置に関係なく、単語をラベル内のアンダースコアで区切られた何らかの単語に一致させることができます。

注意: ltxtquery ではシンボルの間に空白を入れることができますが、 ltree lquery ではできません。

F.21.2. 演算子と関数

ltree 型は、通常の比較演算子 = <> < > <= >= を持ちます。 比較では、ツリーの巡回順でソートされ、ノードの子要素はラベルテキストでソートされます。 さらに、 表F-12 に示す特殊な演算子が使用可能です。

表 F-12. ltree 演算子

演算子 戻り値 説明
ltree @> ltree boolean 左辺の引数が右辺の祖先要素(か同じ)かどうか
ltree <@ ltree boolean 左辺の引数が右辺の子孫要素(か同じ)かどうか
ltree ~ lquery boolean ltree lquery に一致するかどうか
lquery ~ ltree boolean ltree lquery に一致するかどうか
ltree ? lquery[] boolean ltree が配列内のいずれかの lquery に一致するかどうか
lquery[] ? ltree boolean ltree が配列内のいずれかの lquery に一致するかどうか
ltree @ ltxtquery boolean ltree ltxtquery に一致するかどうか
ltxtquery @ ltree boolean ltree ltxtquery に一致するかどうか
ltree || ltree ltree ltree 経路を連結します
ltree || text ltree テキストを ltree に変換し、連結します
text || ltree ltree テキストを ltree に変換し、連結します
ltree[] @> ltree boolean 配列に ltree の祖先要素が含まれるかどうか
ltree <@ ltree[] boolean 配列に ltree の祖先要素が含まれるかどうか
ltree[] <@ ltree boolean 配列に ltree の子孫要素が含まれるかどうか
ltree @> ltree[] boolean 配列に ltree の子孫要素が含まれるかどうか
ltree[] ~ lquery boolean 配列に lquery に一致する経路が含まれるかどうか
lquery ~ ltree[] boolean 配列に lquery に一致する経路が含まれるかどうか
ltree[] ? lquery[] boolean ltree 配列にいずれかの lquery に一致する経路が含まれるかどうか
lquery[] ? ltree[] boolean ltree 配列にいずれかの lquery に一致する経路が含まれるかどうか
ltree[] @ ltxtquery boolean 配列に ltxtquery に一致する経路が含まれるかどうか
ltxtquery @ ltree[] boolean 配列に ltxtquery に一致する経路が含まれるかどうか
ltree[] ?@> ltree ltree ltree の祖先要素となる配列内の最初の要素。存在しなければNULL
ltree[] ?<@ ltree ltree ltree の子孫要素となる配列内の最初の要素。存在しなければNULL
ltree[] ?~ lquery ltree lquery に一致する配列内の最初の要素。存在しなければNULL
ltree[] ?@ ltxtquery ltree ltxtquery に一致する配列内の最初の要素。存在しなければNULL

<@ @> @ ~ 演算子は ^<@ ^@> ^@ ^~ と類似です。 これらはインデックスを使用しない点を除き、同一です。 これらは試験の際にだけ役に立ちます。

使用可能な関数を 表F-13 に示します。

表 F-13. ltree 関数

関数 戻り値型 説明 結果
subltree(ltree, int start, int end) ltree start 位置から end -1位置までの ltree の部分経路(位置は0から始まります)。 subltree('Top.Child1.Child2',1,2) Child1
subpath(ltree, int offset, int len) ltree offset 位置から len 個の ltree の部分経路(位置は0から始まります)。 offset が負の場合、部分経路は経路の終端から数えた位置から始まります。 len が負の場合、経路の終端から指定個のラベルを除きます。 subpath('Top.Child1.Child2',0,2) Top.Child1
subpath(ltree, int offset) ltree offset 位置から経路の終端までの ltree の部分経路(位置は0から始まります)。 offset が負の場合、部分経路は経路の終端から数えた位置から始まります。 subpath('Top.Child1.Child2',1) Child1.Child2
nlevel(ltree) integer 経路内のラベル数 nlevel('Top.Child1.Child2') 3
index(ltree a, ltree b) integer a 内で b が最初に出現する位置。存在しなければ-1 index('0.1.2.3.5.4.5.6.8.5.6.8','5.6') 6
index(ltree a, ltree b, int offset) integer a 内で offset から検索を始めて b が最初に出現する位置。 負の offset は経路終端から -offset ラベルから検索を始めることを意味します。 index('0.1.2.3.5.4.5.6.8.5.6.8','5.6',-4) 9
text2ltree(text) ltree text ltree にキャスト
ltree2text(ltree) text ltree text にキャスト
lca(ltree, ltree, ...) ltree 最少共通祖先。つまり、経路で共通する最長接頭辞。(最大8個の引数をサポート) lca('1.2.2.3','1.2.3.4.5.6') 1.2
lca(ltree[]) ltree 最少共通祖先。つまり、経路で共通する最長接頭辞。 lca(array['1.2.2.3'::ltree,'1.2.3']) 1.2

F.21.3. インデックス

ltree は、以下で示された演算子を高速化できる、複数種類のインデックスをサポートします。

  • ltree に対するB-treeインデックス: < <= = >= >

  • ltree に対するGiSTインデックス: < <= = >= > @> <@ @ ~ ?

    インデックスの作成例を以下に示します。

    CREATE INDEX path_gist_idx ON test USING GIST (path);
  • ltree[] に対するGiSTインデックス: ltree[] <@ ltree ltree @> ltree[] @ ~ ?

    インデックスの作成例を以下に示します。

    CREATE INDEX path_gist_idx ON test USING GIST (array_path);

    注意:この種類のインデックスは非可逆です。

F.21.4. 例

この例は、後述のデータを使用します(ソース配布内の contrib/ltree/ltreetest.sql ファイルでも利用可能です)。

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING gist(path);
CREATE INDEX path_idx ON test USING btree(path);

これで、以下の階層を記述するデータが投入された test テーブルができます。

                        Top
                     /   |  \
             Science Hobbies Collections
                 /       |              \
        Astronomy   Amateurs_Astronomy Pictures
           /  \                            |
Astrophysics  Cosmology                Astronomy
                                        /  |    \
                                 Galaxies Stars Astronauts

継承を行うことができます。

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)

経路一致の例をいくつか示します。

ltreetest=> SELECT path FROM test WHERE path ~ '*.Astronomy.*';
                     path
-----------------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Collections.Pictures.Astronomy
 Top.Collections.Pictures.Astronomy.Stars
 Top.Collections.Pictures.Astronomy.Galaxies
 Top.Collections.Pictures.Astronomy.Astronauts
(7 rows)

ltreetest=> SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

全文検索の例をいくつか示します。

ltreetest=> SELECT path FROM test WHERE path @ 'Astro*% & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Hobbies.Amateurs_Astronomy
(4 rows)

ltreetest=> SELECT path FROM test WHERE path @ 'Astro* & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

関数を使用した経路構築の例です。

ltreetest=> SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE path <@ 'Top.Science.Astronomy';
                 ?column?
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

経路内の位置にラベルを挿入するSQL関数を作成することで、これを簡略化することができます。

CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree
    AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);'
    LANGUAGE SQL IMMUTABLE;

ltreetest=> SELECT ins_label(path,2,'Space') FROM test WHERE path <@ 'Top.Science.Astronomy';
                ins_label
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

F.21.5. 作者

開発はすべてTeodor Sigaev ( )とOleg Bartunov ( )によりなされました。 さらなる情報については http://www.sai.msu.su/~megera/postgres/gist/ を参照してください。 作者は有用な議論を行ったEugeny Rodichevに感謝しています。 コメントや不具合報告を歓迎します。


powered by SEO.CUG.NET