doc/src/sgml/seg.sgml

   1 <!-- $PostgreSQL$ -->
   2
   3 <sect1 id="seg">
   4  <title>seg</title>
   5
   6  <indexterm zone="seg">
   7   <primary>seg</primary>
   8  </indexterm>
   9
  10  <para>
  11   This module implements a data type <type>seg</> for
  12   representing line segments, or floating point intervals.
  13   <type>seg</> can represent uncertainty in the interval endpoints,
  14   making it especially useful for representing laboratory measurements.
  15  </para>
  16
  17  <sect2>
  18   <title>Rationale</title>
  19
  20   <para>
  21    The geometry of measurements is usually more complex than that of a
  22    point in a numeric continuum. A measurement is usually a segment of
  23    that continuum with somewhat fuzzy limits. The measurements come out
  24    as intervals because of uncertainty and randomness, as well as because
  25    the value being measured may naturally be an interval indicating some
  26    condition, such as the temperature range of stability of a protein.
  27   </para>
  28
  29   <para>
  30    Using just common sense, it appears more convenient to store such data
  31    as intervals, rather than pairs of numbers. In practice, it even turns
  32    out more efficient in most applications.
  33   </para>
  34
  35   <para>
  36    Further along the line of common sense, the fuzziness of the limits
  37    suggests that the use of traditional numeric data types leads to a
  38    certain loss of information. Consider this: your instrument reads
  39    6.50, and you input this reading into the database. What do you get
  40    when you fetch it? Watch:
  41
  42   <programlisting>
  43 test=> select 6.50 :: float8 as "pH";
  44  pH
  45 ---
  46 6.5
  47 (1 row)
  48   </programlisting>
  49
  50    In the world of measurements, 6.50 is not the same as 6.5. It may
  51    sometimes be critically different. The experimenters usually write
  52    down (and publish) the digits they trust. 6.50 is actually a fuzzy
  53    interval contained within a bigger and even fuzzier interval, 6.5,
  54    with their center points being (probably) the only common feature they
  55    share. We definitely do not want such different data items to appear the
  56    same.
  57   </para>
  58
  59   <para>
  60    Conclusion? It is nice to have a special data type that can record the
  61    limits of an interval with arbitrarily variable precision. Variable in
  62    the sense that each data element records its own precision.
  63   </para>
  64
  65   <para>
  66    Check this out:
  67
  68    <programlisting>
  69 test=> select '6.25 .. 6.50'::seg as "pH";
  70           pH
  71 ------------
  72 6.25 .. 6.50
  73 (1 row)
  74    </programlisting>
  75   </para>
  76  </sect2>
  77
  78  <sect2>
  79   <title>Syntax</title>
  80
  81   <para>
  82    The external representation of an interval is formed using one or two
  83    floating point numbers joined by the range operator (<literal>..</literal>
  84    or <literal>...</literal>).  Alternatively, it can be specified as a
  85    center point plus or minus a deviation.
  86    Optional certainty indicators (<literal>&lt;</literal>,
  87    <literal>&gt;</literal> and <literal>~</literal>) can be stored as well.
  88    (Certainty indicators are ignored by all the built-in operators, however.)
  89   </para>
  90
  91   <para>
  92    In <xref linkend="seg-repr-table">, <replaceable>x</>, <replaceable>y</>, and
  93    <replaceable>delta</> denote
  94    floating-point numbers.  <replaceable>x</> and <replaceable>y</>, but
  95    not <replaceable>delta</>, can be preceded by a certainty indicator.
  96   </para>
  97
  98   <table id="seg-repr-table">
  99    <title><type>seg</> external representations</title>
 100    <tgroup cols="2">
 101     <tbody>
 102      <row>
 103       <entry><literal><replaceable>x</></literal></entry>
 104       <entry>Single value (zero-length interval)
 105       </entry>
 106      </row>
 107      <row>
 108       <entry><literal><replaceable>x</> .. <replaceable>y</></literal></entry>
 109       <entry>Interval from <replaceable>x</> to <replaceable>y</>
 110       </entry>
 111      </row>
 112      <row>
 113       <entry><literal><replaceable>x</> (+-) <replaceable>delta</></literal></entry>
 114       <entry>Interval from <replaceable>x</> - <replaceable>delta</> to
 115       <replaceable>x</> + <replaceable>delta</>
 116       </entry>
 117      </row>
 118      <row>
 119       <entry><literal><replaceable>x</> ..</literal></entry>
 120       <entry>Open interval with lower bound <replaceable>x</>
 121       </entry>
 122      </row>
 123      <row>
 124       <entry><literal>.. <replaceable>x</></literal></entry>
 125       <entry>Open interval with upper bound <replaceable>x</>
 126       </entry>
 127      </row>
 128     </tbody>
 129    </tgroup>
 130   </table>
 131
 132   <table>
 133    <title>Examples of valid <type>seg</> input</title>
 134    <tgroup cols="2">
 135     <tbody>
 136      <row>
 137       <entry><literal>5.0</literal></entry>
 138       <entry>
 139        Creates a zero-length segment (a point, if you will)
 140       </entry>
 141      </row>
 142      <row>
 143       <entry><literal>~5.0</literal></entry>
 144       <entry>
 145        Creates a zero-length segment and records
 146        <literal>~</> in the data.  <literal>~</literal> is ignored
 147        by <type>seg</> operations, but
 148        is preserved as a comment.
 149       </entry>
 150      </row>
 151      <row>
 152       <entry><literal>&lt;5.0</literal></entry>
 153       <entry>
 154        Creates a point at 5.0.  <literal>&lt;</literal> is ignored but
 155        is preserved as a comment.
 156       </entry>
 157      </row>
 158      <row>
 159       <entry><literal>&gt;5.0</literal></entry>
 160       <entry>
 161        Creates a point at 5.0.  <literal>&gt;</literal> is ignored but
 162        is preserved as a comment.
 163       </entry>
 164      </row>
 165      <row>
 166       <entry><literal>5(+-)0.3</literal></entry>
 167       <entry>
 168         Creates an interval <literal>4.7 .. 5.3</literal>.
 169         Note that the <literal>(+-)</> notation isn't preserved.
 170       </entry>
 171      </row>
 172      <row>
 173       <entry><literal>50 .. </literal></entry>
 174       <entry>Everything that is greater than or equal to 50</entry>
 175      </row>
 176      <row>
 177       <entry><literal>.. 0</literal></entry>
 178       <entry>Everything that is less than or equal to 0</entry>
 179      </row>
 180      <row>
 181       <entry><literal>1.5e-2 .. 2E-2 </literal></entry>
 182       <entry>Creates an interval <literal>0.015 .. 0.02</literal></entry>
 183      </row>
 184      <row>
 185       <entry><literal>1 ... 2</literal></entry>
 186       <entry>
 187        The same as <literal>1...2</literal>, or <literal>1 .. 2</literal>,
 188        or <literal>1..2</literal>
 189        (spaces around the range operator are ignored)
 190       </entry>
 191      </row>
 192     </tbody>
 193    </tgroup>
 194   </table>
 195
 196   <para>
 197    Because <literal>...</> is widely used in data sources, it is allowed
 198    as an alternative spelling of <literal>..</>.  Unfortunately, this
 199    creates a parsing ambiguity: it is not clear whether the upper bound
 200    in <literal>0...23</> is meant to be <literal>23</> or <literal>0.23</>.
 201    This is resolved by requiring at least one digit before the decimal
 202    point in all numbers in <type>seg</> input.
 203   </para>
 204
 205   <para>
 206    As a sanity check, <type>seg</> rejects intervals with the lower bound
 207    greater than the upper, for example <literal>5 .. 2</>.
 208   </para>
 209
 210  </sect2>
 211
 212  <sect2>
 213   <title>Precision</title>
 214
 215   <para>
 216    <type>seg</> values are stored internally as pairs of 32-bit floating point
 217    numbers. This means that numbers with more than 7 significant digits
 218    will be truncated.
 219   </para>
 220
 221   <para>
 222    Numbers with 7 or fewer significant digits retain their
 223    original precision. That is, if your query returns 0.00, you will be
 224    sure that the trailing zeroes are not the artifacts of formatting: they
 225    reflect the precision of the original data. The number of leading
 226    zeroes does not affect precision: the value 0.0067 is considered to
 227    have just 2 significant digits.
 228   </para>
 229  </sect2>
 230
 231  <sect2>
 232   <title>Usage</title>
 233
 234   <para>
 235    The <filename>seg</> module includes a GiST index operator class for
 236    <type>seg</> values.
 237    The operators supported by the GiST opclass include:
 238   </para>
 239
 240   <itemizedlist>
 241    <listitem>
 242     <programlisting>
 243 [a, b] &lt;&lt; [c, d]        Is left of
 244     </programlisting>
 245     <para>
 246      [a, b] is entirely to the left of [c, d].  That is,
 247      [a, b] &lt;&lt; [c, d] is true if b &lt; c and false otherwise
 248     </para>
 249    </listitem>
 250    <listitem>
 251     <programlisting>
 252 [a, b] &gt;&gt; [c, d]        Is right of
 253     </programlisting>
 254     <para>
 255      [a, b] is entirely to the right of [c, d].  That is,
 256      [a, b] &gt;&gt; [c, d] is true if a &gt; d and false otherwise
 257     </para>
 258    </listitem>
 259    <listitem>
 260     <programlisting>
 261 [a, b] &amp;&lt; [c, d]        Overlaps or is left of
 262     </programlisting>
 263     <para>
 264      This might be better read as <quote>does not extend to right of</quote>.
 265      It is true when b &lt;= d.
 266     </para>
 267    </listitem>
 268    <listitem>
 269     <programlisting>
 270 [a, b] &amp;&gt; [c, d]        Overlaps or is right of
 271     </programlisting>
 272     <para>
 273      This might be better read as <quote>does not extend to left of</quote>.
 274      It is true when a &gt;= c.
 275     </para>
 276    </listitem>
 277    <listitem>
 278     <programlisting>
 279 [a, b] = [c, d]         Same as
 280     </programlisting>
 281     <para>
 282      The segments [a, b] and [c, d] are identical, that is, a = c and b = d
 283     </para>
 284    </listitem>
 285    <listitem>
 286     <programlisting>
 287 [a, b] &amp;&amp; [c, d]        Overlaps
 288     </programlisting>
 289     <para>
 290      The segments [a, b] and [c, d] overlap.
 291     </para>
 292    </listitem>
 293    <listitem>
 294     <programlisting>
 295 [a, b] @&gt; [c, d]        Contains
 296     </programlisting>
 297     <para>
 298      The segment [a, b] contains the segment [c, d], that is,
 299      a &lt;= c and b &gt;= d
 300     </para>
 301    </listitem>
 302    <listitem>
 303     <programlisting>
 304 [a, b] &lt;@ [c, d]        Contained in
 305     </programlisting>
 306     <para>
 307      The segment [a, b] is contained in [c, d], that is,
 308      a &gt;= c and b &lt;= d
 309     </para>
 310    </listitem>
 311   </itemizedlist>
 312
 313   <para>
 314    (Before PostgreSQL 8.2, the containment operators @&gt; and &lt;@ were
 315    respectively called @ and ~.  These names are still available, but are
 316    deprecated and will eventually be retired.  Notice that the old names
 317    are reversed from the convention formerly followed by the core geometric
 318    datatypes!)
 319   </para>
 320
 321   <para>
 322    The standard B-tree operators are also provided, for example
 323
 324   <programlisting>
 325 [a, b] &lt; [c, d]                Less than
 326 [a, b] &gt; [c, d]                Greater than
 327   </programlisting>
 328
 329    These operators do not make a lot of sense for any practical
 330    purpose but sorting. These operators first compare (a) to (c),
 331    and if these are equal, compare (b) to (d). That results in
 332    reasonably good sorting in most cases, which is useful if
 333    you want to use ORDER BY with this type.
 334   </para>
 335  </sect2>
 336
 337  <sect2>
 338   <title>Notes</title>
 339
 340   <para>
 341    For examples of usage, see the regression test <filename>sql/seg.sql</>.
 342   </para>
 343
 344   <para>
 345    The mechanism that converts <literal>(+-)</> to regular ranges
 346    isn't completely accurate in determining the number of significant digits
 347    for the boundaries.  For example, it adds an extra digit to the lower
 348    boundary if the resulting interval includes a power of ten:
 349
 350    <programlisting>
 351 postgres=> select '10(+-)1'::seg as seg;
 352       seg
 353 ---------
 354 9.0 .. 11             -- should be: 9 .. 11
 355    </programlisting>
 356   </para>
 357
 358   <para>
 359    The performance of an R-tree index can largely depend on the initial
 360    order of input values. It may be very helpful to sort the input table
 361    on the <type>seg</> column; see the script <filename>sort-segments.pl</>
 362    for an example.
 363   </para>
 364  </sect2>
 365
 366  <sect2>
 367   <title>Credits</title>
 368
 369   <para>
 370    Original author: Gene Selkov, Jr. <email>selkovjr@mcs.anl.gov</email>,
 371    Mathematics and Computer Science Division, Argonne National Laboratory.
 372   </para>
 373
 374   <para>
 375    My thanks are primarily to Prof. Joe Hellerstein
 376    (<ulink url="http://db.cs.berkeley.edu/~jmh/"></ulink>) for elucidating the
 377    gist of the GiST (<ulink url="http://gist.cs.berkeley.edu/"></ulink>). I am
 378    also grateful to all Postgres developers, present and past, for enabling
 379    myself to create my own world and live undisturbed in it. And I would like
 380    to acknowledge my gratitude to Argonne Lab and to the U.S. Department of
 381    Energy for the years of faithful support of my database research.
 382   </para>
 383
 384  </sect2>
 385
 386 </sect1>