Este módulo implementa un tipo de datos ltree para representar
etiquetas de datos almacenados en una estructura jerárquica similar a un árbol.
Se proporcionan amplias facilidades para realizar búsquedas en árboles de etiquetas.
Este módulo se considera «confiable» (trusted), es decir, puede ser
instalado por no superusuarios que tengan el privilegio CREATE
en la base de datos actual.
Una etiqueta (label) es una secuencia de caracteres
alfanuméricos, guiones bajos y guiones. Los rangos de caracteres alfanuméricos
válidos dependen de la configuración regional (locale) de la base de datos.
Por ejemplo, en la configuración regional C, se permiten los caracteres
A-Za-z0-9_-.
Las etiquetas no deben tener más de 1000 caracteres de longitud.
Ejemplos: 42, Personal_Services
Una ruta de etiquetas (label path) es una secuencia de cero o
más etiquetas separadas por puntos, por ejemplo L1.L2.L3, que representa
una ruta desde la raíz de un árbol jerárquico hasta un nodo particular. La
longitud de una ruta de etiquetas no puede exceder las 65535 etiquetas.
Ejemplo: Top.Countries.Europe.Russia
El módulo ltree proporciona varios tipos de datos:
ltree almacena una ruta de etiquetas.
lquery representa un patrón similar a una expresión regular
para hacer coincidir valores de tipo ltree. Una palabra simple
coincide con esa etiqueta dentro de una ruta. Un símbolo de estrella
(*) coincide con cero o más etiquetas. Estos pueden unirse
con puntos para formar un patrón que debe coincidir con toda la ruta de
etiquetas. Por ejemplo:
foo Coincidir exactamente con la ruta de etiquetasfoo*.foo.* Coincidir con cualquier ruta de etiquetas que contenga la etiquetafoo*.foo Coincidir con cualquier ruta de etiquetas cuya última etiqueta seafoo
Tanto los símbolos de estrella como las palabras simples se pueden cuantificar para restringir cuántas etiquetas pueden coincidir:
*{n} Coincidir exactamente con n etiquetas
*{n,} Coincidir con al menos n etiquetas
*{n,m} Coincidir con al menos n pero no más de m etiquetas
*{,m} Coincidir a lo sumo con m etiquetas — lo mismo que *{0,m}
foo{n,m} Coincidir con al menos n pero no más de m ocurrencias de foo
foo{,} Coincidir con cualquier número de ocurrencias de foo, incluyendo cero
A falta de cualquier cuantificador explícito, el comportamiento predeterminado
para un símbolo de estrella es coincidir con cualquier número de etiquetas
(es decir, {,}), mientras que el predeterminado para un
elemento que no sea estrella es coincidir exactamente una vez (es decir,
{1}).
Existen varios modificadores que se pueden colocar al final de un elemento de
tipo lquery que no sea estrella para que coincida con algo más que la
coincidencia exacta:
@ Coincidir sin distinguir mayúsculas de minúsculas, por ejemploa@coincide conA* Coincidir con cualquier etiqueta que tenga este prefijo, por ejemplofoo*coincide confoobar% Coincidir con palabras iniciales separadas por guiones bajos
El comportamiento de % es un poco complicado. Intenta
hacer coincidir palabras individuales en lugar de toda la etiqueta. Por ejemplo,
foo_bar% coincide con foo_bar_baz pero no
con foo_barbaz. Si se combina con *,
la coincidencia de prefijos se aplica a cada palabra por separado; por ejemplo,
foo_bar%* coincide con foo1_bar2_baz pero
no con foo1_br2_baz.
También puedes escribir varios elementos que no sean estrellas (posiblemente
modificados) separados por | (OR) para que coincidan con
cualquiera de ellos, y puedes colocar ! (NOT) al inicio de
un grupo que no sea estrella para coincidir con cualquier etiqueta que no
coincida con ninguna de las alternativas. Si hay un cuantificador, se coloca
al final del grupo; esto significa cierta cantidad de coincidencias para el
grupo en su conjunto (es decir, cierta cantidad de etiquetas que coinciden o
no coinciden con ninguna de las alternativas).
Aquí tienes un ejemplo anotado de lquery:
Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain
a. b. c. d. e.
Esta consulta coincidirá con cualquier ruta de etiquetas que:
comience con la etiqueta Top
y luego tenga de cero a dos etiquetas antes de
una etiqueta que comience con el prefijo sport (sin distinguir mayúsculas de minúsculas)
luego tenga una o más etiquetas, ninguna de las cuales coincida con
football ni con tennis
y finalmente termine con una etiqueta que comience con Russ o
coincida exactamente con Spain.
ltxtquery representa un patrón similar al de búsqueda de texto
completo para hacer coincidir valores de tipo ltree. Un
valor de tipo ltxtquery contiene palabras, posiblemente con los
modificadores @, *, % al final;
los modificadores tienen el mismo significado que en lquery.
Las palabras se pueden combinar con & (AND),
| (OR), ! (NOT) y paréntesis.
La diferencia clave con respecto a
lquery es que ltxtquery busca coincidir con palabras sin
importar su posición en la ruta de etiquetas.
Aquí tienes un ejemplo de ltxtquery:
Europe & Russia*@ & !Transportation
Esto coincidirá con rutas que contengan la etiqueta Europe y
cualquier etiqueta que comience con Russia (sin distinguir
mayúsculas de minúsculas), pero no con rutas que contengan la etiqueta
Transportation. La ubicación de estas palabras dentro de la ruta
no es importante. Además, cuando se usa %, la palabra puede
coincidir con cualquier palabra separada por guiones bajos dentro de una etiqueta,
independientemente de su posición.
Nota: ltxtquery permite espacios en blanco entre símbolos, pero
ltree y lquery no.
El tipo ltree tiene los operadores de comparación habituales
=, <>,
<, >, <=, >=.
La comparación se ordena según el recorrido de un árbol, con los hijos
de un nodo ordenados por el texto de la etiqueta. Además, están disponibles
los operadores especializados que se muestran en la Table F.12.
Table F.12. Operadores de ltree
Operador Descripción |
|---|
¿El argumento izquierdo es ancestro del derecho (o igual)? |
¿El argumento izquierdo es descendiente del derecho (o igual)? |
¿El |
¿El |
¿El |
Concatena rutas de |
Convierte texto a |
¿El array contiene un ancestro de |
¿El array contiene un descendiente de |
¿El array contiene alguna ruta que coincida con el |
¿El array de |
¿El array contiene alguna ruta que coincida con el |
Devuelve la primera entrada del array que sea ancestro de |
Devuelve la primera entrada del array que sea descendiente de |
Devuelve la primera entrada del array que coincida con el |
Devuelve la primera entrada del array que coincida con el |
Los operadores <@, @>,
@ y ~ tienen análogos
^<@, ^@>, ^@,
^~, los cuales son iguales excepto que no utilizan
índices. Estos son útiles solo para fines de prueba.
Las funciones disponibles se muestran en la Table F.13.
Table F.13. Funciones de ltree
ltree admite varios tipos de índices que pueden acelerar
los operadores indicados:
Índice B-tree sobre ltree:
<, <=, =,
>=, >
Índice Hash sobre ltree:
=
Índice GiST sobre ltree (clase de operador gist_ltree_ops):
<, <=, =,
>=, >,
@>, <@,
@, ~, ?
La clase de operador GiST gist_ltree_ops aproxima un conjunto de
etiquetas de ruta como una firma de mapa de bits. Su parámetro entero opcional
siglen determina la longitud de la firma en bytes. La longitud
de firma por defecto es 8 bytes. La longitud debe ser un múltiplo positivo de la
alineación de int (4 bytes en la mayoría de las máquinas) hasta 2024.
Las firmas más largas conducen a una búsqueda más precisa (escaneando una fracción
más pequeña del índice y menos páginas de almacenamiento), a costa de un índice
más grande.
Ejemplo de creación de dicho índice con la longitud de firma predeterminada de 8 bytes:
CREATE INDEX path_gist_idx ON test USING GIST (path);
Ejemplo de creación de dicho índice con una longitud de firma de 100 bytes:
CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
Índice GiST sobre ltree[] (clase de operador gist__ltree_ops):
ltree[] <@ ltree, ltree @> ltree[],
@, ~, ?
La clase de operador GiST gist__ltree_ops funciona de manera
similar a gist_ltree_ops y también toma la longitud de la firma
como parámetro. El valor por defecto de siglen en
gist__ltree_ops es 28 bytes.
Ejemplo de creación de dicho índice con la longitud de firma predeterminada de 28 bytes:
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
Ejemplo de creación de dicho índice con una longitud de firma de 100 bytes:
CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));
Nota: Este tipo de índice es con pérdida (lossy).
Este ejemplo utiliza los siguientes datos (también disponibles en el archivo
contrib/ltree/ltreetest.sql en la distribución de fuentes):
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);
CREATE INDEX path_hash_idx ON test USING HASH (path);
Ahora, tenemos una tabla test poblada con datos que describen
la jerarquía mostrada a continuación:
Top
/ | \
Science Hobbies Collections
/ | \
Astronomy Amateurs_Astronomy Pictures
/ \ |
Astrophysics Cosmology Astronomy
/ | \
Galaxies Stars Astronauts
Podemos realizar herencias:
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)
Aquí tienes algunos ejemplos de coincidencia de rutas:
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 ~ '*[email protected].*';
path
------------------------------------
Top.Science.Astronomy
Top.Science.Astronomy.Astrophysics
Top.Science.Astronomy.Cosmology
(3 rows)
Aquí tienes algunos ejemplos de búsqueda de texto completo:
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)
Construcción de rutas usando funciones:
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)
Podríamos simplificar esto creando una función SQL que inserte una etiqueta en una posición específica de la ruta:
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)
La extensión ltree_plpython3u implementa transformaciones para
el tipo ltree en PL/Python. Si está instalada y se especifica al
crear una función, los valores de tipo ltree se asignan a listas de
Python. (Sin embargo, el proceso inverso no está soportado actualmente).
Todo el trabajo fue realizado por Teodor Sigaev (<[email protected]>) y
Oleg Bartunov (<[email protected]>). Consulta
http://www.sai.msu.su/~megera/postgres/gist/ para
obtener información adicional. Los autores desean agradecer a Eugeny Rodichev por
sus útiles discusiones. Los comentarios y reportes de errores son bienvenidos.