ltree — тип данных для представления меток данных, хранящихся в древовидной иерархической структуре

Этот модуль реализует тип данных ltree для представления меток данных, хранящихся в древовидной иерархической структуре. Он также предоставляет расширенные средства для поиска в деревьях меток.

Этот модуль считается «доверенным», то есть его могут устанавливать обычные пользователи с правом CREATE в текущей базе данных.

Определения

Метка — это последовательность буквенно-цифровых символов, знаков подчеркивания и дефисов. Допустимые диапазоны буквенно-цифровых символов зависят от локали базы данных. Например, в локали C допускаются символы A-Za-z0-9_. Длина метки не должна превышать 1000 символов.

Примеры: 42, Personal_Services

Путь метки — это последовательность из нуля и более разделенных точками меток, например, L1.L2.L3, представляющая путь от корня иерархического дерева до конкретного узла. Длина пути метки не может превышать 65 535 меток.

Пример: Top.Countries.Europe.Russia

Модуль ltree предоставляет несколько типов данных:

  • ltree хранит путь метки.

  • lquery представляет похожий на регулярные выражения шаблон для поиска соответствующих значений ltree. В нем простое слово соответствует этой метке в пути, а символ звездочки (*) — нулю и более любых меток. Отдельные элементы можно соединить точками, чтобы сформировать шаблон, которому должен соответствовать весь путь метки. Например:

foo         Подбирает путь конкретно метки foo
*.foo.*     Подбирает любой путь, содержащий метку foo
*.foo       Подбирает любой путь с последней меткой foo

И для символов звездочки, и для простых слов можно добавить количественное
значение, ограничивающее число меток, которые будут соответствовать этому
элементу:

*{n}        Подбирает ровно n меток
*{n,}       Подбирает как минимум n меток
*{n,m}      Подбирает как минимум n, но не более m меток
*{,m}       Подбирает не более m меток — равнозначно *{0,m}
foo{n,m}    Подбирает как минимум n, но не более m вхождений foo
foo{,}      Подбирает любой количество вхождений foo, включая ноль

В отсутствие явного квантификатора символу звездочки по умолчанию соответствует
любое количество меток (то есть `{,}`), тогда как простому слову — ровно одна
(то есть `{1}`).

Существует несколько модификаторов, которые можно добавить после отличного от
звездочки элемента *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{1,}.Russ*|Spain
a.  b.     c.      d.                   e.

Этот запрос выберет любой путь, который: \
a. начинается с метки *Top* \
b. затем включает от нуля до двух меток до \
c. метки, начинающейся с префикса *sport* (без учета регистра) \
d. затем одну или более меток, отличных от *football* и *tennis* \
e. и заканчивается меткой, которая начинается с *Russ* или точно соответствует
   *Spain*.

  • ltxtquery представляет похожий на полнотекстовый поиска шаблон для подбора соответствующих значений ltree. Значение ltxtquery содержит слова, возможно, с модификаторами @, *, % в конце; эти модификаторы имеют тот же смысл, что и в lquery Слова можно комбинировать с символами & (И), | (ИЛИ), ! (НЕ) и скобками. Ключевое отличие от lquery состоит в том, что ltxtquery выбирает слова независимо от их положения в пути метки.

    Пример ltxtquery:

Europe & Russia*@ & !Transportation

Этот шаблон подберет пути, содержащие метку *Europe* и любую метку,
начинающуюся с *Russia* (без учета регистра), но не пути, содержащие метку
*Transportation*. Положение этих слов в пути не имеет значения. Кроме того,
когда используется **%**, слово может быть сопоставлено с любым другим
отделенным подчеркиванием словом в метке, независимо от его положения.

Примечание: ltxtquery допускает пробелы между символами, а ltree и lquery — нет.

Операторы и функции

Для типа ltree определены обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортирует пути в порядке движения по дереву, а потомки узла сортируются по тексту метки. В дополнение к ним доступны специализированные операторы, перечисленные ниже.

ltree @> ltree → boolean

Левый аргумент является предком правого (или равен ему)?

ltree <@ ltree → boolean

Левый аргумент является потомком правого (или равен ему)?

ltree ~ lquery → boolean
lquery ~ ltree → boolean

Значение ltree соответствует lquery?

ltree ? lquery[] → boolean
lquery[] ? ltree → boolean

Значение ltree соответствует какому-либо lquery в массиве?

ltree @ ltxtquery → boolean
ltxtquery @ ltree → boolean

Значение ltree соответствует ltxtquery?

ltree || ltree → ltree

Конкатенирует пути ltree.

ltree || text → ltree
text || ltree → ltree

Преобразует текст в ltree и конкатенирует его с путем.

ltree[] @> ltree → boolean
ltree <@ ltree[] → boolean

Массив содержит предка ltree?

ltree[] <@ ltree → boolean
ltree @> ltree[] → boolean

Массив содержит потомка ltree?

ltree[] ~ lquery → boolean
lquery ~ ltree[] → boolean

Массив содержит какой-либо путь, соответствующий lquery?

ltree[] ? lquery[] → boolean
lquery[] ? ltree[] → boolean

Массив ltree содержит какой-либо путь, соответствующий какому-либо lquery?

ltree[] @ ltxtquery → boolean
ltxtquery @ ltree[] → boolean

Массив содержит какой-либо путь, соответствующий ltxtquery?

ltree[] ?@> ltree → ltree

Возвращает первую запись массива, являющуюся предком ltree, или NULL, если такой записи нет.

ltree[] ?<@ ltree → ltree

Возвращает первую запись массива, являющуюся потомком ltree, или NULL, если такой записи нет.

ltree[] ?~ lquery → ltree

Возвращает первую запись массива, соответствующую lquery, или NULL, если такой записи нет.

ltree[] ?@ ltxtquery → ltree

Возвращает первую запись массива, соответствующую ltxtquery, или NULL, если такой записи нет.

У операторов <@, @>, @ и ~ есть аналоги ^<@, ^@>, ^@, ^~, которые отличаются тем, что не используют индексы. Они полезны только для тестирования.

Доступные функции ltree перечислены ниже.

subltree ( ltree, начало integer, конец integer ) → ltree

Возвращает подпуть ltree от позиции начало до позиции конец-1 (считая от 0).

subltree('Top.Child1.Child2', 1, 2) → Child1

subpath ( ltree, смещение integer, длина integer ) → ltree

Возвращает подпуть ltree, начиная с позиции смещение, длиной в заданное число меток. Если смещение отрицательное, подпуть начинается с этой позиции от конца пути. Если длина отрицательная, функция отбрасывает это число меток с конца пути.

subpath('Top.Child1.Child2', 0, 2) → Top.Child1

subpath ( ltree, смещение integer ) → ltree

Возвращает подпуть ltree, начиная с позиции смещение и до конца пути. Если смещение отрицательное, подпуть начинается с этой позиции от конца пути.

subpath('Top.Child1.Child2', 1) → Child1.Child2

nlevel ( ltree ) → integer

Возвращает количество меток в пути.

nlevel('Top.Child1.Child2') → 3

index ( a ltree, b ltree ) → integer

Возвращает позицию первого вхождения b в a или -1, если такое вхождение не найдено.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6') → 6

index ( a ltree, b ltree, смещение integer ) → integer

Возвращает позицию первого вхождения b в a или -1, если такое вхождение не найдено. Поиск начинается с позиции смещение; отрицательное смещение означает, что поиск начинается с этой позиции от конца пути.

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.3', '1.2.3.4.5.6') → 1.2

lca ( ltree[] ) → ltree

Вычисляет длиннейшего общего предка путей в массиве.

lca(array['1.2.3'::ltree,'1.2.3.4']) → 1.2

Индексы

ltree поддерживает несколько типов индексов, которые могут ускорить указанные операторы:

  • Индекс B-дерево по значениям ltree: <, <=, =, >=, >

  • Индекс GiST по значениям ltree (класс операторов gist_ltree_ops): <, <=, =, >=, >, @>, <@, @, ~, ?

    Класс операторов GiST gist_ltree_ops аппроксимирует набор меток пути в виде сигнатуры битовой карты. Его необязательный целочисленный параметр siglen определяет длину сигнатуры в байтах. Значение по умолчанию — 8 байт. Длина сигнатуры должна быть положительным значением до 2024, кратным выравниванию по целым (int) (4 байта для большинства машин). При увеличении размера сигнатуры поиск работает точнее (сканируется меньшая область индекса и меньше страниц кучи), но сам индекс становится больше.

    Пример создания такого индекса с длиной сигнатуры по умолчанию (8 байт):

CREATE INDEX path_gist_idx ON test USING GIST (path);

Пример создания такого индекса с длиной сигнатуры 100 байт:

CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));

  • Индекс GiST по массиву ltree[] (класс операторов gist__ltree_ops): ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

    Класс операторов GiST gist__ltree_ops работает подобно gist_ltree_ops и тоже принимает в качестве параметра длину сигнатуры. По умолчанию значение siglen в gist__ltree_ops составляет 28 байт.

    Пример создания такого индекса с длиной сигнатуры по умолчанию (28 байт):

CREATE INDEX path_gist_idx ON test USING GIST (array_path);

Пример создания такого индекса с длиной сигнатуры 100 байт:

CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));

Примечание: Индекс этого типа является неточным.

Пример

Для этого примера используются следующие данные:

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)

Авторы

Разработку полностью осуществили Федор Сигаев (teodor@stack.net) и Олег Бартунов (oleg@sai.msu.su). Дополнительную информацию см. на странице http://www.sai.msu.su/~megera/postgres/gist/. Авторы выражают благодарность Евгению Родичеву за полезные дискуссии. Комментарии и сообщения об ошибках приветствуются.

Copyright © KVANTOM LLC, 2019-2025