begriffs open source - ai-pg/blob - full-docs/txt/ltree.txt

   1
   2 F.22. ltree — hierarchical tree-like data type #
   3
   4    F.22.1. Definitions
   5    F.22.2. Operators and Functions
   6    F.22.3. Indexes
   7    F.22.4. Example
   8    F.22.5. Transforms
   9    F.22.6. Authors
  10
  11    This module implements a data type ltree for representing labels of
  12    data stored in a hierarchical tree-like structure. Extensive facilities
  13    for searching through label trees are provided.
  14
  15    This module is considered “trusted”, that is, it can be installed by
  16    non-superusers who have CREATE privilege on the current database.
  17
  18 F.22.1. Definitions #
  19
  20    A label is a sequence of alphanumeric characters, underscores, and
  21    hyphens. Valid alphanumeric character ranges are dependent on the
  22    database locale. For example, in C locale, the characters A-Za-z0-9_-
  23    are allowed. Labels must be no more than 1000 characters long.
  24
  25    Examples: 42, Personal_Services
  26
  27    A label path is a sequence of zero or more labels separated by dots,
  28    for example L1.L2.L3, representing a path from the root of a
  29    hierarchical tree to a particular node. The length of a label path
  30    cannot exceed 65535 labels.
  31
  32    Example: Top.Countries.Europe.Russia
  33
  34    The ltree module provides several data types:
  35      * ltree stores a label path.
  36      * lquery represents a regular-expression-like pattern for matching
  37        ltree values. A simple word matches that label within a path. A
  38        star symbol (*) matches zero or more labels. These can be joined
  39        with dots to form a pattern that must match the whole label path.
  40        For example:
  41 foo         Match the exact label path foo
  42 *.foo.*     Match any label path containing the label foo
  43 *.foo       Match any label path whose last label is foo
  44
  45        Both star symbols and simple words can be quantified to restrict
  46        how many labels they can match:
  47 *{n}        Match exactly n labels
  48 *{n,}       Match at least n labels
  49 *{n,m}      Match at least n but not more than m labels
  50 *{,m}       Match at most m labels — same as *{0,m}
  51 foo{n,m}    Match at least n but not more than m occurrences of foo
  52 foo{,}      Match any number of occurrences of foo, including zero
  53
  54        In the absence of any explicit quantifier, the default for a star
  55        symbol is to match any number of labels (that is, {,}) while the
  56        default for a non-star item is to match exactly once (that is,
  57        {1}).
  58        There are several modifiers that can be put at the end of a
  59        non-star lquery item to make it match more than just the exact
  60        match:
  61 @           Match case-insensitively, for example a@ matches A
  62 *           Match any label with this prefix, for example foo* matches foobar
  63 %           Match initial underscore-separated words
  64
  65        The behavior of % is a bit complicated. It tries to match words
  66        rather than the entire label. For example foo_bar% matches
  67        foo_bar_baz but not foo_barbaz. If combined with *, prefix matching
  68        applies to each word separately, for example foo_bar%* matches
  69        foo1_bar2_baz but not foo1_br2_baz.
  70        Also, you can write several possibly-modified non-star items
  71        separated with | (OR) to match any of those items, and you can put
  72        ! (NOT) at the start of a non-star group to match any label that
  73        doesn't match any of the alternatives. A quantifier, if any, goes
  74        at the end of the group; it means some number of matches for the
  75        group as a whole (that is, some number of labels matching or not
  76        matching any of the alternatives).
  77        Here's an annotated example of lquery:
  78 Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain
  79 a.  b.     c.      d.                   e.
  80
  81        This query will match any label path that:
  82          a. begins with the label Top
  83          b. and next has zero to two labels before
  84          c. a label beginning with the case-insensitive prefix sport
  85          d. then has one or more labels, none of which match football nor
  86             tennis
  87          e. and then ends with a label beginning with Russ or exactly
  88             matching Spain.
  89      * ltxtquery represents a full-text-search-like pattern for matching
  90        ltree values. An ltxtquery value contains words, possibly with the
  91        modifiers @, *, % at the end; the modifiers have the same meanings
  92        as in lquery. Words can be combined with & (AND), | (OR), ! (NOT),
  93        and parentheses. The key difference from lquery is that ltxtquery
  94        matches words without regard to their position in the label path.
  95        Here's an example ltxtquery:
  96 Europe & Russia*@ & !Transportation
  97
  98        This will match paths that contain the label Europe and any label
  99        beginning with Russia (case-insensitive), but not paths containing
 100        the label Transportation. The location of these words within the
 101        path is not important. Also, when % is used, the word can be
 102        matched to any underscore-separated word within a label, regardless
 103        of position.
 104
 105    Note: ltxtquery allows whitespace between symbols, but ltree and lquery
 106    do not.
 107
 108 F.22.2. Operators and Functions #
 109
 110    Type ltree has the usual comparison operators =, <>, <, >, <=, >=.
 111    Comparison sorts in the order of a tree traversal, with the children of
 112    a node sorted by label text. In addition, the specialized operators
 113    shown in Table F.12 are available.
 114
 115    Table F.12. ltree Operators
 116
 117    Operator
 118
 119    Description
 120
 121    ltree @> ltree → boolean
 122
 123    Is left argument an ancestor of right (or equal)?
 124
 125    ltree <@ ltree → boolean
 126
 127    Is left argument a descendant of right (or equal)?
 128
 129    ltree ~ lquery → boolean
 130
 131    lquery ~ ltree → boolean
 132
 133    Does ltree match lquery?
 134
 135    ltree ? lquery[] → boolean
 136
 137    lquery[] ? ltree → boolean
 138
 139    Does ltree match any lquery in array?
 140
 141    ltree @ ltxtquery → boolean
 142
 143    ltxtquery @ ltree → boolean
 144
 145    Does ltree match ltxtquery?
 146
 147    ltree || ltree → ltree
 148
 149    Concatenates ltree paths.
 150
 151    ltree || text → ltree
 152
 153    text || ltree → ltree
 154
 155    Converts text to ltree and concatenates.
 156
 157    ltree[] @> ltree → boolean
 158
 159    ltree <@ ltree[] → boolean
 160
 161    Does array contain an ancestor of ltree?
 162
 163    ltree[] <@ ltree → boolean
 164
 165    ltree @> ltree[] → boolean
 166
 167    Does array contain a descendant of ltree?
 168
 169    ltree[] ~ lquery → boolean
 170
 171    lquery ~ ltree[] → boolean
 172
 173    Does array contain any path matching lquery?
 174
 175    ltree[] ? lquery[] → boolean
 176
 177    lquery[] ? ltree[] → boolean
 178
 179    Does ltree array contain any path matching any lquery?
 180
 181    ltree[] @ ltxtquery → boolean
 182
 183    ltxtquery @ ltree[] → boolean
 184
 185    Does array contain any path matching ltxtquery?
 186
 187    ltree[] ?@> ltree → ltree
 188
 189    Returns first array entry that is an ancestor of ltree, or NULL if
 190    none.
 191
 192    ltree[] ?<@ ltree → ltree
 193
 194    Returns first array entry that is a descendant of ltree, or NULL if
 195    none.
 196
 197    ltree[] ?~ lquery → ltree
 198
 199    Returns first array entry that matches lquery, or NULL if none.
 200
 201    ltree[] ?@ ltxtquery → ltree
 202
 203    Returns first array entry that matches ltxtquery, or NULL if none.
 204
 205    The operators <@, @>, @ and ~ have analogues ^<@, ^@>, ^@, ^~, which
 206    are the same except they do not use indexes. These are useful only for
 207    testing purposes.
 208
 209    The available functions are shown in Table F.13.
 210
 211    Table F.13. ltree Functions
 212
 213    Function
 214
 215    Description
 216
 217    Example(s)
 218
 219    subltree ( ltree, start integer, end integer ) → ltree
 220
 221    Returns subpath of ltree from position start to position end-1
 222    (counting from 0).
 223
 224    subltree('Top.Child1.Child2', 1, 2) → Child1
 225
 226    subpath ( ltree, offset integer, len integer ) → ltree
 227
 228    Returns subpath of ltree starting at position offset, with length len.
 229    If offset is negative, subpath starts that far from the end of the
 230    path. If len is negative, leaves that many labels off the end of the
 231    path.
 232
 233    subpath('Top.Child1.Child2', 0, 2) → Top.Child1
 234
 235    subpath ( ltree, offset integer ) → ltree
 236
 237    Returns subpath of ltree starting at position offset, extending to end
 238    of path. If offset is negative, subpath starts that far from the end of
 239    the path.
 240
 241    subpath('Top.Child1.Child2', 1) → Child1.Child2
 242
 243    nlevel ( ltree ) → integer
 244
 245    Returns number of labels in path.
 246
 247    nlevel('Top.Child1.Child2') → 3
 248
 249    index ( a ltree, b ltree ) → integer
 250
 251    Returns position of first occurrence of b in a, or -1 if not found.
 252
 253    index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6') → 6
 254
 255    index ( a ltree, b ltree, offset integer ) → integer
 256
 257    Returns position of first occurrence of b in a, or -1 if not found. The
 258    search starts at position offset; negative offset means start -offset
 259    labels from the end of the path.
 260
 261    index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6', -4) → 9
 262
 263    text2ltree ( text ) → ltree
 264
 265    Casts text to ltree.
 266
 267    ltree2text ( ltree ) → text
 268
 269    Casts ltree to text.
 270
 271    lca ( ltree [, ltree [, ... ]] ) → ltree
 272
 273    Computes longest common ancestor of paths (up to 8 arguments are
 274    supported).
 275
 276    lca('1.2.3', '1.2.3.4.5.6') → 1.2
 277
 278    lca ( ltree[] ) → ltree
 279
 280    Computes longest common ancestor of paths in array.
 281
 282    lca(array['1.2.3'::ltree,'1.2.3.4']) → 1.2
 283
 284 F.22.3. Indexes #
 285
 286    ltree supports several types of indexes that can speed up the indicated
 287    operators:
 288      * B-tree index over ltree: <, <=, =, >=, >
 289      * Hash index over ltree: =
 290      * GiST index over ltree (gist_ltree_ops opclass): <, <=, =, >=, >,
 291        @>, <@, @, ~, ?
 292        gist_ltree_ops GiST opclass approximates a set of path labels as a
 293        bitmap signature. Its optional integer parameter siglen determines
 294        the signature length in bytes. The default signature length is 8
 295        bytes. The length must be a positive multiple of int alignment (4
 296        bytes on most machines)) up to 2024. Longer signatures lead to a
 297        more precise search (scanning a smaller fraction of the index and
 298        fewer heap pages), at the cost of a larger index.
 299        Example of creating such an index with the default signature length
 300        of 8 bytes:
 301 CREATE INDEX path_gist_idx ON test USING GIST (path);
 302
 303        Example of creating such an index with a signature length of 100
 304        bytes:
 305 CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
 306
 307      * GiST index over ltree[] (gist__ltree_ops opclass): ltree[] <@
 308        ltree, ltree @> ltree[], @, ~, ?
 309        gist__ltree_ops GiST opclass works similarly to gist_ltree_ops and
 310        also takes signature length as a parameter. The default value of
 311        siglen in gist__ltree_ops is 28 bytes.
 312        Example of creating such an index with the default signature length
 313        of 28 bytes:
 314 CREATE INDEX path_gist_idx ON test USING GIST (array_path);
 315
 316        Example of creating such an index with a signature length of 100
 317        bytes:
 318 CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen
 319 =100));
 320
 321        Note: This index type is lossy.
 322
 323 F.22.4. Example #
 324
 325    This example uses the following data (also available in file
 326    contrib/ltree/ltreetest.sql in the source distribution):
 327 CREATE TABLE test (path ltree);
 328 INSERT INTO test VALUES ('Top');
 329 INSERT INTO test VALUES ('Top.Science');
 330 INSERT INTO test VALUES ('Top.Science.Astronomy');
 331 INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
 332 INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
 333 INSERT INTO test VALUES ('Top.Hobbies');
 334 INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
 335 INSERT INTO test VALUES ('Top.Collections');
 336 INSERT INTO test VALUES ('Top.Collections.Pictures');
 337 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
 338 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
 339 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
 340 INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
 341 CREATE INDEX path_gist_idx ON test USING GIST (path);
 342 CREATE INDEX path_idx ON test USING BTREE (path);
 343 CREATE INDEX path_hash_idx ON test USING HASH (path);
 344
 345    Now, we have a table test populated with data describing the hierarchy
 346    shown below:
 347                         Top
 348                      /   |  \
 349              Science Hobbies Collections
 350                  /       |              \
 351         Astronomy   Amateurs_Astronomy Pictures
 352            /  \                            |
 353 Astrophysics  Cosmology                Astronomy
 354                                         /  |    \
 355                                  Galaxies Stars Astronauts
 356
 357    We can do inheritance:
 358 ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
 359                 path
 360 ------------------------------------
 361  Top.Science
 362  Top.Science.Astronomy
 363  Top.Science.Astronomy.Astrophysics
 364  Top.Science.Astronomy.Cosmology
 365 (4 rows)
 366
 367    Here are some examples of path matching:
 368 ltreetest=> SELECT path FROM test WHERE path ~ '*.Astronomy.*';
 369                      path
 370 -----------------------------------------------
 371  Top.Science.Astronomy
 372  Top.Science.Astronomy.Astrophysics
 373  Top.Science.Astronomy.Cosmology
 374  Top.Collections.Pictures.Astronomy
 375  Top.Collections.Pictures.Astronomy.Stars
 376  Top.Collections.Pictures.Astronomy.Galaxies
 377  Top.Collections.Pictures.Astronomy.Astronauts
 378 (7 rows)
 379
 380 ltreetest=> SELECT path FROM test WHERE path ~ '*.!pictures@.Astronomy.*';
 381                 path
 382 ------------------------------------
 383  Top.Science.Astronomy
 384  Top.Science.Astronomy.Astrophysics
 385  Top.Science.Astronomy.Cosmology
 386 (3 rows)
 387
 388    Here are some examples of full text search:
 389 ltreetest=> SELECT path FROM test WHERE path @ 'Astro*% & !pictures@';
 390                 path
 391 ------------------------------------
 392  Top.Science.Astronomy
 393  Top.Science.Astronomy.Astrophysics
 394  Top.Science.Astronomy.Cosmology
 395  Top.Hobbies.Amateurs_Astronomy
 396 (4 rows)
 397
 398 ltreetest=> SELECT path FROM test WHERE path @ 'Astro* & !pictures@';
 399                 path
 400 ------------------------------------
 401  Top.Science.Astronomy
 402  Top.Science.Astronomy.Astrophysics
 403  Top.Science.Astronomy.Cosmology
 404 (3 rows)
 405
 406    Path construction using functions:
 407 ltreetest=> SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE p
 408 ath <@ 'Top.Science.Astronomy';
 409                  ?column?
 410 ------------------------------------------
 411  Top.Science.Space.Astronomy
 412  Top.Science.Space.Astronomy.Astrophysics
 413  Top.Science.Space.Astronomy.Cosmology
 414 (3 rows)
 415
 416    We could simplify this by creating an SQL function that inserts a label
 417    at a specified position in a path:
 418 CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree
 419     AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);'
 420     LANGUAGE SQL IMMUTABLE;
 421
 422 ltreetest=> SELECT ins_label(path,2,'Space') FROM test WHERE path <@ 'Top.Scienc
 423 e.Astronomy';
 424                 ins_label
 425 ------------------------------------------
 426  Top.Science.Space.Astronomy
 427  Top.Science.Space.Astronomy.Astrophysics
 428  Top.Science.Space.Astronomy.Cosmology
 429 (3 rows)
 430
 431 F.22.5. Transforms #
 432
 433    The ltree_plpython3u extension implements transforms for the ltree type
 434    for PL/Python. If installed and specified when creating a function,
 435    ltree values are mapped to Python lists. (The reverse is currently not
 436    supported, however.)
 437
 438 F.22.6. Authors #
 439
 440    All work was done by Teodor Sigaev (<teodor@stack.net>) and Oleg
 441    Bartunov (<oleg@sai.msu.su>). See
 442    http://www.sai.msu.su/~megera/postgres/gist/ for additional
 443    information. Authors would like to thank Eugeny Rodichev for helpful
 444    discussions. Comments and bug reports are welcome.