Documentation PostgreSQL 15.15 » Annexes » Modules supplémentaires fournis » ltree

Précédent | Niveau supérieur | Suivant
F.22. lo | Sommaire | F.24. old_snapshot

## F.23. ltree

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 et de tirets bas (par exemple, dans la locale C, les caractères `A-Za-z0-9_` sont autorisés). La longueur d'un label est limité par 256 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 plus 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` `@>` `ltree` → `boolean` L'argument gauche est-il un ancêtre de l'argument droit (ou identique) ?
`ltree` `<@` `ltree` → `boolean` L'argument gauche est-il un descendant de l'argument droit (ou identique) ?
`ltree` `~` `lquery` → `boolean` `lquery` `~` `ltree` → `boolean` Est-ce que `ltree` établit une correspondance avec `lquery` ??
`ltree` `?` `lquery[]` → `boolean` `lquery[]` `?` `ltree` → `boolean` Est-ce que `ltree` établit une correspondance avec au moins un `lquery` dans ce tableau ?
`ltree` `@` `ltxtquery` → `boolean` `ltxtquery` `@` `ltree` → `boolean` Est-ce que `ltree` établit une correspondance avec `ltxtquery` ?
`ltree` `||` `ltree` → `ltree` Concatène des chemins `ltree`.
`ltree` `||` `text` → `ltree` `text` `||` `ltree` → `ltree` Convertit du texte en `ltree` et concatène.
`ltree[]` `@>` `ltree` → `boolean` `ltree` `<@` `ltree[]` → `boolean` Est-ce que le tableau contient un ancêtre de `ltree` ?
`ltree[]` `<@` `ltree` → `boolean` `ltree` `@>` `ltree[]` → `boolean` Est-ce que le tableau contient un descendant de `ltree` ??
`ltree[]` `~` `lquery` → `boolean` `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[]` `@` `ltxtquery` → `boolean` `ltxtquery` `@` `ltree[]` → `boolean` Est-ce que le tableau contient au moins un chemin correspondant à `ltxtquery` ??
`ltree[]` `?@>` `ltree` → `ltree` Renvoie la première entrée du tableau ancêtre de `ltree` ou NULL sinon.
`ltree[]` `?<@` `ltree` → `ltree` Renvoie la première entrée du tableau qui est un descendant de `ltree` ou NULL sinon.
`ltree[]` `?~` `lquery` → `ltree` Renvoie la première entrée du tableau établissant une correspondance avec `lquery` et NULL sinon.
`ltree[]` `?@` `ltxtquery` → `ltree` Renvoie la première entrée du tableau établissant une correspondance avec `ltxtquery` et NULL sinon.

Les opé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 occurrence 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 occurrence 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 opérateurs indiqués :

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

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

  La classe d'opérateurs 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 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érateurs `gist__ltree_ops` : `ltree[] <@ ltree`, `ltree @> ltree[]`, `@`, `~`, `?`

  La classe d'opérateurs 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ée 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é 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 (`<teodor@stack.net>`) et Oleg Bartunov (`<oleg@sai.msu.su>`). 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.