PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 16.4 » Annexes » Modules et extensions supplémentaires fournis » ltree -- type de données hiérarchique style arbre

F.23. ltree -- type de données hiérarchique style arbre #

Ce module implémente le type de données ltree pour représenter des labels de données stockés dans une structure hiérarchique de type arbre. Des fonctionnalités étendues de recherche sont fournies.

Ce module est considéré comme « trusted », ce qui signifie qu'il peut être installé par des utilisateurs simples (sans attribut SUPERUSER) et qui ont l'attribut CREATE sur la base de données courante.

F.23.1. Définitions #

Un label est une séquence de caractères alphanumériques, tirets bas, et traits d'union. L'ensemble des caractères alphanumériques valides est dépendant de la locale de la base. Par exemple, dans la locale C, les caractères A-Za-z0-9_- sont autorisées. Les labels ne doivent pas avoir plus de 1000 caractères.

Exemples : 42, Personal_Services

Le chemin de label est une séquence de zéro ou plusieurs labels séparés par des points, par exemple L1.L2.L3, ce qui représente le chemin de la racine jusqu'à un nœud particulier. La longueur d'un chemin est limité à 65535 labels.

Exemple : Top.Countries.Europe.Russia

Le module ltree fournit plusieurs types de données :

  • ltree stocke un chemin de label.

  • lquery représente un type d'expression rationnelle du chemin pour la correspondance de valeurs de type ltree. Un mot simple établit une correspondance avec ce label dans un chemin. Le caractère joker (*) est utilisé pour spécifier tout nombre de labels (niveaux). Ils peuvent être liés avec des points pour former des motifs qui doivent correspondre au chemin entier du label. Par exemple :

    foo         Correspond au chemin exact foo
    *.foo.*     Correspond à tout chemin contenant le label foo
    *.foo       Correspond à tout chemin dont le dernier label est
    foo
         

    Les caractères joker et les mots simples peuvent être quantifiés pour restreindre le nombre de labels de la correspondance :

    *{n}        Correspond à exactement n labels
    *{n,}       Correspond à au moins n labels
    *{n,m}      Correspond à au moins n labels mais à pas plus de m
    *{,m}       Correspond à au moins m labels  --  identiques à *{0,m}
    foo{n,m}    Correspond à au moins n mais pas plus que m occurrences de foo
    foo{,}      Correspond à n'importe quel nombre d'occurrences de foo, incluant zéro
         

    En absence d'un quantificateur explicite, le défaut pour un symbole étoile est de correspondre à n'importe quel nombre de labels (c'est-à-dire {,}) tandis que le défaut pour un élément non-étoile est qu'il doit correspondre exactement une fois (c'est-à-dire {1}).

    Il existe plusieurs modificateurs qui peuvent être placés à la fin d'un élément lquery sans joker pour que la correspondance se fasse sur plus que la correspondance exacte :

    @           Correspondance sans vérification de casse, par exemple a@ établit une correspondance avec A
    *           Correspondance d'un préfixe pour un label, par exemple foo* établit une correspondance avec foobar
    %           Correspondance avec les mots séparés par des tirets bas
         

    Le comportement de % est un peu complexe. Il tente d'établir une correspondance avec des mots plutôt qu'avec un label complet. Par exemple, foo_bar% établit une correspondance avec foo_bar_baz mais pas avec foo_barbaz. S'il est combiné avec *, la correspondance du préfixe s'applique à chaque mot séparément. Par exemple, foo_bar%* établit une correspondance avec foo1_bar2_baz, mais pas avec foo1_br2_baz.

    Vous pouvez aussi écrire de nombreux éléments non-étoiles, modifiés ou non, séparés avec | (OR) pour correspondre à au moins un de ces éléments, et vous pouvez mettre un ! (NOT) au début d'un groupe non-étoile pour correspondre à tout label qui ne correspond à aucune alternative. Un quantificateur, s'il y a, va toujours à la fin du groupe ; cela signifie un certain nombre de correspondances pour le groupe entier (c'est-à-dire, un certain nombre de labels correspondants ou non correspondants à n'importe quelle alternative.)

    Voici un exemple annoté d'une lquery :

    Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain
    a.  b.     c.      d.                   e.
         

    Cette requête établira une correspondance avec tout chemin qui :

    1. commence avec le label Top

    2. et suit avec zéro ou deux labels jusqu'à

    3. un label commençant avec le préfixe sport quelque soit la casse

    4. puis un ou plusieurs labels, dont aucun ne correspond ni à football ni à tennis

    5. et se termine enfin avec un label commençant par Russ ou correspond strictement à Spain.

  • ltxtquery représente en quelque sorte une recherche plein texte pour la correspondance de valeurs ltree. Une valeur ltxtquery contient des mots, quelque fois avec les modificateurs @, *, % à la fin ; les modifications ont la même signification que dans un lquery. Les mots peuvent être combinés avec & (AND), | (OR), ! (NOT) et des parenthèses. La différence clé d'une lquery est que ltxtquery établit une correspondance avec des mots sans relation avec leur position dans le chemin de labels.

    Voici un exemple de ltxtquery :

         Europe & Russia*@ & !Transportation
         

    Ceci établira une correspondance avec les chemins contenant le label Europe et tout label commençant par Russia (quelque soit la casse), mais pas les chemins contenant le label Transportation. L'emplacement de ces mots dans le chemin n'est pas important. De plus, quand % est utilisé, le mot peut établir une correspondance avec tout mot séparé par un tiret bas dans un label, quelque soit sa position.

Note : ltxtquery autorise un espace blanc entre des symboles mais ltree et lquery ne le permettent pas.

F.23.2. Opérateurs et fonctions #

Le type ltree dispose des opérateurs de comparaison habituels =, <>, <, >, <=, >=. Les comparaisons trient dans l'ordre du parcours d'un arbre, avec les enfants d'un nœud trié par le texte du label. De plus, les opérateurs spécialisés indiqués dans Tableau F.13 sont disponibles.

Tableau F.13. Opérateurs ltree

Opérateur

Description

ltree @> ltreeboolean

L'argument gauche est-il un ancêtre de l'argument droit (ou identique) ?

ltree <@ ltreeboolean

L'argument gauche est-il un descendant de l'argument droit (ou identique) ?

ltree ~ lqueryboolean

lquery ~ ltreeboolean

Est-ce que ltree établie une correspondance avec lquery ??

ltree ? lquery[]boolean

lquery[] ? ltreeboolean

Est-ce que ltree établie une correspondance avec au moins un lquery dans ce tableau ?

ltree @ ltxtqueryboolean

ltxtquery @ ltreeboolean

Est-ce que ltree établie une correspondance avec ltxtquery ?

ltree || ltreeltree

Concatène des chemins ltree.

ltree || textltree

text || ltreeltree

Convertit du texte en ltree et concatène.

ltree[] @> ltreeboolean

ltree <@ ltree[]boolean

Est-ce que le tableau contient un ancêtre de ltree ?

ltree[] <@ ltreeboolean

ltree @> ltree[]boolean

Est-ce que le tableau contient un descendant de ltree ??

ltree[] ~ lqueryboolean

lquery ~ ltree[]boolean

Est-ce que le tableau contient au moins un chemin correspondant à lquery ??

ltree[] ? lquery[]boolean

lquery[] ? ltree[]boolean

Est-ce que le tableau ltree contient au moins un chemin correspondant à un lquery ?

ltree[] @ ltxtqueryboolean

ltxtquery @ ltree[]boolean

Est-ce que le tableau contient au moins un chemin correspondant à ltxtquery ??

ltree[] ?@> ltreeltree

Renvoie la première entrée du tableau ancêtre de ltree ou NULL sinon.

ltree[] ?<@ ltreeltree

Renvoie la première entrée du tableau qui est un descendant de ltree ou NULL sinon.

ltree[] ?~ lqueryltree

Renvoie la première entrée du tableau établissant une correspondance avec lquery et NULL sinon.

ltree[] ?@ ltxtqueryltree

Renvoie la première entrée du tableau établissant une correspondance avec ltxtquery et NULL sinon.


Lesopérateurs operators <@, @>, @ et ~ ont des versions analogues ^<@, ^@>, ^@, ^~, qui sont identiques sauf qu'elles n'utilisent pas les index. Elles sont utiles pour tester.

Les fonctions disponibles sont indiquées dans Tableau F.14.

Tableau F.14. Fonctions ltree

Fonction

Description

Exemple(s)

subltree ( ltree, start integer, end integer ) → ltree

Retourne le sous-chemin du ltree à partir de la position start jusqu'à la position end-1 (comptée à partir de 0).

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

subpath ( ltree, offset integer, len integer ) → ltree

Retourne le sous-ensemble du ltree en commençant à la position offset, avec une longueur len. Si offset est négatif, le sous-ensemble débute depuis la fin de chemin et s'étend vers le début. Si len est négatif, cela élimine ce nombre (en valeur absolue) de labels depuis la fin du chemin.

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

subpath ( ltree, offset integer ) → ltree

Retourne le sous-ensemble du ltree en commençant à la position offset, avec une longueur len. Si offset est négatif, le sous-ensemble débute depuis la fin de chemin et s'étend vers le début.

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

nlevel ( ltree ) → integer

Retourne le nombre de label dans le chemin.

nlevel('Top.Child1.Child2')3

index ( a ltree, b ltree ) → integer

Retourne la position de la première occurence de b dans a, ou -1 si non trouvé.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')6

index ( a ltree, b ltree, offset integer ) → integer

Retourne la position de la première occurence de b dans a, ou -1 si non trouvé. La recherche débute à la position offset ; un offset négatif indique un départ à -offset label depuis la fin du chemin.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6', -4)9

text2ltree ( text ) → ltree

Convertit un text en ltree.

ltree2text ( ltree ) → text

Convertit un ltree en text.

lca ( ltree [, ltree [, ... ]] ) → ltree

Calcule le plus long ancêtre commun des chemins. (8 arguments sont supportés au maximum).

lca('1.2.3', '1.2.3.4.5.6')1.2

lca ( ltree[] ) → ltree

Calcule le plus long ancêtre commun des chemins dans un tableau.

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


F.23.3. Index #

ltree accepte différents types d'index pouvant améliorer les performances des oopérateurs indiqués :

  • Index B-tree sur ltree : <, <=, =, >=, >

  • Index GiST sur ltree (classe d'opérateur gist_ltree_ops) : <, <=, =, >=, >, @>, <@, @, ~, ?

    La classe d'opérateur GiST gist_ltree_ops effectue une approximation sur un ensemble de chemins de labels sous format de signature bitmap. La taille de la signature par défaut est 8 octets. La longueur doit être un multiple positif de l'alignement d'un type int (4 octets sur la plupart des most machines) jusqu'à 2024. Des tailles de signatures plus longues permettent une recherche plus précise (en parcourant une fraction plus petite de l'index et moins de pages heap), au coût d'un plus large index.

    Exemple de création d'un tel index avec une taille de signature par défaut de 8 octets :

         CREATE INDEX path_gist_idx ON test USING GIST (path);
        

    Exemple de création d'un tel index avec une taille de signature de 100 octets :

    CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
        
  • Index GiST sur ltree[] (classe d'opérateur gist__ltree_ops : ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

    La classe d'opérateur GiST gist__ltree_ops fonctionne de façon similaire à gist_ltree_ops et aussi prend une taille de signature en paramètre. La valeur par défaut de siglen dans gist__ltree_ops est 28 octets.

    Exemple de création d'un tel index avec la taille de signature par défaut de 28 octets :

         CREATE INDEX path_gist_idx ON test USING GIST (array_path);
        

    Note : ce type d'index est à perte.

F.23.4. Exemple #

Cet exemple utilise les données suivantes (disponibles dans le fichier contrib/ltree/ltreetest.sql des sources) :

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);
  

Maintenant, nous avons une table test peuplée avec des données décrivant la hiérarchie ci-dessous :

                            Top
                         /   |  \
                 Science Hobbies Collections
                     /       |              \
            Astronomy   Amateurs_Astronomy Pictures
               /  \                            |
    Astrophysics  Cosmology                Astronomy
                                            /  |    \
                                     Galaxies Stars Astronauts
  

Nous pouvons faire de l'héritage :

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)
  

Voici quelques exemples de correspondance de chemins :

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)
  

Voici quelques exemples de recherche plein texte :

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)
  

Construction d'un chemin en utilisant les fonctions :

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)
  

Nous pouvons simplifier ceci en créant une fonction SQL qui insère un label à une position spécifié dans un chemin :

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.23.5. Transformations #

L'extension ltree_plpython3u implémente les transformations du type ltree pour PL/Python. Si elle est installée et indiquée lors de la création d'une fonction, les valeurs ltree sont converties en listes Python. Il est à noter que l'inverse n'est pas encore supportée.

Attention

Il est fortement recommandée que l'extension de transformation soit installée dans le même schéma que ltree. Sinon il existe un risque au moment de l'installation si le schéma de l'extension de transformation contient des objets définis par un utilisateur hostile.

F.23.6. Auteurs #

Tout le travail a été réalisé par Teodor Sigaev () et Oleg Bartunov (). Voir http://www.sai.msu.su/~megera/postgres/gist pour des informations supplémentaires. Les auteurs voudraient remercier Eugeny Rodichev pour son aide. Commentaires et rapports de bogue sont les bienvenus.