1. The structure of the data base

As mentioned above, sd-records (or, records, for short) form the informational units of the data base and contain, e.g., problem descriptions, examples, references to the literature etc. Similar records share a common structure and are grouped into tables. Each sd-record must have a Type tag whose value specifies the table the record belongs to and a Key tag which uniquely identifies the record within its table.

There are two basic kinds of tables: data tables and meta tables. Data tables are used to actually store the collected data whereas meta tables are used to specify and define the syntax and semantics of the tags of data tables. More precisely, for each known tag of a particular data table, there is a sd-record in the corresponding meta table which specifies a set of attributes of the considered tag. They define a ``data structure'' in an object-oriented sense.

Since we store the meta information about data tables again in the form of sd-records we can use the same tools to retrieve and manipulate both, data and specifications. Even more importantly, such an approach allows flexible, modular, and independent extension and modification of the structure of the data base, like adding a new data table type for a different kind of application, since the meta information is a part of the data base, and not explicitly fixed in the tools of SYMBOLICDATA.

Tag attributes need to specify

• the type of the tag which determines the syntax of its value,
• a level of the tag which determines its importance ( level==1 characterizes mandatory tags),
• and a description of the meaning/purpose of the tag.

Further attributes may specify the name of a (Perl) procedure that semantically validates (e.g., verifying that polynomials are in normal form) or even generates (e.g., determines the number of variables occurring in a polynomial) the value of the tag, or defines how the tag value has to be transformed into a different format (e.g., how polynomials are represented in HTML).

The type concept for tag values we have developed can loosely be described as follows:

1. It defines (mostly by means of regular expressions) a set of basic tag types, e.g., Text, Integer, Float, URL, Ref (for references to records in other tables), Polynomial, BibTeXEntry, etc. These basic tag type specifications are again stored in form of meta sd-records which allows dynamic type extensions by simply adding a new sd-record specifying a new basic tag type.
2. It defines how lists and hashes can recursively be constructed from basic types. To have a list constructor is necessary to express such concept as ``list of (lists of) polynomials''. A hash constructor, which constructs sets of key/value pairs from the underlying type, is necessary to express, e.g., one-to-many or many-to-one relations between records and tags.

Requiring that each tag value is of a certain type has the advantage that many operations, like syntactic validation, HTML or SQL conversion, etc., on tag values can be realized in a generic, ``content independent'' way.

Interrelations between different tables are specified by means of the type Ref. A tag value of type Ref (or, reference, for short) is a hash of key/comment pairs where `key' is the name of a record, or even a regular expression matching several records, in the foreign table and `comment' is any text. The name of the foreign table is either specified in the tag's meta sd-file or inherited from the tag name, if it coincides with a valid table name. Interrelations are used to attach to a record, for example, bibliography entries (from the BIB table), problem descriptions (from the PROBLEMS table) etc.

Each meta table contains a special sd-record (whose Key is Meta) with ``class attributes'', i.e., information that specifies properties of the entire data table. This may be a description of the purpose of this data table, names of (Perl) modules required for processing records of this table, specifications of procedures which compare two records of this table, etc.

All sd-files are stored in a directory hierarchy, where the string concatenation of the Type and Key of a record yields the location of its sd-file within the directory hierarchy of the data base. A further sub-classification of the records of a table can be realized by means of the directory delimiter `` /'' in their Key values.