| 1 |
<!-- doc/src/sgml/ltree.sgml --> |
| 2 |
|
| 3 |
<sect1 id="ltree" xreflabel="ltree"> |
| 4 |
<title>ltree — hierarchical tree-like data type</title> |
| 5 |
|
| 6 |
<indexterm zone="ltree"> |
| 7 |
<primary>ltree</primary> |
| 8 |
</indexterm> |
| 9 |
|
| 10 |
<para> |
| 11 |
This module implements a data type <type>ltree</type> for representing |
| 12 |
labels of data stored in a hierarchical tree-like structure. |
| 13 |
Extensive facilities for searching through label trees are provided. |
| 14 |
</para> |
| 15 |
|
| 16 |
<para> |
| 17 |
This module is considered <quote>trusted</quote>, that is, it can be |
| 18 |
installed by non-superusers who have <literal>CREATE</literal> privilege |
| 19 |
on the current database. |
| 20 |
</para> |
| 21 |
|
| 22 |
<sect2 id="ltree-definitions"> |
| 23 |
<title>Definitions</title> |
| 24 |
|
| 25 |
<para> |
| 26 |
A <firstterm>label</firstterm> is a sequence of alphanumeric characters, |
| 27 |
underscores, and hyphens. Valid alphanumeric character ranges are |
| 28 |
dependent on the database locale. For example, in C locale, the characters |
| 29 |
<literal>A-Za-z0-9_-</literal> are allowed. |
| 30 |
Labels must be no more than 1000 characters long. |
| 31 |
</para> |
| 32 |
|
| 33 |
<para> |
| 34 |
Examples: <literal>42</literal>, <literal>Personal_Services</literal> |
| 35 |
</para> |
| 36 |
|
| 37 |
<para> |
| 38 |
A <firstterm>label path</firstterm> is a sequence of zero or more |
| 39 |
labels separated by dots, for example <literal>L1.L2.L3</literal>, representing |
| 40 |
a path from the root of a hierarchical tree to a particular node. The |
| 41 |
length of a label path cannot exceed 65535 labels. |
| 42 |
</para> |
| 43 |
|
| 44 |
<para> |
| 45 |
Example: <literal>Top.Countries.Europe.Russia</literal> |
| 46 |
</para> |
| 47 |
|
| 48 |
<para> |
| 49 |
The <filename>ltree</filename> module provides several data types: |
| 50 |
</para> |
| 51 |
|
| 52 |
<itemizedlist> |
| 53 |
<listitem> |
| 54 |
<para> |
| 55 |
<type>ltree</type> stores a label path. |
| 56 |
</para> |
| 57 |
</listitem> |
| 58 |
|
| 59 |
<listitem> |
| 60 |
<para> |
| 61 |
<type>lquery</type> represents a regular-expression-like pattern |
| 62 |
for matching <type>ltree</type> values. A simple word matches that |
| 63 |
label within a path. A star symbol (<literal>*</literal>) matches zero |
| 64 |
or more labels. These can be joined with dots to form a pattern that |
| 65 |
must match the whole label path. For example: |
| 66 |
<synopsis> |
| 67 |
foo <lineannotation>Match the exact label path <literal>foo</literal></lineannotation> |
| 68 |
*.foo.* <lineannotation>Match any label path containing the label <literal>foo</literal></lineannotation> |
| 69 |
*.foo <lineannotation>Match any label path whose last label is <literal>foo</literal></lineannotation> |
| 70 |
</synopsis> |
| 71 |
</para> |
| 72 |
|
| 73 |
<para> |
| 74 |
Both star symbols and simple words can be quantified to restrict how many |
| 75 |
labels they can match: |
| 76 |
<synopsis> |
| 77 |
*{<replaceable>n</replaceable>} <lineannotation>Match exactly <replaceable>n</replaceable> labels</lineannotation> |
| 78 |
*{<replaceable>n</replaceable>,} <lineannotation>Match at least <replaceable>n</replaceable> labels</lineannotation> |
| 79 |
*{<replaceable>n</replaceable>,<replaceable>m</replaceable>} <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> labels</lineannotation> |
| 80 |
*{,<replaceable>m</replaceable>} <lineannotation>Match at most <replaceable>m</replaceable> labels — same as </lineannotation>*{0,<replaceable>m</replaceable>} |
| 81 |
foo{<replaceable>n</replaceable>,<replaceable>m</replaceable>} <lineannotation>Match at least <replaceable>n</replaceable> but not more than <replaceable>m</replaceable> occurrences of <literal>foo</literal></lineannotation> |
| 82 |
foo{,} <lineannotation>Match any number of occurrences of <literal>foo</literal>, including zero</lineannotation> |
| 83 |
</synopsis> |
| 84 |
In the absence of any explicit quantifier, the default for a star symbol |
| 85 |
is to match any number of labels (that is, <literal>{,}</literal>) while |
| 86 |
the default for a non-star item is to match exactly once (that |
| 87 |
is, <literal>{1}</literal>). |
| 88 |
</para> |
| 89 |
|
| 90 |
<para> |
| 91 |
There are several modifiers that can be put at the end of a non-star |
| 92 |
<type>lquery</type> item to make it match more than just the exact match: |
| 93 |
<synopsis> |
| 94 |
@ <lineannotation>Match case-insensitively, for example <literal>a@</literal> matches <literal>A</literal></lineannotation> |
| 95 |
* <lineannotation>Match any label with this prefix, for example <literal>foo*</literal> matches <literal>foobar</literal></lineannotation> |
| 96 |
% <lineannotation>Match initial underscore-separated words</lineannotation> |
| 97 |
</synopsis> |
| 98 |
The behavior of <literal>%</literal> is a bit complicated. It tries to match |
| 99 |
words rather than the entire label. For example |
| 100 |
<literal>foo_bar%</literal> matches <literal>foo_bar_baz</literal> but not |
| 101 |
<literal>foo_barbaz</literal>. If combined with <literal>*</literal>, prefix |
| 102 |
matching applies to each word separately, for example |
| 103 |
<literal>foo_bar%*</literal> matches <literal>foo1_bar2_baz</literal> but |
| 104 |
not <literal>foo1_br2_baz</literal>. |
| 105 |
</para> |
| 106 |
|
| 107 |
<para> |
| 108 |
Also, you can write several possibly-modified non-star items separated with |
| 109 |
<literal>|</literal> (OR) to match any of those items, and you can put |
| 110 |
<literal>!</literal> (NOT) at the start of a non-star group to match any |
| 111 |
label that doesn't match any of the alternatives. A quantifier, if any, |
| 112 |
goes at the end of the group; it means some number of matches for the |
| 113 |
group as a whole (that is, some number of labels matching or not matching |
| 114 |
any of the alternatives). |
| 115 |
</para> |
| 116 |
|
| 117 |
<para> |
| 118 |
Here's an annotated example of <type>lquery</type>: |
| 119 |
<programlisting> |
| 120 |
Top.*{0,2}.sport*@.!football|tennis{1,}.Russ*|Spain |
| 121 |
a. b. c. d. e. |
| 122 |
</programlisting> |
| 123 |
This query will match any label path that: |
| 124 |
</para> |
| 125 |
<orderedlist numeration="loweralpha"> |
| 126 |
<listitem> |
| 127 |
<para> |
| 128 |
begins with the label <literal>Top</literal> |
| 129 |
</para> |
| 130 |
</listitem> |
| 131 |
<listitem> |
| 132 |
<para> |
| 133 |
and next has zero to two labels before |
| 134 |
</para> |
| 135 |
</listitem> |
| 136 |
<listitem> |
| 137 |
<para> |
| 138 |
a label beginning with the case-insensitive prefix <literal>sport</literal> |
| 139 |
</para> |
| 140 |
</listitem> |
| 141 |
<listitem> |
| 142 |
<para> |
| 143 |
then has one or more labels, none of which |
| 144 |
match <literal>football</literal> nor <literal>tennis</literal> |
| 145 |
</para> |
| 146 |
</listitem> |
| 147 |
<listitem> |
| 148 |
<para> |
| 149 |
and then ends with a label beginning with <literal>Russ</literal> or |
| 150 |
exactly matching <literal>Spain</literal>. |
| 151 |
</para> |
| 152 |
</listitem> |
| 153 |
</orderedlist> |
| 154 |
</listitem> |
| 155 |
|
| 156 |
<listitem> |
| 157 |
<para><type>ltxtquery</type> represents a full-text-search-like |
| 158 |
pattern for matching <type>ltree</type> values. An |
| 159 |
<type>ltxtquery</type> value contains words, possibly with the |
| 160 |
modifiers <literal>@</literal>, <literal>*</literal>, <literal>%</literal> at the end; |
| 161 |
the modifiers have the same meanings as in <type>lquery</type>. |
| 162 |
Words can be combined with <literal>&</literal> (AND), |
| 163 |
<literal>|</literal> (OR), <literal>!</literal> (NOT), and parentheses. |
| 164 |
The key difference from |
| 165 |
<type>lquery</type> is that <type>ltxtquery</type> matches words without |
| 166 |
regard to their position in the label path. |
| 167 |
</para> |
| 168 |
|
| 169 |
<para> |
| 170 |
Here's an example <type>ltxtquery</type>: |
| 171 |
<programlisting> |
| 172 |
Europe & Russia*@ & !Transportation |
| 173 |
</programlisting> |
| 174 |
This will match paths that contain the label <literal>Europe</literal> and |
| 175 |
any label beginning with <literal>Russia</literal> (case-insensitive), |
| 176 |
but not paths containing the label <literal>Transportation</literal>. |
| 177 |
The location of these words within the path is not important. |
| 178 |
Also, when <literal>%</literal> is used, the word can be matched to any |
| 179 |
underscore-separated word within a label, regardless of position. |
| 180 |
</para> |
| 181 |
</listitem> |
| 182 |
|
| 183 |
</itemizedlist> |
| 184 |
|
| 185 |
<para> |
| 186 |
Note: <type>ltxtquery</type> allows whitespace between symbols, but |
| 187 |
<type>ltree</type> and <type>lquery</type> do not. |
| 188 |
</para> |
| 189 |
</sect2> |
| 190 |
|
| 191 |
<sect2 id="ltree-ops-funcs"> |
| 192 |
<title>Operators and Functions</title> |
| 193 |
|
| 194 |
<para> |
| 195 |
Type <type>ltree</type> has the usual comparison operators |
| 196 |
<literal>=</literal>, <literal><></literal>, |
| 197 |
<literal><</literal>, <literal>></literal>, <literal><=</literal>, <literal>>=</literal>. |
| 198 |
Comparison sorts in the order of a tree traversal, with the children |
| 199 |
of a node sorted by label text. In addition, the specialized |
| 200 |
operators shown in <xref linkend="ltree-op-table"/> are available. |
| 201 |
</para> |
| 202 |
|
| 203 |
<table id="ltree-op-table"> |
| 204 |
<title><type>ltree</type> Operators</title> |
| 205 |
<tgroup cols="1"> |
| 206 |
<thead> |
| 207 |
<row> |
| 208 |
<entry role="func_table_entry"><para role="func_signature"> |
| 209 |
Operator |
| 210 |
</para> |
| 211 |
<para> |
| 212 |
Description |
| 213 |
</para></entry> |
| 214 |
</row> |
| 215 |
</thead> |
| 216 |
|
| 217 |
<tbody> |
| 218 |
<row> |
| 219 |
<entry role="func_table_entry"><para role="func_signature"> |
| 220 |
<type>ltree</type> <literal>@></literal> <type>ltree</type> |
| 221 |
<returnvalue>boolean</returnvalue> |
| 222 |
</para> |
| 223 |
<para> |
| 224 |
Is left argument an ancestor of right (or equal)? |
| 225 |
</para></entry> |
| 226 |
</row> |
| 227 |
|
| 228 |
<row> |
| 229 |
<entry role="func_table_entry"><para role="func_signature"> |
| 230 |
<type>ltree</type> <literal><@</literal> <type>ltree</type> |
| 231 |
<returnvalue>boolean</returnvalue> |
| 232 |
</para> |
| 233 |
<para> |
| 234 |
Is left argument a descendant of right (or equal)? |
| 235 |
</para></entry> |
| 236 |
</row> |
| 237 |
|
| 238 |
<row> |
| 239 |
<entry role="func_table_entry"><para role="func_signature"> |
| 240 |
<type>ltree</type> <literal>~</literal> <type>lquery</type> |
| 241 |
<returnvalue>boolean</returnvalue> |
| 242 |
</para> |
| 243 |
<para role="func_signature"> |
| 244 |
<type>lquery</type> <literal>~</literal> <type>ltree</type> |
| 245 |
<returnvalue>boolean</returnvalue> |
| 246 |
</para> |
| 247 |
<para> |
| 248 |
Does <type>ltree</type> match <type>lquery</type>? |
| 249 |
</para></entry> |
| 250 |
</row> |
| 251 |
|
| 252 |
<row> |
| 253 |
<entry role="func_table_entry"><para role="func_signature"> |
| 254 |
<type>ltree</type> <literal>?</literal> <type>lquery[]</type> |
| 255 |
<returnvalue>boolean</returnvalue> |
| 256 |
</para> |
| 257 |
<para role="func_signature"> |
| 258 |
<type>lquery[]</type> <literal>?</literal> <type>ltree</type> |
| 259 |
<returnvalue>boolean</returnvalue> |
| 260 |
</para> |
| 261 |
<para> |
| 262 |
Does <type>ltree</type> match any <type>lquery</type> in array? |
| 263 |
</para></entry> |
| 264 |
</row> |
| 265 |
|
| 266 |
<row> |
| 267 |
<entry role="func_table_entry"><para role="func_signature"> |
| 268 |
<type>ltree</type> <literal>@</literal> <type>ltxtquery</type> |
| 269 |
<returnvalue>boolean</returnvalue> |
| 270 |
</para> |
| 271 |
<para role="func_signature"> |
| 272 |
<type>ltxtquery</type> <literal>@</literal> <type>ltree</type> |
| 273 |
<returnvalue>boolean</returnvalue> |
| 274 |
</para> |
| 275 |
<para> |
| 276 |
Does <type>ltree</type> match <type>ltxtquery</type>? |
| 277 |
</para></entry> |
| 278 |
</row> |
| 279 |
|
| 280 |
<row> |
| 281 |
<entry role="func_table_entry"><para role="func_signature"> |
| 282 |
<type>ltree</type> <literal>||</literal> <type>ltree</type> |
| 283 |
<returnvalue>ltree</returnvalue> |
| 284 |
</para> |
| 285 |
<para> |
| 286 |
Concatenates <type>ltree</type> paths. |
| 287 |
</para></entry> |
| 288 |
</row> |
| 289 |
|
| 290 |
<row> |
| 291 |
<entry role="func_table_entry"><para role="func_signature"> |
| 292 |
<type>ltree</type> <literal>||</literal> <type>text</type> |
| 293 |
<returnvalue>ltree</returnvalue> |
| 294 |
</para> |
| 295 |
<para role="func_signature"> |
| 296 |
<type>text</type> <literal>||</literal> <type>ltree</type> |
| 297 |
<returnvalue>ltree</returnvalue> |
| 298 |
</para> |
| 299 |
<para> |
| 300 |
Converts text to <type>ltree</type> and concatenates. |
| 301 |
</para></entry> |
| 302 |
</row> |
| 303 |
|
| 304 |
<row> |
| 305 |
<entry role="func_table_entry"><para role="func_signature"> |
| 306 |
<type>ltree[]</type> <literal>@></literal> <type>ltree</type> |
| 307 |
<returnvalue>boolean</returnvalue> |
| 308 |
</para> |
| 309 |
<para role="func_signature"> |
| 310 |
<type>ltree</type> <literal><@</literal> <type>ltree[]</type> |
| 311 |
<returnvalue>boolean</returnvalue> |
| 312 |
</para> |
| 313 |
<para> |
| 314 |
Does array contain an ancestor of <type>ltree</type>? |
| 315 |
</para></entry> |
| 316 |
</row> |
| 317 |
|
| 318 |
<row> |
| 319 |
<entry role="func_table_entry"><para role="func_signature"> |
| 320 |
<type>ltree[]</type> <literal><@</literal> <type>ltree</type> |
| 321 |
<returnvalue>boolean</returnvalue> |
| 322 |
</para> |
| 323 |
<para role="func_signature"> |
| 324 |
<type>ltree</type> <literal>@></literal> <type>ltree[]</type> |
| 325 |
<returnvalue>boolean</returnvalue> |
| 326 |
</para> |
| 327 |
<para> |
| 328 |
Does array contain a descendant of <type>ltree</type>? |
| 329 |
</para></entry> |
| 330 |
</row> |
| 331 |
|
| 332 |
<row> |
| 333 |
<entry role="func_table_entry"><para role="func_signature"> |
| 334 |
<type>ltree[]</type> <literal>~</literal> <type>lquery</type> |
| 335 |
<returnvalue>boolean</returnvalue> |
| 336 |
</para> |
| 337 |
<para role="func_signature"> |
| 338 |
<type>lquery</type> <literal>~</literal> <type>ltree[]</type> |
| 339 |
<returnvalue>boolean</returnvalue> |
| 340 |
</para> |
| 341 |
<para> |
| 342 |
Does array contain any path matching <type>lquery</type>? |
| 343 |
</para></entry> |
| 344 |
</row> |
| 345 |
|
| 346 |
<row> |
| 347 |
<entry role="func_table_entry"><para role="func_signature"> |
| 348 |
<type>ltree[]</type> <literal>?</literal> <type>lquery[]</type> |
| 349 |
<returnvalue>boolean</returnvalue> |
| 350 |
</para> |
| 351 |
<para role="func_signature"> |
| 352 |
<type>lquery[]</type> <literal>?</literal> <type>ltree[]</type> |
| 353 |
<returnvalue>boolean</returnvalue> |
| 354 |
</para> |
| 355 |
<para> |
| 356 |
Does <type>ltree</type> array contain any path matching |
| 357 |
any <type>lquery</type>? |
| 358 |
</para></entry> |
| 359 |
</row> |
| 360 |
|
| 361 |
<row> |
| 362 |
<entry role="func_table_entry"><para role="func_signature"> |
| 363 |
<type>ltree[]</type> <literal>@</literal> <type>ltxtquery</type> |
| 364 |
<returnvalue>boolean</returnvalue> |
| 365 |
</para> |
| 366 |
<para role="func_signature"> |
| 367 |
<type>ltxtquery</type> <literal>@</literal> <type>ltree[]</type> |
| 368 |
<returnvalue>boolean</returnvalue> |
| 369 |
</para> |
| 370 |
<para> |
| 371 |
Does array contain any path matching <type>ltxtquery</type>? |
| 372 |
</para></entry> |
| 373 |
</row> |
| 374 |
|
| 375 |
<row> |
| 376 |
<entry role="func_table_entry"><para role="func_signature"> |
| 377 |
<type>ltree[]</type> <literal>?@></literal> <type>ltree</type> |
| 378 |
<returnvalue>ltree</returnvalue> |
| 379 |
</para> |
| 380 |
<para> |
| 381 |
Returns first array entry that is an ancestor of <type>ltree</type>, |
| 382 |
or <literal>NULL</literal> if none. |
| 383 |
</para></entry> |
| 384 |
</row> |
| 385 |
|
| 386 |
<row> |
| 387 |
<entry role="func_table_entry"><para role="func_signature"> |
| 388 |
<type>ltree[]</type> <literal>?<@</literal> <type>ltree</type> |
| 389 |
<returnvalue>ltree</returnvalue> |
| 390 |
</para> |
| 391 |
<para> |
| 392 |
Returns first array entry that is a descendant of <type>ltree</type>, |
| 393 |
or <literal>NULL</literal> if none. |
| 394 |
</para></entry> |
| 395 |
</row> |
| 396 |
|
| 397 |
<row> |
| 398 |
<entry role="func_table_entry"><para role="func_signature"> |
| 399 |
<type>ltree[]</type> <literal>?~</literal> <type>lquery</type> |
| 400 |
<returnvalue>ltree</returnvalue> |
| 401 |
</para> |
| 402 |
<para> |
| 403 |
Returns first array entry that matches <type>lquery</type>, |
| 404 |
or <literal>NULL</literal> if none. |
| 405 |
</para></entry> |
| 406 |
</row> |
| 407 |
|
| 408 |
<row> |
| 409 |
<entry role="func_table_entry"><para role="func_signature"> |
| 410 |
<type>ltree[]</type> <literal>?@</literal> <type>ltxtquery</type> |
| 411 |
<returnvalue>ltree</returnvalue> |
| 412 |
</para> |
| 413 |
<para> |
| 414 |
Returns first array entry that matches <type>ltxtquery</type>, |
| 415 |
or <literal>NULL</literal> if none. |
| 416 |
</para></entry> |
| 417 |
</row> |
| 418 |
</tbody> |
| 419 |
</tgroup> |
| 420 |
</table> |
| 421 |
|
| 422 |
<para> |
| 423 |
The operators <literal><@</literal>, <literal>@></literal>, |
| 424 |
<literal>@</literal> and <literal>~</literal> have analogues |
| 425 |
<literal>^<@</literal>, <literal>^@></literal>, <literal>^@</literal>, |
| 426 |
<literal>^~</literal>, which are the same except they do not use |
| 427 |
indexes. These are useful only for testing purposes. |
| 428 |
</para> |
| 429 |
|
| 430 |
<para> |
| 431 |
The available functions are shown in <xref linkend="ltree-func-table"/>. |
| 432 |
</para> |
| 433 |
|
| 434 |
<table id="ltree-func-table"> |
| 435 |
<title><type>ltree</type> Functions</title> |
| 436 |
<tgroup cols="1"> |
| 437 |
<thead> |
| 438 |
<row> |
| 439 |
<entry role="func_table_entry"><para role="func_signature"> |
| 440 |
Function |
| 441 |
</para> |
| 442 |
<para> |
| 443 |
Description |
| 444 |
</para> |
| 445 |
<para> |
| 446 |
Example(s) |
| 447 |
</para></entry> |
| 448 |
</row> |
| 449 |
</thead> |
| 450 |
|
| 451 |
<tbody> |
| 452 |
<row> |
| 453 |
<entry role="func_table_entry"><para role="func_signature"> |
| 454 |
<indexterm><primary>subltree</primary></indexterm> |
| 455 |
<function>subltree</function> ( <type>ltree</type>, <parameter>start</parameter> <type>integer</type>, <parameter>end</parameter> <type>integer</type> ) |
| 456 |
<returnvalue>ltree</returnvalue> |
| 457 |
</para> |
| 458 |
<para> |
| 459 |
Returns subpath of <type>ltree</type> from |
| 460 |
position <parameter>start</parameter> to |
| 461 |
position <parameter>end</parameter>-1 (counting from 0). |
| 462 |
</para> |
| 463 |
<para> |
| 464 |
<literal>subltree('Top.Child1.Child2', 1, 2)</literal> |
| 465 |
<returnvalue>Child1</returnvalue> |
| 466 |
</para></entry> |
| 467 |
</row> |
| 468 |
|
| 469 |
<row> |
| 470 |
<entry role="func_table_entry"><para role="func_signature"> |
| 471 |
<indexterm><primary>subpath</primary></indexterm> |
| 472 |
<function>subpath</function> ( <type>ltree</type>, <parameter>offset</parameter> <type>integer</type>, <parameter>len</parameter> <type>integer</type> ) |
| 473 |
<returnvalue>ltree</returnvalue> |
| 474 |
</para> |
| 475 |
<para> |
| 476 |
Returns subpath of <type>ltree</type> starting at |
| 477 |
position <parameter>offset</parameter>, with |
| 478 |
length <parameter>len</parameter>. If <parameter>offset</parameter> |
| 479 |
is negative, subpath starts that far from the end of the path. |
| 480 |
If <parameter>len</parameter> is negative, leaves that many labels off |
| 481 |
the end of the path. |
| 482 |
</para> |
| 483 |
<para> |
| 484 |
<literal>subpath('Top.Child1.Child2', 0, 2)</literal> |
| 485 |
<returnvalue>Top.Child1</returnvalue> |
| 486 |
</para></entry> |
| 487 |
</row> |
| 488 |
|
| 489 |
<row> |
| 490 |
<entry role="func_table_entry"><para role="func_signature"> |
| 491 |
<function>subpath</function> ( <type>ltree</type>, <parameter>offset</parameter> <type>integer</type> ) |
| 492 |
<returnvalue>ltree</returnvalue> |
| 493 |
</para> |
| 494 |
<para> |
| 495 |
Returns subpath of <type>ltree</type> starting at |
| 496 |
position <parameter>offset</parameter>, extending to end of path. |
| 497 |
If <parameter>offset</parameter> is negative, subpath starts that far |
| 498 |
from the end of the path. |
| 499 |
</para> |
| 500 |
<para> |
| 501 |
<literal>subpath('Top.Child1.Child2', 1)</literal> |
| 502 |
<returnvalue>Child1.Child2</returnvalue> |
| 503 |
</para></entry> |
| 504 |
</row> |
| 505 |
|
| 506 |
<row> |
| 507 |
<entry role="func_table_entry"><para role="func_signature"> |
| 508 |
<indexterm><primary>nlevel</primary></indexterm> |
| 509 |
<function>nlevel</function> ( <type>ltree</type> ) |
| 510 |
<returnvalue>integer</returnvalue> |
| 511 |
</para> |
| 512 |
<para> |
| 513 |
Returns number of labels in path. |
| 514 |
</para> |
| 515 |
<para> |
| 516 |
<literal>nlevel('Top.Child1.Child2')</literal> |
| 517 |
<returnvalue>3</returnvalue> |
| 518 |
</para></entry> |
| 519 |
</row> |
| 520 |
|
| 521 |
<row> |
| 522 |
<entry role="func_table_entry"><para role="func_signature"> |
| 523 |
<indexterm><primary>index</primary></indexterm> |
| 524 |
<function>index</function> ( <parameter>a</parameter> <type>ltree</type>, <parameter>b</parameter> <type>ltree</type> ) |
| 525 |
<returnvalue>integer</returnvalue> |
| 526 |
</para> |
| 527 |
<para> |
| 528 |
Returns position of first occurrence of <parameter>b</parameter> in |
| 529 |
<parameter>a</parameter>, or -1 if not found. |
| 530 |
</para> |
| 531 |
<para> |
| 532 |
<literal>index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')</literal> |
| 533 |
<returnvalue>6</returnvalue> |
| 534 |
</para></entry> |
| 535 |
</row> |
| 536 |
|
| 537 |
<row> |
| 538 |
<entry role="func_table_entry"><para role="func_signature"> |
| 539 |
<function>index</function> ( <parameter>a</parameter> <type>ltree</type>, <parameter>b</parameter> <type>ltree</type>, <parameter>offset</parameter> <type>integer</type> ) |
| 540 |
<returnvalue>integer</returnvalue> |
| 541 |
</para> |
| 542 |
<para> |
| 543 |
Returns position of first occurrence of <parameter>b</parameter> |
| 544 |
in <parameter>a</parameter>, or -1 if not found. The search starts at |
| 545 |
position <parameter>offset</parameter>; |
| 546 |
negative <parameter>offset</parameter> means |
| 547 |
start <parameter>-offset</parameter> labels from the end of the path. |
| 548 |
</para> |
| 549 |
<para> |
| 550 |
<literal>index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6', -4)</literal> |
| 551 |
<returnvalue>9</returnvalue> |
| 552 |
</para></entry> |
| 553 |
</row> |
| 554 |
|
| 555 |
<row> |
| 556 |
<entry role="func_table_entry"><para role="func_signature"> |
| 557 |
<indexterm><primary>text2ltree</primary></indexterm> |
| 558 |
<function>text2ltree</function> ( <type>text</type> ) |
| 559 |
<returnvalue>ltree</returnvalue> |
| 560 |
</para> |
| 561 |
<para> |
| 562 |
Casts <type>text</type> to <type>ltree</type>. |
| 563 |
</para></entry> |
| 564 |
</row> |
| 565 |
|
| 566 |
<row> |
| 567 |
<entry role="func_table_entry"><para role="func_signature"> |
| 568 |
<indexterm><primary>ltree2text</primary></indexterm> |
| 569 |
<function>ltree2text</function> ( <type>ltree</type> ) |
| 570 |
<returnvalue>text</returnvalue> |
| 571 |
</para> |
| 572 |
<para> |
| 573 |
Casts <type>ltree</type> to <type>text</type>. |
| 574 |
</para></entry> |
| 575 |
</row> |
| 576 |
|
| 577 |
<row> |
| 578 |
<entry role="func_table_entry"><para role="func_signature"> |
| 579 |
<indexterm><primary>lca</primary></indexterm> |
| 580 |
<function>lca</function> ( <type>ltree</type> <optional>, <type>ltree</type> <optional>, ... </optional></optional> ) |
| 581 |
<returnvalue>ltree</returnvalue> |
| 582 |
</para> |
| 583 |
<para> |
| 584 |
Computes longest common ancestor of paths |
| 585 |
(up to 8 arguments are supported). |
| 586 |
</para> |
| 587 |
<para> |
| 588 |
<literal>lca('1.2.3', '1.2.3.4.5.6')</literal> |
| 589 |
<returnvalue>1.2</returnvalue> |
| 590 |
</para></entry> |
| 591 |
</row> |
| 592 |
|
| 593 |
<row> |
| 594 |
<entry role="func_table_entry"><para role="func_signature"> |
| 595 |
<function>lca</function> ( <type>ltree[]</type> ) |
| 596 |
<returnvalue>ltree</returnvalue> |
| 597 |
</para> |
| 598 |
<para> |
| 599 |
Computes longest common ancestor of paths in array. |
| 600 |
</para> |
| 601 |
<para> |
| 602 |
<literal>lca(array['1.2.3'::ltree,'1.2.3.4'])</literal> |
| 603 |
<returnvalue>1.2</returnvalue> |
| 604 |
</para></entry> |
| 605 |
</row> |
| 606 |
</tbody> |
| 607 |
</tgroup> |
| 608 |
</table> |
| 609 |
</sect2> |
| 610 |
|
| 611 |
<sect2 id="ltree-indexes"> |
| 612 |
<title>Indexes</title> |
| 613 |
<para> |
| 614 |
<filename>ltree</filename> supports several types of indexes that can speed |
| 615 |
up the indicated operators: |
| 616 |
</para> |
| 617 |
|
| 618 |
<itemizedlist> |
| 619 |
<listitem> |
| 620 |
<para> |
| 621 |
B-tree index over <type>ltree</type>: |
| 622 |
<literal><</literal>, <literal><=</literal>, <literal>=</literal>, |
| 623 |
<literal>>=</literal>, <literal>></literal> |
| 624 |
</para> |
| 625 |
</listitem> |
| 626 |
<listitem> |
| 627 |
<para> |
| 628 |
Hash index over <type>ltree</type>: |
| 629 |
<literal>=</literal> |
| 630 |
</para> |
| 631 |
</listitem> |
| 632 |
|
| 633 |
<listitem> |
| 634 |
<para> |
| 635 |
GiST index over <type>ltree</type> (<literal>gist_ltree_ops</literal> |
| 636 |
opclass): |
| 637 |
<literal><</literal>, <literal><=</literal>, <literal>=</literal>, |
| 638 |
<literal>>=</literal>, <literal>></literal>, |
| 639 |
<literal>@></literal>, <literal><@</literal>, |
| 640 |
<literal>@</literal>, <literal>~</literal>, <literal>?</literal> |
| 641 |
</para> |
| 642 |
<para> |
| 643 |
<literal>gist_ltree_ops</literal> GiST opclass approximates a set of |
| 644 |
path labels as a bitmap signature. Its optional integer parameter |
| 645 |
<literal>siglen</literal> determines the |
| 646 |
signature length in bytes. The default signature length is 8 bytes. |
| 647 |
The length must be a positive multiple of <type>int</type> alignment |
| 648 |
(4 bytes on most machines)) up to 2024. Longer |
| 649 |
signatures lead to a more precise search (scanning a smaller fraction of the index and |
| 650 |
fewer heap pages), at the cost of a larger index. |
| 651 |
</para> |
| 652 |
<para> |
| 653 |
Example of creating such an index with the default signature length of 8 bytes: |
| 654 |
</para> |
| 655 |
<programlisting> |
| 656 |
CREATE INDEX path_gist_idx ON test USING GIST (path); |
| 657 |
</programlisting> |
| 658 |
<para> |
| 659 |
Example of creating such an index with a signature length of 100 bytes: |
| 660 |
</para> |
| 661 |
<programlisting> |
| 662 |
CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100)); |
| 663 |
</programlisting> |
| 664 |
</listitem> |
| 665 |
<listitem> |
| 666 |
<para> |
| 667 |
GiST index over <type>ltree[]</type> (<literal>gist__ltree_ops</literal> |
| 668 |
opclass): |
| 669 |
<literal>ltree[] <@ ltree</literal>, <literal>ltree @> ltree[]</literal>, |
| 670 |
<literal>@</literal>, <literal>~</literal>, <literal>?</literal> |
| 671 |
</para> |
| 672 |
<para> |
| 673 |
<literal>gist__ltree_ops</literal> GiST opclass works similarly to |
| 674 |
<literal>gist_ltree_ops</literal> and also takes signature length as |
| 675 |
a parameter. The default value of <literal>siglen</literal> in |
| 676 |
<literal>gist__ltree_ops</literal> is 28 bytes. |
| 677 |
</para> |
| 678 |
<para> |
| 679 |
Example of creating such an index with the default signature length of 28 bytes: |
| 680 |
</para> |
| 681 |
<programlisting> |
| 682 |
CREATE INDEX path_gist_idx ON test USING GIST (array_path); |
| 683 |
</programlisting> |
| 684 |
<para> |
| 685 |
Example of creating such an index with a signature length of 100 bytes: |
| 686 |
</para> |
| 687 |
<programlisting> |
| 688 |
CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100)); |
| 689 |
</programlisting> |
| 690 |
<para> |
| 691 |
Note: This index type is lossy. |
| 692 |
</para> |
| 693 |
</listitem> |
| 694 |
</itemizedlist> |
| 695 |
</sect2> |
| 696 |
|
| 697 |
<sect2 id="ltree-example"> |
| 698 |
<title>Example</title> |
| 699 |
|
| 700 |
<para> |
| 701 |
This example uses the following data (also available in file |
| 702 |
<filename>contrib/ltree/ltreetest.sql</filename> in the source distribution): |
| 703 |
</para> |
| 704 |
|
| 705 |
<programlisting> |
| 706 |
CREATE TABLE test (path ltree); |
| 707 |
INSERT INTO test VALUES ('Top'); |
| 708 |
INSERT INTO test VALUES ('Top.Science'); |
| 709 |
INSERT INTO test VALUES ('Top.Science.Astronomy'); |
| 710 |
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics'); |
| 711 |
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology'); |
| 712 |
INSERT INTO test VALUES ('Top.Hobbies'); |
| 713 |
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy'); |
| 714 |
INSERT INTO test VALUES ('Top.Collections'); |
| 715 |
INSERT INTO test VALUES ('Top.Collections.Pictures'); |
| 716 |
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy'); |
| 717 |
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars'); |
| 718 |
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies'); |
| 719 |
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts'); |
| 720 |
CREATE INDEX path_gist_idx ON test USING GIST (path); |
| 721 |
CREATE INDEX path_idx ON test USING BTREE (path); |
| 722 |
CREATE INDEX path_hash_idx ON test USING HASH (path); |
| 723 |
</programlisting> |
| 724 |
|
| 725 |
<para> |
| 726 |
Now, we have a table <structname>test</structname> populated with data describing |
| 727 |
the hierarchy shown below: |
| 728 |
</para> |
| 729 |
|
| 730 |
<literallayout class="monospaced"> |
| 731 |
Top |
| 732 |
/ | \ |
| 733 |
Science Hobbies Collections |
| 734 |
/ | \ |
| 735 |
Astronomy Amateurs_Astronomy Pictures |
| 736 |
/ \ | |
| 737 |
Astrophysics Cosmology Astronomy |
| 738 |
/ | \ |
| 739 |
Galaxies Stars Astronauts |
| 740 |
</literallayout> |
| 741 |
|
| 742 |
<para> |
| 743 |
We can do inheritance: |
| 744 |
<screen> |
| 745 |
ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science'; |
| 746 |
path |
| 747 |
------------------------------------ |
| 748 |
Top.Science |
| 749 |
Top.Science.Astronomy |
| 750 |
Top.Science.Astronomy.Astrophysics |
| 751 |
Top.Science.Astronomy.Cosmology |
| 752 |
(4 rows) |
| 753 |
</screen> |
| 754 |
</para> |
| 755 |
|
| 756 |
<para> |
| 757 |
Here are some examples of path matching: |
| 758 |
<screen> |
| 759 |
ltreetest=> SELECT path FROM test WHERE path ~ '*.Astronomy.*'; |
| 760 |
path |
| 761 |
----------------------------------------------- |
| 762 |
Top.Science.Astronomy |
| 763 |
Top.Science.Astronomy.Astrophysics |
| 764 |
Top.Science.Astronomy.Cosmology |
| 765 |
Top.Collections.Pictures.Astronomy |
| 766 |
Top.Collections.Pictures.Astronomy.Stars |
| 767 |
Top.Collections.Pictures.Astronomy.Galaxies |
| 768 |
Top.Collections.Pictures.Astronomy.Astronauts |
| 769 |
(7 rows) |
| 770 |
|
| 771 |
ltreetest=> SELECT path FROM test WHERE path ~ '*[email protected].*'; |
| 772 |
path |
| 773 |
------------------------------------ |
| 774 |
Top.Science.Astronomy |
| 775 |
Top.Science.Astronomy.Astrophysics |
| 776 |
Top.Science.Astronomy.Cosmology |
| 777 |
(3 rows) |
| 778 |
</screen> |
| 779 |
</para> |
| 780 |
|
| 781 |
<para> |
| 782 |
Here are some examples of full text search: |
| 783 |
<screen> |
| 784 |
ltreetest=> SELECT path FROM test WHERE path @ 'Astro*% & !pictures@'; |
| 785 |
path |
| 786 |
------------------------------------ |
| 787 |
Top.Science.Astronomy |
| 788 |
Top.Science.Astronomy.Astrophysics |
| 789 |
Top.Science.Astronomy.Cosmology |
| 790 |
Top.Hobbies.Amateurs_Astronomy |
| 791 |
(4 rows) |
| 792 |
|
| 793 |
ltreetest=> SELECT path FROM test WHERE path @ 'Astro* & !pictures@'; |
| 794 |
path |
| 795 |
------------------------------------ |
| 796 |
Top.Science.Astronomy |
| 797 |
Top.Science.Astronomy.Astrophysics |
| 798 |
Top.Science.Astronomy.Cosmology |
| 799 |
(3 rows) |
| 800 |
</screen> |
| 801 |
</para> |
| 802 |
|
| 803 |
<para> |
| 804 |
Path construction using functions: |
| 805 |
<screen> |
| 806 |
ltreetest=> SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE path <@ 'Top.Science.Astronomy'; |
| 807 |
?column? |
| 808 |
------------------------------------------ |
| 809 |
Top.Science.Space.Astronomy |
| 810 |
Top.Science.Space.Astronomy.Astrophysics |
| 811 |
Top.Science.Space.Astronomy.Cosmology |
| 812 |
(3 rows) |
| 813 |
</screen> |
| 814 |
</para> |
| 815 |
|
| 816 |
<para> |
| 817 |
We could simplify this by creating an SQL function that inserts a label |
| 818 |
at a specified position in a path: |
| 819 |
<screen> |
| 820 |
CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree |
| 821 |
AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);' |
| 822 |
LANGUAGE SQL IMMUTABLE; |
| 823 |
|
| 824 |
ltreetest=> SELECT ins_label(path,2,'Space') FROM test WHERE path <@ 'Top.Science.Astronomy'; |
| 825 |
ins_label |
| 826 |
------------------------------------------ |
| 827 |
Top.Science.Space.Astronomy |
| 828 |
Top.Science.Space.Astronomy.Astrophysics |
| 829 |
Top.Science.Space.Astronomy.Cosmology |
| 830 |
(3 rows) |
| 831 |
</screen> |
| 832 |
</para> |
| 833 |
</sect2> |
| 834 |
|
| 835 |
<sect2 id="ltree-transforms"> |
| 836 |
<title>Transforms</title> |
| 837 |
|
| 838 |
<para> |
| 839 |
The <literal>ltree_plpython3u</literal> extension implements transforms for |
| 840 |
the <type>ltree</type> type for PL/Python. If installed and specified when |
| 841 |
creating a function, <type>ltree</type> values are mapped to Python lists. |
| 842 |
(The reverse is currently not supported, however.) |
| 843 |
</para> |
| 844 |
</sect2> |
| 845 |
|
| 846 |
<sect2 id="ltree-authors"> |
| 847 |
<title>Authors</title> |
| 848 |
|
| 849 |
<para> |
| 850 |
All work was done by Teodor Sigaev (<email>[email protected]</email>) and |
| 851 |
Oleg Bartunov (<email>[email protected]</email>). See |
| 852 |
<ulink url="http://www.sai.msu.su/~megera/postgres/gist/"></ulink> for |
| 853 |
additional information. Authors would like to thank Eugeny Rodichev for |
| 854 |
helpful discussions. Comments and bug reports are welcome. |
| 855 |
</para> |
| 856 |
</sect2> |
| 857 |
|
| 858 |
</sect1> |