ltree
Этот модуль реализует тип данных ltree для представления меток данных, хранящихся в древовидной иерархической структуре. Он также предоставляет расширенные средства для поиска в деревьях меток.
Этот модуль считается «доверенным», то есть его могут устанавливать обычные пользователи с правом CREATE в текущей базе данных.
Определения
Метка — это последовательность буквенно-цифровых символов и знаков подчеркивания (например, в локали C допускаются символы A-Za-z0-9_). Длина метки должна быть меньше 256 символов.
Примеры: 42, Personal_Services
Путь метки — это последовательность из нуля и более разделенных точками меток, например L1.L2.L3, представляющая путь от корня иерархического дерева к конкретному узлу. Длина пути метки не может составлять более 65535 меток.
Пример: 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 определены обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортирует пути в порядке движения по дереву, а потомки узла сортируются по тексту метки. В дополнение к ним доступны специализированные операторы, перечисленные в Таблице 13.
Таблица 13. Операторы 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, если такой записи нет. |
У операторов <@, @>, @ и ~ есть аналоги ^<@, ^@>, ^@, ^~, которые отличаются только тем, что не используют индексы. Они полезны только для тестирования.
Доступные функции перечислены в Таблице 14.
Таблица 14. Функции ltree
Функция | Описание | Пример(ы) |
---|---|---|
subltree ( ltree, start integer, end integer ) → ltree | Возвращает подпуть ltree от позиции start до позиции end-1 (считая от 0). | subltree('Top.Child1.Child2', 1, 2) → Child1 |
subpath ( ltree, offset integer, len integer ) → ltree | Возвращает подпуть ltree, начиная с позиции offset, длиной len. Если offset отрицательный, подпуть начинается с этого смещения от конца пути. Если len отрицательный, функция отбрасывает заданное количество меток с конца пути. | subpath('Top.Child1.Child2', 0, 2) → Top.Child1 |
subpath ( ltree, offset integer ) → ltree | Возвращает подпуть ltree, начиная с позиции offset и до конца пути. Если offset отрицательный, подпуть начинается с этого смещения от конца пути. | 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, offset integer ) → integer | Возвращает позицию первого вхождения b в a или -1, если такое вхождение не найдено. Поиск начинается с позиции offset; отрицательный 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.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 байтов. Допустима длина сигнатуры в пределах от 1 до 2024 байтов. При увеличении размера сигнатур поиск работает точнее (сканируется меньшая область индекса и меньше страниц кучи), но сам индекс становится больше.
Пример создания такого индекса с длиной сигнатуры по умолчанию (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));
Примечание: Индекс этого типа является неточным.
Пример
Для этого примера используются следующие данные (также их можно найти в файле 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)
Трансформации
Также имеются дополнительные расширения, которые реализуют трансформацию типа ltree для языка PL/Python. Эти расширения называются ltree_plpythonu, ltree_plpython2u и ltree_plpython3u. Если вы установите эти трансформации и укажите их при создании функции, значения ltree будут отображаться в списки Python. (Однако обратное преобразование в настоящее время не поддерживается.)
Внимание
Настоятельно рекомендуется устанавливать расширения трансформации в одну схему с ltree. Если выбрать какую-либо другую схему, которая может содержать объекты, определенные злонамеренным пользователем, то при установке расширения возникнут угрозы безопасности.
Авторы
Разработку осуществили Федор Сигаев (teodor@stack.net) и Олег Бартунов (oleg@sai.msu.su). Дополнительную информацию см. на странице http://www.sai.msu.su/~megera/postgres/gist/. Авторы выражают благодарность Евгению Родичеву за полезные дискуссии. Комментарии и сообщения об ошибках приветствуются.