F.22. ltree — tipo de datos jerárquico similar a un árbol #

F.22.1. Definiciones
F.22.2. Operadores y funciones
F.22.3. Índices
F.22.4. Ejemplo
F.22.5. Transformaciones (Transforms)
F.22.6. Autores

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.

F.22.1. Definiciones #

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 etiquetas foo
    *.foo.*     Coincidir con cualquier ruta de etiquetas que contenga la etiqueta foo
    *.foo       Coincidir con cualquier ruta de etiquetas cuya última etiqueta sea foo
    

    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 ejemplo a@ coincide con A
    *           Coincidir con cualquier etiqueta que tenga este prefijo, por ejemplo foo* coincide con foobar
    %           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:

    1. comience con la etiqueta Top

    2. y luego tenga de cero a dos etiquetas antes de

    3. una etiqueta que comience con el prefijo sport (sin distinguir mayúsculas de minúsculas)

    4. luego tenga una o más etiquetas, ninguna de las cuales coincida con football ni con tennis

    5. 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.

F.22.2. Operadores y funciones #

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

ltree @> ltreeboolean

¿El argumento izquierdo es ancestro del derecho (o igual)?

ltree <@ ltreeboolean

¿El argumento izquierdo es descendiente del derecho (o igual)?

ltree ~ lqueryboolean

lquery ~ ltreeboolean

¿El ltree coincide con el lquery?

ltree ? lquery[]boolean

lquery[] ? ltreeboolean

¿El ltree coincide con algún lquery en el array?

ltree @ ltxtqueryboolean

ltxtquery @ ltreeboolean

¿El ltree coincide con el ltxtquery?

ltree || ltreeltree

Concatena rutas de ltree.

ltree || textltree

text || ltreeltree

Convierte texto a ltree y los concatena.

ltree[] @> ltreeboolean

ltree <@ ltree[]boolean

¿El array contiene un ancestro de ltree?

ltree[] <@ ltreeboolean

ltree @> ltree[]boolean

¿El array contiene un descendiente de ltree?

ltree[] ~ lqueryboolean

lquery ~ ltree[]boolean

¿El array contiene alguna ruta que coincida con el lquery?

ltree[] ? lquery[]boolean

lquery[] ? ltree[]boolean

¿El array de ltree contiene alguna ruta que coincida con algún lquery?

ltree[] @ ltxtqueryboolean

ltxtquery @ ltree[]boolean

¿El array contiene alguna ruta que coincida con el ltxtquery?

ltree[] ?@> ltreeltree

Devuelve la primera entrada del array que sea ancestro de ltree, o NULL si no hay ninguna.

ltree[] ?<@ ltreeltree

Devuelve la primera entrada del array que sea descendiente de ltree, o NULL si no hay ninguna.

ltree[] ?~ lqueryltree

Devuelve la primera entrada del array que coincida con el lquery, o NULL si no hay ninguna.

ltree[] ?@ ltxtqueryltree

Devuelve la primera entrada del array que coincida con el ltxtquery, o NULL si no hay ninguna.


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

Función

Descripción

Ejemplo(s)

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

Devuelve una subruta del ltree desde la posición start hasta la posición end-1 (contando desde 0).

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

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

Devuelve una subruta del ltree que comienza en la posición offset, con una longitud len. Si offset es negativo, la subruta comienza a esa distancia desde el final de la ruta. Si len es negativo, deja esa cantidad de etiquetas fuera del final de la ruta.

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

subpath ( ltree, offset integer ) → ltree

Devuelve una subruta del ltree que comienza en la posición offset y se extiende hasta el final de la ruta. Si offset es negativo, la subruta comienza a esa distancia desde el final de la ruta.

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

nlevel ( ltree ) → integer

Devuelve el número de etiquetas en la ruta.

nlevel('Top.Child1.Child2')3

index ( a ltree, b ltree ) → integer

Devuelve la posición de la primera ocurrencia de b en a, o -1 si no se encuentra.

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')6

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

Devuelve la posición de la primera ocurrencia de b en a, o -1 si no se encuentra. La búsqueda comienza en la posición offset; un offset negativo significa comenzar a -offset etiquetas del final de la ruta.

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

text2ltree ( text ) → ltree

Convierte text a ltree.

ltree2text ( ltree ) → text

Convierte ltree a text.

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

Calcula el ancestro común más largo de las rutas (se admiten hasta 8 argumentos).

lca('1.2.3', '1.2.3.4.5.6')1.2

lca ( ltree[] ) → ltree

Calcula el ancestro común más largo de las rutas del array.

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


F.22.3. Índices #

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

F.22.4. Ejemplo #

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)

F.22.5. Transformaciones (Transforms) #

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

F.22.6. Autores #

Todo el trabajo fue realizado por Teodor Sigaev () y Oleg Bartunov (). 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.