Документация по PostgreSQL 9.4.1 | |||
---|---|---|---|
Пред. | Уровень выше | Приложение E. Дополнительно поставляемые модули | След. |
E.21. ltree
Этот модуль реализует тип данных ltree для представления меток данных в иерархической древовидной структуре. Он также предоставляет расширенные средства для поиска в таких деревьях.
E.21.1. Определения
Метка — это последовательность алфавитно-цифровых символов и знаков подчёркивания (например, в локали C допускаются символы A-Za-z0-9_). Метки должны занимать меньше 256 байт.
Примеры: 42, Personal_Services
Путь метки — это последовательность из нуля или более меток, разделённых точками, (например, L1.L2.L3), представляющая путь от корня иерархического дерева к конкретному узлу. Длина пути метки должна быть меньше 65 КБ, но лучше, если она будет в пределах 2 КБ. На практике это ограничение не является критичным; например, самый длинный путь в каталоге DMOZ (http://www.dmoz.org) имеет длину около 240 байт.
Пример: 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}
В конце метки, отличной от звёздочки, в 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.
Этот запрос выберет путь, который:
начинается с метки Top
и затем включает от нуля до двух меток до
метки, начинающейся с префикса sport (без учёта регистра)
затем метку, отличную от football и tennis
и заканчивается меткой, которая начинается подстрокой Russ или в точности равна Spain.
ltxtquery представляет подобный полнотекстовому запрос поиска подходящих значений ltree. Значение ltxtquery содержит слова, возможно с модификаторами @, *, % в конце; эти модификаторы имеют то же значение, что и в lquery. Слова можно объединять символами & (И), | (ИЛИ), ! (НЕ) и скобками. Ключевое отличие от lquery состоит в том, что ltxtquery выбирает слова независимо от их положения в пути метки.
Пример ltxtquery:
Europe & Russia*@ & !Transportation
Этот запрос выберет пути, содержащие метку Europe или любую метку с начальной подстрокой Russia (без учёта регистра), но не пути, содержащие метку Transportation. Положение этих слов в пути не имеет значения. Кроме того, когда применяется %, слово может быть сопоставлено с любым другим отделённым подчёркиваниями словом в метке, вне зависимости от его положения.
Замечание: ltxtquery допускает пробелы между символами, а ltree и lquery — нет.
E.21.2. Операторы и функции
Для типа ltree определены обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортирует пути в порядке движения по дереву, а потомки узла сортируются по тексту метки. В дополнение к ним есть и специализированные операторы, перечисленные в Таблице E-12.
Таблица E-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, если такого нет |
Операторы <@, @>, @ и ~ имеют аналоги в виде ^<@, ^@>, ^@, ^~, которые отличатся только тем, что не используют индексы. Они полезны только для тестирования.
Доступные функции перечислены в Таблице E-13.
Таблица E-13. Функции ltree
Функция | Тип результата | Описание | Пример | Результат |
---|---|---|---|---|
subltree(ltree, int start, int end) | ltree | подпуть ltree от позиции start до позиции end-1 (начиная с 0) | subltree('Top.Child1.Child2',1,2) | Child1 |
subpath(ltree, int offset, int len) | ltree | подпуть ltree, начиная с позиции offset, длиной len. Если offset меньше нуля, подпуть начинается с этого смещения от конца пути. Если len меньше нуля, будет отброшено заданное число меток с конца строки. | subpath('Top.Child1.Child2',0,2) | Top.Child1 |
subpath(ltree, int offset) | ltree | подпуть ltree, начиная с позиции offset и до конца пути. Если offset меньше нуля, подпуть начинается с этого смещения от конца пути. | subpath('Top.Child1.Child2',1) | Child1.Child2 |
nlevel(ltree) | integer | число меток в пути | nlevel('Top.Child1.Child2') | 3 |
index(ltree a, ltree b) | integer | позиция первого вхождения b в a; -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 | позиция первого вхождения b в a, найденного от позиции offset; если offset меньше 0, поиск начинается с -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 |
E.21.3. Индексы
ltree поддерживает несколько типов индексов, которые могут ускорить означенные операции:
B-дерево по значениям ltree: <, <=, =, >=, >
GiST по значениям ltree: <, <=, =, >=, >, @>, <@, @, ~, ?
Пример создания такого индекса:
CREATE INDEX path_gist_idx ON test USING GIST (path);
GiST по колонке ltree[]: ltree[] <@ ltree, ltree @> ltree[], @, ~, ?
Пример создания такого индекса:
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
Примечание: Индекс этого типа является неточным.
E.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)
E.21.5. Авторы
Разработку осуществили Фёдор Сигаев (<teodor@stack.net>
) и Олег Бартунов (<oleg@sai.msu.su>
). Дополнительные сведения можно найти на странице http://www.sai.msu.su/~megera/postgres/gist/. Авторы выражают благодарность Евгению Родичеву за полезную дискуссии. Замечания и сообщения об ошибках приветствуются.
Пред. | Начало | След. |
lo | Уровень выше | pageinspect |