F.28. ltree — иерархический древовидный тип данных#

F.28. ltree — иерархический древовидный тип данных
F.28. ltree — иерархический древовидный тип данных
Назад НаверхПриложение F. Дополнительные поставляемые модули и расширенияНачало Далее

F.28. ltree — иерархический древовидный тип данных #

F.28.1. Определения
F.28.2. Операторы и функции
F.28.3. Индексы
F.28.4. Пример
F.28.5. Преобразования
F.28.6. Авторы

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

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

F.28.1. Определения #

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

Примеры: 42, Personal_Services

Метка пути (label path) - это последовательность нуля или более меток, разделенных точками, например 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.

    Этот запрос будет соответствовать любому пути метки, который:

    1. начинается с метки Top

    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.28.2. Операторы и функции #

Тип ltree имеет обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортируется в порядке обхода дерева, с детьми узла, отсортированными по тексту метки. Кроме того, доступны специализированные операторы, показанные в Таблица F.13.

Таблица F.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, если таковых нет.


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

Все доступные функции показаны в Таблица F.14.

Таблица F.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


F.28.3. Индексы #

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

  • Индекс B-дерева над lдерево: <, <=, =, >=, >

  • Индекс GiST над ltree (gist_ltree_ops opclass): <, <=, =, >=, >, @>, <@, @, ~, ?

    gist_ltree_ops GiST opclass приближает набор меток пути как битовую подпись. Его необязательный целочисленный параметр siglen определяет длину подписи в байтах. Стандартная длина подписи составляет 8 байт. Длина должна быть положительным кратным int выравнивания (4 байта на большинстве машин) до 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 opclass): ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

    gist__ltree_ops Операторная классификация GiST работает аналогично 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));

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

F.28.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, заполненная данными, описывающими иерархию, показанную ниже: 

Вверх
                     /   |  \
             Наука Хобби Коллекции
                 /       |              \
        Астрономия   Любители_астрономии Картинки
           /  \                            |
Астрофизика  Космология                Астрономия
                                        /  |    \
                                 Галактики Звезды Космонавты

можно использовать наследование: 

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.28.5. Преобразования #

Расширение ltree_plpython3u реализует преобразования для типа ltree для PL/Python. Если оно установлено и указано при создании функции, значения типа ltree отображаются на списки Python. (Обратное в настоящее время не поддерживается, однако).

Предостережение

Сильно рекомендуется установить расширение transform в той же схеме, что и ltree. В противном случае, при установке могут возникнуть проблемы с безопасностью, если схема расширения transform содержит объекты, определенные вредоносным пользователем.

F.28.6. Авторы #

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

Назад Наверх Далее
F.27. lo — управление большими объектами Начало F.29. old_snapshot — проверка состояния old_snapshot_threshold