This module implements a data type <type>ltree</type> for representing
labels of data stored in a hierarchical tree-like structure.
Extensive facilities for searching through label trees are provided.
本モジュールは階層ツリーを模擬した構造に格納されたデータのラベルを表現する ltree
データ型を実装します。
ラベルツリー全体を検索する高度な機能を提供します。
This module is considered <quote>trusted</quote>, that is, it can be
installed by non-superusers who have <literal>CREATE</literal> privilege
on the current database.
このモジュールは「trusted」と見なされます。つまり、現在のデータベースに対してCREATE
権限を持つ非スーパーユーザがインストールできます。
A <firstterm>label</firstterm> is a sequence of alphanumeric characters,
underscores, and hyphens. Valid alphanumeric character ranges are
dependent on the database locale. For example, in C locale, the characters
<literal>A-Za-z0-9_-</literal> are allowed.
Labels must be no more than 1000 characters long.
ラベルは、英数字、アンダースコア、ハイフンの並びです。
有効な英数字の範囲はデータベースのロケールに依存します。
例えば、CロケールではA-Za-z0-9_-
という文字が許されます。
ラベルの長さは1000文字以内でなければなりません。
Examples: <literal>42</literal>, <literal>Personal_Services</literal>
例えば42
、Personal_Services
です。
A <firstterm>label path</firstterm> is a sequence of zero or more
labels separated by dots, for example <literal>L1.L2.L3</literal>, representing
a path from the root of a hierarchical tree to a particular node. The
length of a label path cannot exceed 65535 labels.
ラベル経路は、例えばL1.L2.L3
のようなドットで区切られた0個以上のラベルの並びであり、階層ツリーのルートから特定のノードまでの経路を表します。
ラベル経路の長さは65535ラベルを超えることはできません。
Example: <literal>Top.Countries.Europe.Russia</literal>
例:'Top.Countries.Europe.Russia'
The <filename>ltree</filename> module provides several data types:
ltree
モジュールは以下の複数のデータ型を提供します。
<type>ltree</type> stores a label path.
ltree
はラベル経路を格納します。
<type>lquery</type> represents a regular-expression-like pattern
for matching <type>ltree</type> values. A simple word matches that
label within a path. A star symbol (<literal>*</literal>) matches zero
or more labels. These can be joined with dots to form a pattern that
must match the whole label path. For example:
lquery
は、ltree
値に一致する正規表現のようなパターンを表現します。
単一の単語は経路内のラベルに一致します。
スター記号(*
)は0個以上のラベルに一致します。
ドットでつなげることで、ラベル経路全体に一致するパターンを形作ることができます。
以下に例を示します。
foo <lineannotation>Match the exact label path <literal>foo</literal></lineannotation> *.foo.* <lineannotation>Match any label path containing the label <literal>foo</literal></lineannotation> *.foo <lineannotation>Match any label path whose last label is <literal>foo</literal></lineannotation> foo 正確にfoo
というラベル経路に一致します。 *.foo.*foo
というラベルを含むラベル経路すべてに一致します。 *.foofoo
というラベルで終わるラベル経路すべてに一致します。
Both star symbols and simple words can be quantified to restrict how many labels they can match: スター記号と単一の単語のどちらも一致可能なラベル数を制限するために量指定を行うことができます。
*{<replaceable>n</replaceable>} <lineannotation>Match exactly <replaceable>n</replaceable> labels</lineannotation> *{<replaceable>n</replaceable>,} <lineannotation>Match at least <replaceable>n</replaceable> labels</lineannotation> *{<replaceable>n</replaceable>,<replaceable>m</replaceable>} <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> labels</lineannotation> *{,<replaceable>m</replaceable>} <lineannotation>Match at most <replaceable>m</replaceable> labels — same as </lineannotation>*{0,<replaceable>m</replaceable>} foo{<replaceable>n</replaceable>,<replaceable>m</replaceable>} <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> occurrences of <literal>foo</literal></lineannotation> foo{,} <lineannotation>Match any number of occurrences of <literal>foo</literal>, including zero</lineannotation> *{n
} 正確にn
個のラベルに一致します。 *{n
,} 少なくともn
個のラベルに一致します。 *{n
,m
} 少なくともn
個に一致し、多くてもm
個を超えないラベルに一致します。 *{,m
} 最大m
個のラベルに一致します。つまりと次と同じです。*{0,m
} foo{n
,m
} 少なくともn
個に一致し、多くてもm
個を超えないfoo
に一致します。 foo{,} ゼロを含む任意の数のfoo
に一致します。
In the absence of any explicit quantifier, the default for a star symbol
is to match any number of labels (that is, <literal>{,}</literal>) while
the default for a non-star item is to match exactly once (that
is, <literal>{1}</literal>).
明示的な量指定子が存在しなければ、スター記号に対するデフォルトは任意の数のラベルに一致(つまり{,}
)である一方、非スター項目に対するデフォルトは正確に1回(つまり{1}
)です。
There are several modifiers that can be put at the end of a non-star
<type>lquery</type> item to make it match more than just the exact match:
単なる正確な一致以上の一致を行うために、スターでないlquery
項目の終端に記述できる複数の修飾子が存在します。
@ <lineannotation>Match case-insensitively, for example <literal>a@</literal> matches <literal>A</literal></lineannotation> * <lineannotation>Match any label with this prefix, for example <literal>foo*</literal> matches <literal>foobar</literal></lineannotation> % <lineannotation>Match initial underscore-separated words</lineannotation> @ 大文字小文字を区別しない一致。例えばa@
はA
に一致します。 * この接頭辞を持つすべてのラベルに一致。例えばfoo*
はfoobar
に一致します。 % 最初のアンダースコアで区切られた単語に一致。
The behavior of <literal>%</literal> is a bit complicated. It tries to match
words rather than the entire label. For example
<literal>foo_bar%</literal> matches <literal>foo_bar_baz</literal> but not
<literal>foo_barbaz</literal>. If combined with <literal>*</literal>, prefix
matching applies to each word separately, for example
<literal>foo_bar%*</literal> matches <literal>foo1_bar2_baz</literal> but
not <literal>foo1_br2_baz</literal>.
%
の動作は多少複雑です。
ラベル全体ではなく単語一致を試みます。
例えばfoo_bar%
はfoo_bar_baz
に一致しますがfoo_barbaz
に一致しません。
*
と組み合わせる場合、接頭辞一致が各単語ごとに適用されます。
例えばfoo_bar%*
はfoo1_bar2_baz
に一致しますが、foo1_br2_baz
に一致しません。
Also, you can write several possibly-modified non-star items separated with
<literal>|</literal> (OR) to match any of those items, and you can put
<literal>!</literal> (NOT) at the start of a non-star group to match any
label that doesn't match any of the alternatives. A quantifier, if any,
goes at the end of the group; it means some number of matches for the
group as a whole (that is, some number of labels matching or not matching
any of the alternatives).
また、項目のいずれかに一致させるために|
(論理和)で区切って、修飾子が付いているかもしれない複数の非スター項目を記述することもできます。
さらに、非スターグループ先頭に!
(否定)を記述して選択肢のいずれにも一致しないすべてのラベルに一致させることもできます。
もしあれば、量指定子はグループの最後になります。これはグループ全体として一致する数を意味します(すなわち、一致するラベルの数、または、選択肢のいずれにも一致しない数です)。
Here's an annotated example of <type>lquery</type>:
以下に注釈付きのlquery
の例を示します。
Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain a. b. c. d. e.
This query will match any label path that: この問い合わせは以下のようなラベルに一致します。
begins with the label <literal>Top</literal>
Top
ラベルから始まる。
and next has zero to two labels before 次いで0から2個のラベルを持つ。
a label beginning with the case-insensitive prefix <literal>sport</literal>
直後にsport
接頭辞(大文字小文字の区別無)から始まるラベルを持つ。
then has one or more labels, none of which
match <literal>football</literal> nor <literal>tennis</literal>
そして、football
にもtennis
にも一致しない1つ以上のラベルを持つ。
and then ends with a label beginning with <literal>Russ</literal> or
exactly matching <literal>Spain</literal>.
Russ
から始まる、または、正確にSpain
に一致するラベルで終わる。
ltxtquery
はltree
値に対する全文検索のようなパターンを表します。
ltxtquery
値は、おそらく最後に@
、*
、%
修飾子を持った単語からなります。
修飾子の意味はlquery
と同じです。
単語は&
(論理積)、|
(論理和)、!
(否定)、括弧を組み合わせることが可能です。
主なlquery
との違いは、ltxtquery
はラベル経路上の位置を考慮せずに単語に一致することです。
Here's an example <type>ltxtquery</type>:
ltxtquery
の例を示します。
Europe & Russia*@ & !Transportation
This will match paths that contain the label <literal>Europe</literal> and
any label beginning with <literal>Russia</literal> (case-insensitive),
but not paths containing the label <literal>Transportation</literal>.
The location of these words within the path is not important.
Also, when <literal>%</literal> is used, the word can be matched to any
underscore-separated word within a label, regardless of position.
これはEurope
ラベルとRussia
(大文字小文字の区別無)から始まるラベルを含む経路に一致します。
しかし、Transportation
ラベルを含む経路は一致しません。
経路内の単語の位置は重要ではありません。
また、%
が使用された場合、位置に関係なく、単語をラベル内のアンダースコアで区切られた何らかの単語に一致させることができます。
Note: <type>ltxtquery</type> allows whitespace between symbols, but
<type>ltree</type> and <type>lquery</type> do not.
注意:ltxtquery
ではシンボルの間に空白を入れることができますが、ltree
とlquery
ではできません。
Type <type>ltree</type> has the usual comparison operators
<literal>=</literal>, <literal><></literal>,
<literal><</literal>, <literal>></literal>, <literal><=</literal>, <literal>>=</literal>.
Comparison sorts in the order of a tree traversal, with the children
of a node sorted by label text. In addition, the specialized
operators shown in <xref linkend="ltree-op-table"/> are available.
ltree
型は、通常の比較演算子=
、<>
、<
、>
、<=
、>=
を持ちます。
比較では、ツリーの巡回順でソートされ、ノードの子要素はラベルテキストでソートされます。
さらに、表 F.12に示す特殊な演算子が使用可能です。
表F.12 ltree
演算子
Operator 演算子 Description 説明 |
---|
Is left argument an ancestor of right (or equal)? 左辺の引数が右辺の祖先要素(か同じ)かどうか。 |
Is left argument a descendant of right (or equal)? 左辺の引数が右辺の子孫要素(か同じ)かどうか。 |
Does <type>ltree</type> match <type>lquery</type>?
|
Does <type>ltree</type> match any <type>lquery</type> in array?
|
Does <type>ltree</type> match <type>ltxtquery</type>?
|
Concatenates <type>ltree</type> paths.
|
Converts text to <type>ltree</type> and concatenates.
テキストを |
Does array contain an ancestor of <type>ltree</type>?
配列に |
Does array contain a descendant of <type>ltree</type>?
配列に |
Does array contain any path matching <type>lquery</type>?
配列に |
Does <type>ltree</type> array contain any path matching
any <type>lquery</type>?
|
Does array contain any path matching <type>ltxtquery</type>?
配列に |
Returns first array entry that is an ancestor of <type>ltree</type>,
or <literal>NULL</literal> if none.
|
Returns first array entry that is a descendant of <type>ltree</type>,
or <literal>NULL</literal> if none.
|
Returns first array entry that matches <type>lquery</type>,
or <literal>NULL</literal> if none.
|
Returns first array entry that matches <type>ltxtquery</type>,
or <literal>NULL</literal> if none.
|
The operators <literal><@</literal>, <literal>@></literal>,
<literal>@</literal> and <literal>~</literal> have analogues
<literal>^<@</literal>, <literal>^@></literal>, <literal>^@</literal>,
<literal>^~</literal>, which are the same except they do not use
indexes. These are useful only for testing purposes.
演算子<@
、@>
、@
、~
には類似の演算子^<@
、^@>
、^@
、^~
があります。
後者はインデックスを使用しない点を除き、同一です。
後者は試験の際にだけ役に立ちます。
The available functions are shown in <xref linkend="ltree-func-table"/>. 使用可能な関数を表 F.13に示します。
表F.13 ltree
関数
<filename>ltree</filename> supports several types of indexes that can speed
up the indicated operators:
ltree
は、以下で示された演算子を高速化できる、複数種類のインデックスをサポートします。
B-tree index over <type>ltree</type>:
<literal><</literal>, <literal><=</literal>, <literal>=</literal>,
<literal>>=</literal>, <literal>></literal>
ltree
に対するB-treeインデックス:<
、<=
、=
、>=
、>
Hash index over <type>ltree</type>:
<literal>=</literal>
《マッチ度[50.000000]》ltree
演算子
《機械翻訳》ハッシュインデックスオーバーltree
:=
.
GiST index over <type>ltree</type> (<literal>gist_ltree_ops</literal>
opclass):
<literal><</literal>, <literal><=</literal>, <literal>=</literal>,
<literal>>=</literal>, <literal>></literal>,
<literal>@></literal>, <literal><@</literal>,
<literal>@</literal>, <literal>~</literal>, <literal>?</literal>
ltree
に対するGiSTインデックス(gist_ltree_ops
演算子クラス):
<
、<=
、=
、>=
、>
、@>
、<@
、@
、~
、?
<literal>gist_ltree_ops</literal> GiST opclass approximates a set of
path labels as a bitmap signature. Its optional integer parameter
<literal>siglen</literal> determines the
signature length in bytes. The default signature length is 8 bytes.
The length must be a positive multiple of <type>int</type> alignment
(4 bytes on most machines)) up to 2024. Longer
signatures lead to a more precise search (scanning a smaller fraction of the index and
fewer heap pages), at the cost of a larger index.
gist_ltree_ops
GiST演算子クラスは経路ラベルの集合をビットマップ署名として近似します。
オプションの整数パラメータsiglen
は、署名の長さをバイト単位で決定します。
デフォルトの署名の長さは8バイトです。
長さは、int
整列(ほとんどのマシンで4バイト)の正の倍数であり、最大で2024であることが必要です。
長い署名では、インデックスはより大きくなってしまいますが、(インデックスのより小さな部分とより少ないヒープページをスキャンすることで)検索がより正確になります。
Example of creating such an index with the default signature length of 8 bytes: デフォルトの署名の長さが8バイトのインデックスを作成する例。
CREATE INDEX path_gist_idx ON test USING GIST (path);
Example of creating such an index with a signature length of 100 bytes: 署名の長さが100バイトのインデックスを作成する例。
CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
GiST index over <type>ltree[]</type> (<literal>gist__ltree_ops</literal>
opclass):
<literal>ltree[] <@ ltree</literal>, <literal>ltree @> ltree[]</literal>,
<literal>@</literal>, <literal>~</literal>, <literal>?</literal>
ltree[]
に対するGiSTインデックス(gist__ltree_ops
演算子クラス):ltree[] <@ ltree
、ltree @> ltree[]
、@
、~
、?
<literal>gist__ltree_ops</literal> GiST opclass works similarly to
<literal>gist_ltree_ops</literal> and also takes signature length as
a parameter. The default value of <literal>siglen</literal> in
<literal>gist__ltree_ops</literal> is 28 bytes.
gist__ltree_ops
GiST演算子クラスはgist_ltree_ops
と同じように動作しますが、署名の長さをパラメータとして取ります。
gist__ltree_ops
でのsiglen
のデフォルトの値は28バイトです。
Example of creating such an index with the default signature length of 28 bytes: デフォルトの署名の長さが28バイトのインデックスを作成する例。
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
Example of creating such an index with a signature length of 100 bytes: 署名の長さが100バイトのインデックスを作成する例。
CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));
Note: This index type is lossy. 注意:この種類のインデックスは非可逆です。
This example uses the following data (also available in file
<filename>contrib/ltree/ltreetest.sql</filename> in the source distribution):
この例は、後述のデータを使用します(ソース配布内の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); CREATE INDEX path_hash_idx ON test USING HASH (path);
Now, we have a table <structname>test</structname> populated with data describing
the hierarchy shown below:
これで、以下の階層を記述するデータが投入されたtest
テーブルができます。
Top / | \ Science Hobbies Collections / | \ Astronomy Amateurs_Astronomy Pictures / \ | Astrophysics Cosmology Astronomy / | \ Galaxies Stars Astronauts
We can do inheritance: 継承を行うことができます。
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)
Here are some examples of path matching: 経路一致の例をいくつか示します。
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)
Here are some examples of full text search: 全文検索の例をいくつか示します。
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)
Path construction using functions: 関数を使用した経路構築の例です。
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)
We could simplify this by creating an SQL function that inserts a label at a specified position in a path: 経路内の位置にラベルを挿入する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)
The <literal>ltree_plpython3u</literal> extension implements transforms for
the <type>ltree</type> type for PL/Python. If installed and specified when
creating a function, <type>ltree</type> values are mapped to Python lists.
(The reverse is currently not supported, however.)
ltree_plpython3u
拡張は、PL/Python用のltree
型の変換を実装します。
関数を作成するときにこの変換をインストールして指定していれば、ltree
の値はPythonのリストにマップされます。
(しかしながら、その逆は今のところサポートされていません。)
It is strongly recommended that the transform extension be installed in
the same schema as <filename>ltree</filename>. Otherwise there are
installation-time security hazards if a transform extension's schema
contains objects defined by a hostile user.
変換の拡張はltree
と同じスキーマにインストールすることを強く勧めます。
さもないと、変換の拡張のスキーマが悪意のあるユーザにより定義されたオブジェクトを含んでいた場合に、インストール時のセキュリティ問題になります。
All work was done by Teodor Sigaev (<email>teodor@stack.net</email>) and
Oleg Bartunov (<email>oleg@sai.msu.su</email>). See
<ulink url="http://www.sai.msu.su/~megera/postgres/gist/"></ulink> for
additional information. Authors would like to thank Eugeny Rodichev for
helpful discussions. Comments and bug reports are welcome.
開発はすべてTeodor Sigaev (<teodor@stack.net>
)とOleg Bartunov (<oleg@sai.msu.su>
)によりなされました。
さらなる情報についてはhttp://www.sai.msu.su/~megera/postgres/gist/を参照してください。
作者は有用な議論を行ったEugeny Rodichevに感謝しています。
コメントや不具合報告を歓迎します。