PostgreSQLLa base de données la plus sophistiquée au monde.

F.15. 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.

F.15.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 octets.

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é à 65 Ko, mais une longueur inférieure ou égale à 2 Ko est préférable. Nous considérons qu'il ne s'agit pas d'une limitation stricte. Par exemple, lataille maximum d'un chemin de label dans le catalogue DMOZ fait environ 240 octets !

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). 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 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  --  identique à *{0,m}
         
    

    Il existe plusieurs modificateurs qui peuvent être placés à la fin d'un label sans joker dans un lquery 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.

    De plus, vous pouvez écrire plusieurs labels séparés avec des | (OR) pour établir une correspondance avec un des labels, et vous pouvez placer un ! (NOT) au début pour établir une correspondance avec tout sauf une des différentes alternatives.

    Voici un exemple annoté d'une lquery :

         Top.*{0,2}.sport*@.!football|tennis.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. ensuite un label ne correspondant ni à football ni à tennis

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

  • ltxtquery represente 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.15.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, il existe les opérateurs spécialisés suivant :

Tableau F.11. Opérateurs ltree

Opérateur Retour 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 est-ce que ltree établie une correspondance avec lquery ?
lquery ~ ltree boolean est-ce que ltree établie une correspondance avec lquery ?
ltree ? lquery[] boolean est-ce que ltree établie une correspondance avec tout any lquery dans ce tableau ?
lquery[] ? ltree boolean est-ce que ltree établie une correspondance avec tout lquery dans ce tableau ?
ltree @ ltxtquery boolean est-ce que ltree établie une correspondance avec ltxtquery ?
ltxtquery @ ltree boolean est-ce que ltree établie une correspondance avec ltxtquery ?
ltree || ltree ltree concatène des chemins ltree
ltree || text ltree convertit du texte en ltree et concatène
text || ltree ltree convertit du texte en ltree et concatène
ltree[] @> ltree boolean est-ce que le tableau contient un ancêtre de ltree ?
ltree <@ ltree[] boolean est-ce que le tableau contient un ancêtre de ltree ?
ltree[] <@ ltree boolean est-ce que le tableau contient un descendant de ltree ?
ltree @> ltree[] boolean est-ce que le tableau contient un descendant de ltree ?
ltree[] ~ lquery boolean est-ce que le tableau contient tout chemin correspondant à lquery ?
lquery ~ ltree[] boolean est-ce que le tableau contient tout chemin correspondant à lquery ?
ltree[] ? lquery[] boolean est-ce que le tableau ltree contient tout chemin correspondant à un lquery ?
lquery[] ? ltree[] boolean est-ce que le tableau ltree contient tout chemin correspondant à un lquery ?
ltree[] @ ltxtquery boolean est-ce que le tableau contient tout chemin correspondant à ltxtquery ?
ltxtquery @ ltree[] boolean est-ce que le tableau contient tout chemin correspondant à ltxtquery ?
ltree[] ?@> ltree ltree première entrée du tableau ancêtre de ltree ; NULL si aucun
ltree[] ?<@ ltree ltree première entrée du tableau descendant de ltree ; NULL si aucun
ltree[] ?~ lquery ltree première entrée du tableau établissant une correspondance avec lquery ; NULL si aucune
ltree[] ?@ ltxtquery ltree première entrée du tableau établissant une correspondance avec ltxtquery ; NULL si aucune

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 suivantes sont disponibles :

Tableau F.12. Fonctions ltree

Fonction Type en retour Description Exemple Résultat
subltree(ltree, int start, int end) ltree sous-chemin de of ltree de la position start à la position end-1 (counting from 0) subltree('Top.Child1.Child2',1,2) Child1
subpath(ltree, int offset, int len) ltree sous-chemin de ltree commençant à la position offset, de longueur len. Si offset est négatif, le sous-chemin commence de ce nombre à partir de la fin du chemin. Si len est négatif, laisse ce nombre de labels depuis la fin du chemin. subpath('Top.Child1.Child2',0,2) Top.Child1
subpath(ltree, int offset) ltree sous-chemin de ltree commençant à la position offset, s'étendant à la fin du chemin. Si offset est négatif, le sous-chemin commence de ce point jusqu'à la fin du chemin. subpath('Top.Child1.Child2',1) Child1.Child2
nlevel(ltree) integer nombre de labels dans le chemin nlevel('Top.Child1.Child2') 3
index(ltree a, ltree b) integer position de la première occurrence de b dans a ; -1 si introuvable index('0.1.2.3.5.4.5.6.8.5.6.8','5.6') 6
index(ltree a, ltree b, int offset) integer position de la première occurrence de b dans a, la recherche commence à offset ; un offset négatif signifie un commencement à -offset labels de 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 du text en ltree
ltree2text(ltree) text convertit du ltree en text
lca(ltree, ltree, ...) ltree plus petit ancêtre commun, c'est-à-dire préfixe commun le plus long des chemins (jusqu'à huit arguments supportés) lca('1.2.2.3','1.2.3.4.5.6') 1.2
lca(ltree[]) ltree plus petit ancêtre commun, c'est-à-dire préfixe commun le plus long des chemins lca(array['1.2.2.3'::ltree,'1.2.3']) 1.2

F.15.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 : <, <=, =, >=, >, @>, <@, @, ~, ?

    Exemple de la création d'un tel index :

         CREATE INDEX path_gist_idx ON test USING GIST (path);
        
    
  • Index GiST sur ltree[] : ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

    Exemple de la création d'un tel index :

         CREATE INDEX path_gist_idx ON test USING GIST (array_path);
        
    

    Note : ce type d'index est à perte.

F.15.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.15.5. 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.