Subject: Data structure in FITS (Was: Re: Thoughts from WGAS...)

From: cflatter at nrao.edu (Chris Flatters)
Date: Fri, 19 Jun 1992 21:56:56 GMT

In article 8132 at nsisrv.gsfc.nasa.gov, warnock at Hypatia.gsfc.nasa.gov (Archie Warnock) writes:
>Second, I'd like to point out the related issue, also raised by Immanuel
>Freedman, that we'd better start thinking about fitting advanced data
>structures into FITS.  If we're going to use FITS as a working format,
>rather than just an interchange format, issues of efficiency become
>important.  We will {\em need} to be able to put things like quadtrees
>and block-stored images into FITS.  We will need to be able to store
>related structures - like keeping palettes with images - and to do so in
>a way which makes explicit the relations.  Just putting a bunch of
>extensions into the same file doesn't do that.

The FITS binary table extension already allows arbitrarily complex
data structures to be stored.  A table defines a data {\it type}. It
is equivalent to a PASCAL record definition or a C struct definition
(or a Fortran 90 TYPE definition).  The columns in the table represent
the components of that type.

Each row in the table represents an {\it instance} of that type.  Each
instance is uniquely identifed by the name of the table it occurs in,
the version number of the table and its row number.  It is therefore
possible to define structures that refer to instances of other
structures by including columns which contain the name and version
number of the table in which the referenced instance occurs and its
row number.

For example suppose that we have a binary tree of integers.  In C
we might declare the following struct to hold tree nodes.

struct TreeNode
    {
    int      value;	/* Value */
    TreeNode *left;     /* Pointer to left subtree or null pointer */
    TreeNode *right;    /* Pointer to right subtree or null pointer */
    };

We could store a binary tree of integers in a single FITS binary table
with the following header.

XTENSION='BINTABLE'
BITPIX  =                     8 / Binary data
NAXIS   =                     2 
NAXIS1  =                    12 / 3 integers at 4 bytes each
NAXIS2  =                     ? / The number of nodes in the tree
PCOUNT  =                     0
GCOUNT  =                     1
TFIELDS =                     3
EXTNAME = 'BTREE   '            / For example
EXTVER  =                     1
TFORM1  = '1J      '
TTYPE1  = 'VALUE           '
TUNIT1  = '        '
TFORM2  = '1J      '
TTYPE2  = 'LEFT SUBTREE    '
TUNIT2  = '        '
TFORM3  = '1J      '
TTYPE3  = 'RIGHT SUBTREE   '
TUNIT3  = '        '
END

In this case all of the node of the tree will be in the same table
so we do not need table fields containing the names and version numbers
of the tables containing the left and right subtrees.

The tree

                   5
                  / \
                 2   9
                / \   \
               7   6   8

could be written using such a table as

Row No. | VALUE | LEFT SUBTREE | RIGHT SUBTREE |
      1 |     5 |            2 |             5 |
      2 |     2 |            3 |             4 |
      3 |     7 |            0 |             0 | 
      4 |     6 |            0 |             0 |
      5 |     9 |            0 |             6 |
      6 |     8 |            0 |             0 |     

	Chris Flatters
	cflatter at nrao.edu

---

From: warnock at Hypatia.gsfc.nasa.gov (Archie Warnock)
Date: 22 Jun 92 14:14:24 GMT

In article <1992Jun19.215656.25564 at nrao.edu>, cflatter at nrao.edu (Chris Flatters) writes:
|> For example suppose that we have a binary tree of integers.  In C
|> we might declare the following struct to hold tree nodes.
|> 
|> struct TreeNode
|>     {
|>     int      value;	/* Value */
|>     TreeNode *left;     /* Pointer to left subtree or null pointer */
|>     TreeNode *right;    /* Pointer to right subtree or null pointer */
|>     };
|> 
|> We could store a binary tree of integers in a single FITS binary table
|> with the following header.
|> 
|> XTENSION='BINTABLE'
|> BITPIX  =                     8 / Binary data
|> NAXIS   =                     2 
|> NAXIS1  =                    12 / 3 integers at 4 bytes each
|> NAXIS2  =                     ? / The number of nodes in the tree
|> PCOUNT  =                     0
|> GCOUNT  =                     1
|> TFIELDS =                     3
|> EXTNAME = 'BTREE   '            / For example
|> EXTVER  =                     1
|> TFORM1  = '1J      '
|> TTYPE1  = 'VALUE           '
|> TUNIT1  = '        '
|> TFORM2  = '1J      '
|> TTYPE2  = 'LEFT SUBTREE    '
|> TUNIT2  = '        '
|> TFORM3  = '1J      '
|> TTYPE3  = 'RIGHT SUBTREE   '
|> TUNIT3  = '        '
|> END

OK, so far I'm with you.  Have we instituted some sort of control
authority to handle the values of EXTNAME so applications can recognize
the data structures there?  Should we?

-- 
----------------------------------------------------------------------------
-- Archie Warnock                   Internet:  warnock at hypatia.gsfc.nasa.gov
-- Hughes STX                       "Unix --- JCL For The 90s"
-- NASA/GSFC

---

From: thompson at stars.gsfc.nasa.gov (William Thompson, code 682.1, x2040)
Date: Mon, 22 Jun 1992 16:07:00 GMT

In article <1992Jun22.141424.3147 at nsisrv.gsfc.nasa.gov>,
warnock at Hypatia.gsfc.nasa.gov (Archie Warnock) writes...

>the data structures there?  Should we?

I believe that this is a misuse of the EXTNAME keyword.  My understanding of
EXTNAME is that it should identify what data is stored in the table, not the
structure used for storing the data.  Certainly, that is how I planned to use
it for storing SOHO/CDS data: the EXTNAME record would contain the unique
identification of the observation, which would then be linked to the master
catalog.

Binary tables have a tremendous capability of extending the way they can be
used.  The above is one example.  Others may wish to follow the relational
model.  At the moment there doesn't seem to be any mechanism for codifying
these subextensions.  At one time, I suggested the additional keyword CONVENTN.

Maybe its just too early to start codifying these conventions.  There are so
many ways that binary tables can be used, that maybe we should wait until we
find out how people want to use binary tables.

Bill Thompson