F.15. ltree

F.15.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.15.2. 演算子と関数

ltree型は、通常の比較演算子=、<>、<、>、<=、>=を持ちます。 比較では、ツリーの巡回順でソートされ、ノードの子要素はラベルテキストでソートされます。 さらに、以下の特殊な演算子が存在します。

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

以下の関数が使用可能です。

F.15.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.15.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.15.5. 作者

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