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.
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 exactfoo
*.foo.* Correspond à tout chemin contenant le labelfoo
*.foo Correspond à tout chemin dont le dernier label estfoo
Les caractères joker et les mots simples peuvent être quantifiés pour restreindre le nombre de labels de la correspondance :
*{n
} Correspond à exactementn
labels *{n
,} Correspond à au moinsn
labels *{n
,m
} Correspond à au moinsn
labels mais à pas plus dem
*{,m
} Correspond à au moinsm
labels -- identiques à *{0,m
} foo{n
,m
} Correspond à au moinsn
mais pas plus quem
occurrences defoo
foo{,} Correspond à n'importe quel nombre d'occurrences defoo
, 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 exemplea@
établit une correspondance avecA
* Correspondance d'un préfixe pour un label, par exemplefoo*
établit une correspondance avecfoobar
% 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 :
commence avec le label Top
et suit avec zéro ou deux labels jusqu'à
un label commençant avec le préfixe sport
quelque
soit la casse
puis un ou plusieurs labels, dont aucun ne correspond ni à
football
ni à tennis
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.
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 |
---|
L'argument gauche est-il un ancêtre de l'argument droit (ou identique) ? |
L'argument gauche est-il un descendant de l'argument droit (ou identique) ? |
Est-ce que |
Est-ce que |
Est-ce que |
Concatène des chemins |
Convertit du texte en |
Est-ce que le tableau contient un ancêtre de
|
Est-ce que le tableau contient un descendant de
|
Est-ce que le tableau contient au moins un chemin correspondant à
|
Est-ce que le tableau |
Est-ce que le tableau contient au moins un chemin correspondant à
|
Renvoie la première entrée du tableau ancêtre de
|
Renvoie la première entrée du tableau qui est un descendant de
|
Renvoie la première entrée du tableau établissant une correspondance avec
|
Renvoie la première entrée du tableau établissant une correspondance avec
|
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
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.
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)
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.
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.
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.