Debian Codegraph @

doc/src/sgml/cube.sgml

raw
1 <!-- doc/src/sgml/cube.sgml -->
2
3 <sect1 id="cube" xreflabel="cube">
4 <title>cube &mdash; a multi-dimensional cube data type</title>
5
6 <indexterm zone="cube">
7 <primary>cube (extension)</primary>
8 </indexterm>
9
10 <para>
11 This module implements a data type <type>cube</type> for
12 representing multidimensional cubes.
13 </para>
14
15 <para>
16 This module is considered <quote>trusted</quote>, that is, it can be
17 installed by non-superusers who have <literal>CREATE</literal> privilege
18 on the current database.
19 </para>
20
21 <sect2 id="cube-syntax">
22 <title>Syntax</title>
23
24 <para>
25 <xref linkend="cube-repr-table"/> shows the valid external
26 representations for the <type>cube</type>
27 type. <replaceable>x</replaceable>, <replaceable>y</replaceable>, etc. denote
28 floating-point numbers.
29 </para>
30
31 <table id="cube-repr-table">
32 <title>Cube External Representations</title>
33 <tgroup cols="2">
34 <thead>
35 <row>
36 <entry>External Syntax</entry>
37 <entry>Meaning</entry>
38 </row>
39 </thead>
40
41 <tbody>
42 <row>
43 <entry><literal><replaceable>x</replaceable></literal></entry>
44 <entry>A one-dimensional point
45 (or, zero-length one-dimensional interval)
46 </entry>
47 </row>
48 <row>
49 <entry><literal>(<replaceable>x</replaceable>)</literal></entry>
50 <entry>Same as above</entry>
51 </row>
52 <row>
53 <entry><literal><replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable></literal></entry>
54 <entry>A point in n-dimensional space, represented internally as a
55 zero-volume cube
56 </entry>
57 </row>
58 <row>
59 <entry><literal>(<replaceable>x1</replaceable>,<replaceable>x2</replaceable>,...,<replaceable>xn</replaceable>)</literal></entry>
60 <entry>Same as above</entry>
61 </row>
62 <row>
63 <entry><literal>(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)</literal></entry>
64 <entry>A one-dimensional interval starting at <replaceable>x</replaceable> and ending at <replaceable>y</replaceable> or vice versa; the
65 order does not matter
66 </entry>
67 </row>
68 <row>
69 <entry><literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal></entry>
70 <entry>Same as above</entry>
71 </row>
72 <row>
73 <entry><literal>(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)</literal></entry>
74 <entry>An n-dimensional cube represented by a pair of its diagonally
75 opposite corners
76 </entry>
77 </row>
78 <row>
79 <entry><literal>[(<replaceable>x1</replaceable>,...,<replaceable>xn</replaceable>),(<replaceable>y1</replaceable>,...,<replaceable>yn</replaceable>)]</literal></entry>
80 <entry>Same as above</entry>
81 </row>
82 </tbody>
83 </tgroup>
84 </table>
85
86 <para>
87 It does not matter which order the opposite corners of a cube are
88 entered in. The <type>cube</type> functions
89 automatically swap values if needed to create a uniform
90 <quote>lower left &mdash; upper right</quote> internal representation.
91 When the corners coincide, <type>cube</type> stores only one corner
92 along with an <quote>is point</quote> flag to avoid wasting space.
93 </para>
94
95 <para>
96 White space is ignored on input, so
97 <literal>[(<replaceable>x</replaceable>),(<replaceable>y</replaceable>)]</literal> is the same as
98 <literal>[ ( <replaceable>x</replaceable> ), ( <replaceable>y</replaceable> ) ]</literal>.
99 </para>
100 </sect2>
101
102 <sect2 id="cube-precision">
103 <title>Precision</title>
104
105 <para>
106 Values are stored internally as 64-bit floating point numbers. This means
107 that numbers with more than about 16 significant digits will be truncated.
108 </para>
109 </sect2>
110
111 <sect2 id="cube-usage">
112 <title>Usage</title>
113
114 <para>
115 <xref linkend="cube-operators-table"/> shows the specialized operators
116 provided for type <type>cube</type>.
117 </para>
118
119 <table id="cube-operators-table">
120 <title>Cube Operators</title>
121 <tgroup cols="1">
122 <thead>
123 <row>
124 <entry role="func_table_entry"><para role="func_signature">
125 Operator
126 </para>
127 <para>
128 Description
129 </para></entry>
130 </row>
131 </thead>
132
133 <tbody>
134 <row>
135 <entry role="func_table_entry"><para role="func_signature">
136 <type>cube</type> <literal>&amp;&amp;</literal> <type>cube</type>
137 <returnvalue>boolean</returnvalue>
138 </para>
139 <para>
140 Do the cubes overlap?
141 </para></entry>
142 </row>
143
144 <row>
145 <entry role="func_table_entry"><para role="func_signature">
146 <type>cube</type> <literal>@&gt;</literal> <type>cube</type>
147 <returnvalue>boolean</returnvalue>
148 </para>
149 <para>
150 Does the first cube contain the second?
151 </para></entry>
152 </row>
153
154 <row>
155 <entry role="func_table_entry"><para role="func_signature">
156 <type>cube</type> <literal>&lt;@</literal> <type>cube</type>
157 <returnvalue>boolean</returnvalue>
158 </para>
159 <para>
160 Is the first cube contained in the second?
161 </para></entry>
162 </row>
163
164 <row>
165 <entry role="func_table_entry"><para role="func_signature">
166 <type>cube</type> <literal>-&gt;</literal> <type>integer</type>
167 <returnvalue>float8</returnvalue>
168 </para>
169 <para>
170 Extracts the <parameter>n</parameter>-th coordinate of the cube
171 (counting from 1).
172 </para></entry>
173 </row>
174
175 <row>
176 <entry role="func_table_entry"><para role="func_signature">
177 <type>cube</type> <literal>~&gt;</literal> <type>integer</type>
178 <returnvalue>float8</returnvalue>
179 </para>
180 <para>
181 Extracts the <parameter>n</parameter>-th coordinate of the cube,
182 counting in the following way: <parameter>n</parameter> = 2
183 * <parameter>k</parameter> - 1 means lower bound
184 of <parameter>k</parameter>-th dimension, <parameter>n</parameter> = 2
185 * <parameter>k</parameter> means upper bound of
186 <parameter>k</parameter>-th dimension. Negative
187 <parameter>n</parameter> denotes the inverse value of the corresponding
188 positive coordinate. This operator is designed for KNN-GiST support.
189 </para></entry>
190 </row>
191
192 <row>
193 <entry role="func_table_entry"><para role="func_signature">
194 <type>cube</type> <literal>&lt;-&gt;</literal> <type>cube</type>
195 <returnvalue>float8</returnvalue>
196 </para>
197 <para>
198 Computes the Euclidean distance between the two cubes.
199 </para></entry>
200 </row>
201
202 <row>
203 <entry role="func_table_entry"><para role="func_signature">
204 <type>cube</type> <literal>&lt;#&gt;</literal> <type>cube</type>
205 <returnvalue>float8</returnvalue>
206 </para>
207 <para>
208 Computes the taxicab (L-1 metric) distance between the two cubes.
209 </para></entry>
210 </row>
211
212 <row>
213 <entry role="func_table_entry"><para role="func_signature">
214 <type>cube</type> <literal>&lt;=&gt;</literal> <type>cube</type>
215 <returnvalue>float8</returnvalue>
216 </para>
217 <para>
218 Computes the Chebyshev (L-inf metric) distance between the two cubes.
219 </para></entry>
220 </row>
221 </tbody>
222 </tgroup>
223 </table>
224
225 <para>
226 In addition to the above operators, the usual comparison
227 operators shown in <xref linkend="functions-comparison-op-table"/> are
228 available for type <type>cube</type>. These
229 operators first compare the first coordinates, and if those are equal,
230 compare the second coordinates, etc. They exist mainly to support the
231 b-tree index operator class for <type>cube</type>, which can be useful for
232 example if you would like a UNIQUE constraint on a <type>cube</type> column.
233 Otherwise, this ordering is not of much practical use.
234 </para>
235
236 <para>
237 The <filename>cube</filename> module also provides a GiST index operator class for
238 <type>cube</type> values.
239 A <type>cube</type> GiST index can be used to search for values using the
240 <literal>=</literal>, <literal>&amp;&amp;</literal>, <literal>@&gt;</literal>, and
241 <literal>&lt;@</literal> operators in <literal>WHERE</literal> clauses.
242 </para>
243
244 <para>
245 In addition, a <type>cube</type> GiST index can be used to find nearest
246 neighbors using the metric operators
247 <literal>&lt;-&gt;</literal>, <literal>&lt;#&gt;</literal>, and
248 <literal>&lt;=&gt;</literal> in <literal>ORDER BY</literal> clauses.
249 For example, the nearest neighbor of the 3-D point (0.5, 0.5, 0.5)
250 could be found efficiently with:
251 <programlisting>
252 SELECT c FROM test ORDER BY c &lt;-&gt; cube(array[0.5,0.5,0.5]) LIMIT 1;
253 </programlisting>
254 </para>
255
256 <para>
257 The <literal>~&gt;</literal> operator can also be used in this way to
258 efficiently retrieve the first few values sorted by a selected coordinate.
259 For example, to get the first few cubes ordered by the first coordinate
260 (lower left corner) ascending one could use the following query:
261 <programlisting>
262 SELECT c FROM test ORDER BY c ~&gt; 1 LIMIT 5;
263 </programlisting>
264 And to get 2-D cubes ordered by the first coordinate of the upper right
265 corner descending:
266 <programlisting>
267 SELECT c FROM test ORDER BY c ~&gt; 3 DESC LIMIT 5;
268 </programlisting>
269 </para>
270
271 <para>
272 <xref linkend="cube-functions-table"/> shows the available functions.
273 </para>
274
275 <table id="cube-functions-table">
276 <title>Cube Functions</title>
277 <tgroup cols="1">
278 <thead>
279 <row>
280 <entry role="func_table_entry"><para role="func_signature">
281 Function
282 </para>
283 <para>
284 Description
285 </para>
286 <para>
287 Example(s)
288 </para></entry>
289 </row>
290 </thead>
291
292 <tbody>
293 <row>
294 <entry role="func_table_entry"><para role="func_signature">
295 <function>cube</function> ( <type>float8</type> )
296 <returnvalue>cube</returnvalue>
297 </para>
298 <para>
299 Makes a one dimensional cube with both coordinates the same.
300 </para>
301 <para>
302 <literal>cube(1)</literal>
303 <returnvalue>(1)</returnvalue>
304 </para></entry>
305 </row>
306
307 <row>
308 <entry role="func_table_entry"><para role="func_signature">
309 <function>cube</function> ( <type>float8</type>, <type>float8</type> )
310 <returnvalue>cube</returnvalue>
311 </para>
312 <para>
313 Makes a one dimensional cube.
314 </para>
315 <para>
316 <literal>cube(1, 2)</literal>
317 <returnvalue>(1),(2)</returnvalue>
318 </para></entry>
319 </row>
320
321 <row>
322 <entry role="func_table_entry"><para role="func_signature">
323 <function>cube</function> ( <type>float8[]</type> )
324 <returnvalue>cube</returnvalue>
325 </para>
326 <para>
327 Makes a zero-volume cube using the coordinates defined by the array.
328 </para>
329 <para>
330 <literal>cube(ARRAY[1,2,3])</literal>
331 <returnvalue>(1, 2, 3)</returnvalue>
332 </para></entry>
333 </row>
334
335 <row>
336 <entry role="func_table_entry"><para role="func_signature">
337 <function>cube</function> ( <type>float8[]</type>, <type>float8[]</type> )
338 <returnvalue>cube</returnvalue>
339 </para>
340 <para>
341 Makes a cube with upper right and lower left coordinates as defined by
342 the two arrays, which must be of the same length.
343 </para>
344 <para>
345 <literal>cube(ARRAY[1,2], ARRAY[3,4])</literal>
346 <returnvalue>(1, 2),(3, 4)</returnvalue>
347 </para></entry>
348 </row>
349
350 <row>
351 <entry role="func_table_entry"><para role="func_signature">
352 <function>cube</function> ( <type>cube</type>, <type>float8</type> )
353 <returnvalue>cube</returnvalue>
354 </para>
355 <para>
356 Makes a new cube by adding a dimension on to an existing cube,
357 with the same values for both endpoints of the new coordinate. This
358 is useful for building cubes piece by piece from calculated values.
359 </para>
360 <para>
361 <literal>cube('(1,2),(3,4)'::cube, 5)</literal>
362 <returnvalue>(1, 2, 5),(3, 4, 5)</returnvalue>
363 </para></entry>
364 </row>
365
366 <row>
367 <entry role="func_table_entry"><para role="func_signature">
368 <function>cube</function> ( <type>cube</type>, <type>float8</type>, <type>float8</type> )
369 <returnvalue>cube</returnvalue>
370 </para>
371 <para>
372 Makes a new cube by adding a dimension on to an existing cube. This is
373 useful for building cubes piece by piece from calculated values.
374 </para>
375 <para>
376 <literal>cube('(1,2),(3,4)'::cube, 5, 6)</literal>
377 <returnvalue>(1, 2, 5),(3, 4, 6)</returnvalue>
378 </para></entry>
379 </row>
380
381 <row>
382 <entry role="func_table_entry"><para role="func_signature">
383 <function>cube_dim</function> ( <type>cube</type> )
384 <returnvalue>integer</returnvalue>
385 </para>
386 <para>
387 Returns the number of dimensions of the cube.
388 </para>
389 <para>
390 <literal>cube_dim('(1,2),(3,4)')</literal>
391 <returnvalue>2</returnvalue>
392 </para></entry>
393 </row>
394
395 <row>
396 <entry role="func_table_entry"><para role="func_signature">
397 <function>cube_ll_coord</function> ( <type>cube</type>, <type>integer</type> )
398 <returnvalue>float8</returnvalue>
399 </para>
400 <para>
401 Returns the <parameter>n</parameter>-th coordinate value for the lower
402 left corner of the cube.
403 </para>
404 <para>
405 <literal>cube_ll_coord('(1,2),(3,4)', 2)</literal>
406 <returnvalue>2</returnvalue>
407 </para></entry>
408 </row>
409
410 <row>
411 <entry role="func_table_entry"><para role="func_signature">
412 <function>cube_ur_coord</function> ( <type>cube</type>, <type>integer</type> )
413 <returnvalue>float8</returnvalue>
414 </para>
415 <para>
416 Returns the <parameter>n</parameter>-th coordinate value for the
417 upper right corner of the cube.
418 </para>
419 <para>
420 <literal>cube_ur_coord('(1,2),(3,4)', 2)</literal>
421 <returnvalue>4</returnvalue>
422 </para></entry>
423 </row>
424
425 <row>
426 <entry role="func_table_entry"><para role="func_signature">
427 <function>cube_is_point</function> ( <type>cube</type> )
428 <returnvalue>boolean</returnvalue>
429 </para>
430 <para>
431 Returns true if the cube is a point, that is,
432 the two defining corners are the same.
433 </para>
434 <para>
435 <literal>cube_is_point(cube(1,1))</literal>
436 <returnvalue>t</returnvalue>
437 </para></entry>
438 </row>
439
440 <row>
441 <entry role="func_table_entry"><para role="func_signature">
442 <function>cube_distance</function> ( <type>cube</type>, <type>cube</type> )
443 <returnvalue>float8</returnvalue>
444 </para>
445 <para>
446 Returns the distance between two cubes. If both
447 cubes are points, this is the normal distance function.
448 </para>
449 <para>
450 <literal>cube_distance('(1,2)', '(3,4)')</literal>
451 <returnvalue>2.8284271247461903</returnvalue>
452 </para></entry>
453 </row>
454
455 <row>
456 <entry role="func_table_entry"><para role="func_signature">
457 <function>cube_subset</function> ( <type>cube</type>, <type>integer[]</type> )
458 <returnvalue>cube</returnvalue>
459 </para>
460 <para>
461 Makes a new cube from an existing cube, using a list of
462 dimension indexes from an array. Can be used to extract the endpoints
463 of a single dimension, or to drop dimensions, or to reorder them as
464 desired.
465 </para>
466 <para>
467 <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[2])</literal>
468 <returnvalue>(3),(7)</returnvalue>
469 </para>
470 <para>
471 <literal>cube_subset(cube('(1,3,5),(6,7,8)'), ARRAY[3,2,1,1])</literal>
472 <returnvalue>(5, 3, 1, 1),(8, 7, 6, 6)</returnvalue>
473 </para></entry>
474 </row>
475
476 <row>
477 <entry role="func_table_entry"><para role="func_signature">
478 <function>cube_union</function> ( <type>cube</type>, <type>cube</type> )
479 <returnvalue>cube</returnvalue>
480 </para>
481 <para>
482 Produces the union of two cubes.
483 </para>
484 <para>
485 <literal>cube_union('(1,2)', '(3,4)')</literal>
486 <returnvalue>(1, 2),(3, 4)</returnvalue>
487 </para></entry>
488 </row>
489
490 <row>
491 <entry role="func_table_entry"><para role="func_signature">
492 <function>cube_inter</function> ( <type>cube</type>, <type>cube</type> )
493 <returnvalue>cube</returnvalue>
494 </para>
495 <para>
496 Produces the intersection of two cubes.
497 </para>
498 <para>
499 <literal>cube_inter('(1,2)', '(3,4)')</literal>
500 <returnvalue>(3, 4),(1, 2)</returnvalue>
501 </para></entry>
502 </row>
503
504 <row>
505 <entry role="func_table_entry"><para role="func_signature">
506 <function>cube_enlarge</function> ( <parameter>c</parameter> <type>cube</type>, <parameter>r</parameter> <type>double</type>, <parameter>n</parameter> <type>integer</type> )
507 <returnvalue>cube</returnvalue>
508 </para>
509 <para>
510 Increases the size of the cube by the specified
511 radius <parameter>r</parameter> in at least <parameter>n</parameter>
512 dimensions. If the radius is negative the cube is shrunk instead.
513 All defined dimensions are changed by the
514 radius <parameter>r</parameter>. Lower-left coordinates are decreased
515 by <parameter>r</parameter> and upper-right coordinates are increased
516 by <parameter>r</parameter>. If a lower-left coordinate is increased
517 to more than the corresponding upper-right coordinate (this can only
518 happen when <parameter>r</parameter> &lt; 0) than both coordinates are
519 set to their average. If <parameter>n</parameter> is greater than the
520 number of defined dimensions and the cube is being enlarged
521 (<parameter>r</parameter> &gt; 0), then extra dimensions are added to
522 make <parameter>n</parameter> altogether; 0 is used as the initial
523 value for the extra coordinates. This function is useful for creating
524 bounding boxes around a point for searching for nearby points.
525 </para>
526 <para>
527 <literal>cube_enlarge('(1,2),(3,4)', 0.5, 3)</literal>
528 <returnvalue>(0.5, 1.5, -0.5),(3.5, 4.5, 0.5)</returnvalue>
529 </para></entry>
530 </row>
531 </tbody>
532 </tgroup>
533 </table>
534 </sect2>
535
536 <sect2 id="cube-defaults">
537 <title>Defaults</title>
538
539 <para>
540 This union:
541 </para>
542 <programlisting>
543 select cube_union('(0,5,2),(2,3,1)', '0');
544 cube_union
545 -------------------
546 (0, 0, 0),(2, 5, 2)
547 (1 row)
548 </programlisting>
549
550 <para>
551 does not contradict common sense, neither does the intersection:
552 </para>
553
554 <programlisting>
555 select cube_inter('(0,-1),(1,1)', '(-2),(2)');
556 cube_inter
557 -------------
558 (0, 0),(1, 0)
559 (1 row)
560 </programlisting>
561
562 <para>
563 In all binary operations on differently-dimensioned cubes,
564 the lower-dimensional one is assumed to be a Cartesian projection, i. e., having zeroes
565 in place of coordinates omitted in the string representation. The above
566 examples are equivalent to:
567 </para>
568
569 <programlisting>
570 cube_union('(0,5,2),(2,3,1)','(0,0,0),(0,0,0)');
571 cube_inter('(0,-1),(1,1)','(-2,0),(2,0)');
572 </programlisting>
573
574 <para>
575 The following containment predicate uses the point syntax,
576 while in fact the second argument is internally represented by a box.
577 This syntax makes it unnecessary to define a separate point type
578 and functions for (box,point) predicates.
579 </para>
580
581 <programlisting>
582 select cube_contains('(0,0),(1,1)', '0.5,0.5');
583 cube_contains
584 --------------
585 t
586 (1 row)
587 </programlisting>
588 </sect2>
589
590 <sect2 id="cube-notes">
591 <title>Notes</title>
592
593 <para>
594 For examples of usage, see the regression test <filename>sql/cube.sql</filename>.
595 </para>
596
597 <para>
598 To make it harder for people to break things, there
599 is a limit of 100 on the number of dimensions of cubes. This is set
600 in <filename>cubedata.h</filename> if you need something bigger.
601 </para>
602 </sect2>
603
604 <sect2 id="cube-credits">
605 <title>Credits</title>
606
607 <para>
608 Original author: Gene Selkov, Jr. <email>[email protected]</email>,
609 Mathematics and Computer Science Division, Argonne National Laboratory.
610 </para>
611
612 <para>
613 My thanks are primarily to Prof. Joe Hellerstein
614 (<ulink url="https://dsf.berkeley.edu/jmh/"></ulink>) for elucidating the
615 gist of the GiST (<ulink url="http://gist.cs.berkeley.edu/"></ulink>), and
616 to his former student Andy Dong for his example written for Illustra.
617 I am also grateful to all Postgres developers, present and past, for
618 enabling myself to create my own world and live undisturbed in it. And I
619 would like to acknowledge my gratitude to Argonne Lab and to the
620 U.S. Department of Energy for the years of faithful support of my database
621 research.
622 </para>
623
624 <para>
625 Minor updates to this package were made by Bruno Wolff III
626 <email>[email protected]</email> in August/September of 2002. These include
627 changing the precision from single precision to double precision and adding
628 some new functions.
629 </para>
630
631 <para>
632 Additional updates were made by Joshua Reich <email>[email protected]</email> in
633 July 2006. These include <literal>cube(float8[], float8[])</literal> and
634 cleaning up the code to use the V1 call protocol instead of the deprecated
635 V0 protocol.
636 </para>
637 </sect2>
638
639 </sect1>