DBIO (Nov84) Database I/O Design DBIO (Nov84) IRAF DATABASE I/O Doug Tody November 1984 1. INTRODUCTION The IRAF database i/o package (DBIO) is a library of SPP callable procedures used to create, modify, and access IRAF database files. All access to these database files shall be indirectly or directly via the DBIO interface. DBIO shall be implemented using IRAF file i/o and memory management facilities, hence the package will be compact and portable. The separate CL level package DBMS shall be provided for interactive database access and for procedural access to the database from within CL scripts. The DBMS tasks will access the database via DBIO. Virtually all runtime IRAF datafiles not maintained in text form shall be maintained under DBIO, hence it is essential that the interface be both efficient and compact. In particular, bulk data (images) and large catalogs shall be maintained under DBIO. The requirement for flexibility in defining and accessing IRAF image headers necessitates quite a sophisticated interface. Catalog storage is required primarily for module intercommunication and output of the results of the larger IRAF applications packages, but will also be useful for accessing astronomical catalogs prepared outside IRAF (e.g., the SAO star catalog). In short, virtually all IRAF applications packages are expected to make use of DBIO; many will depend upon it heavily. The relationship of the DBIO and DBMS packages to each other and to the related standard IRAF interfaces is shown in Figure 1.1. DBMS DBIO FIO MEMIO (kernel) (datafiles) (cl) | (vos) | (host) Fig 1.1 Major Interfaces While images will be maintained under DBIO, access to the pixels will continue to be provided by the IMIO interface. IMIO is a higher level interface which will use DBIO to maintain the image header. Pixel -1- DBIO (Nov84) Database I/O Design DBIO (Nov84) storage will be either in a separate pixel storage file or in the database file itself (as a one dimensional array), depending on the size of the image. A system defined thresold value will determine which type of storage is used. The relationship of IMIO to DBIO is shown in Figure 1.2. IMAGES IMIO DBIO FIO MEMIO (cl) | (vos) Fig 1.2 Relationship of Database and Image I/O 2. REQUIREMENTS The requirements for the DBIO interface are driven by its intended usage for image and catalog storage. It is arguable whether the same interface should be used for both types of data, but development of an interface such as DBIO with all the associated DBMS utilities is expensive, hence we would prefer to have to develop only one such interface. Furthermore, it is desirable for the user to only have to learn one such interface. The primary functional and performance requirements which DBIO must meet are the following (in no particular order). [1] DBIO shall provide a high degree of data independence, i.e., a program shall be able to access a data structure maintained under DBIO without detailed knowledge of its contents. [2] A DBIO datafile shall be self describing and self contained, i.e., it shall be possible to examine the structure and contents of a DBIO datafile without prior knowledge of its structure or contents. [3] DBIO shall be able to deal efficiently with records containing up to N fields and with data groups containing up to M records, where N and M are at least sysgen configurable and are order of magnitude N=10**2 and M=10**6. [4] The time required to access an image header under DBIO must be comparable to the time currently required for the equivalent operation under IMIO. -2- DBIO (Nov84) Database I/O Design DBIO (Nov84) [5] It shall be possible for an image header maintained under DBIO to contain application or user defined fields in addition to the standard fields required by IMIO. [6] It shall be possible to dynamically add new fields to an existing image header (or to any DBIO record). [7] It shall be possible to group similar records together in the database and to perform global operations upon all or part of the records in a group. [8] It shall be possible for a field of a record to be a one-dimensional array of any of the primitive types. [9] Variant records (records containing variable size fields) shall be supported, ideally without penalizing efficient access to databases which do not contain such records. [A] It shall be possible to copy a record without knowledge of its contents. [B] It shall be possible to merge (join) two records containing disjoint sets of fields. [C] It shall be possible to update a record in place. [D] It shall be possible to simultaneously access (retrieve, update, or insert) multiple records from the same data group. To summarize, the primary requirements are data independence, efficient access to both large and small databases, and flexibility in the contents of the database. 3. CONCEPTUAL DESIGN The DBIO database faciltities shall be based upon the relational model. The relational model is preferred due to its simplicity (to the user) and due to the demonstrable fact that relational databases can efficiently handle large amounts of data. In the relational model the database appears to be nothing more than a set of TABLES, with no builtin connections between separate tables. The operations defined upon these tables are based upon the relational algebra, which is in turn based upon set theory. The major advantages claimed for relational databases are the simplicity of the concept of a database as a collection of tables, and the predictability of the relational operators due to their being based on a formal theoretical model. None of the requirements listed in section 2 state that DBIO must implement a relational database. Most of our needs can be met by structuring our data according to the relational data model (i.e., as -3- DBIO (Nov84) Database I/O Design DBIO (Nov84) tables), and providing a good SELECT operator for retrieving records from the database. If a semirelational database is sufficient to meet our requirements then most likely that is what will be built (at least initially; the relational operators are very attractive for data analysis). DBIO is not expected to be competitive with any commercial relational database; to try to make it so would probably compromise the requirement that the interface be compact. On the other hand, the database requirements of IRAF are similar enough to those addressed by commercial databases that we would be foolish not to try to make use of some of the same technology. FORMAL RELATIONAL TERM INFORMAL EQUIVALENTS relation table tuple record, row attribute field, column domain datatype primary key record id A DBIO DATABASE shall consist of one or more RELATIONS (tables). Each relation shall contain zero or more RECORDS (rows of the table). Each record shall contain one or more FIELDS (columns of the table). All records in a relation shall share the same set of fields, but all of the fields in a record need not have been assigned values. When a new ATTRIBUTE (column) is added to an existing relation a default valued field is added to each current and future record in the relation. Each attribute is defined upon a particular DOMAIN, e.g., the set of all nonnegative integer values less than or equal to 100. It shall be possible to specify minimum and maximum values for integer and real attributes and to enumerate the permissible values of a string type attribute. It shall be possible to specify a default value for an attribute. If no default value is given INDEF is assumed. One dimensional arrays shall be supported as attribute types; these will be treated as atomic datatypes by the relational operators. Array valued attributes shall be either fixed in size (the most efficient form) or variant. There need be no special character string datatype since one dimensional arrays of type character are supported. Each relation shall be implemented as a separate file. If the relations comprising a database are stored in a directory then the directory can be thought of as the database. Public databases will be stored in well known public (write protected) directories, private databases in user directories. The logical directory name of each public database will be the name of the database. Physical storage for a database need not necessarily be allocated locally, i.e., a database may be centrally located and remotely accessed if the host computer is part of a local area network. Locking shall be at the level of entire relations rather than at the record level, at least in the initial implementation. There shall be -4- DBIO (Nov84) Database I/O Design DBIO (Nov84) no support for indices in the initial implementation except possibly for the primary key. It should be possible to add either or both of these features to a future implementation without changing the basic DBIO interface. Modifications to the internal data structures used in database files will likely be necessary when adding such a major feature, making a save and restore operation necessary for each database file to convert it to the new format. The save format chosen (e.g. FITS table) should be independent of the internal format used at a particular time on a particular host machine. Images shall be stored in the database as individual records. All image records shall share a common subset of attributes. Related images (image records) may be grouped together to form relations. The IRAF image operators shall support operations upon relations (sets of images) much as the IRAF file operators support operations upon sets of files. A unary image operator shall take as input a relation (set of one or more images), inserting the processed images into the output relation. A binary image operator shall take as input either two relations or a relation and a record, inserting the processed images into the output relation. In all cases the output relation can be an input relation as well. The input relation will be defined either by a list or by selection using a theta-join (operationally similar to a filename template). 3.1 RELATIONAL OPERATORS DBIO shall support two basic types of database operations: operations upon relations and operations upon records. The basic relational operators are the following. All of these operators produce as output a new relation. create Create a new base relation (physical relation as stored on disk) by specifying an initial set of attributes and the (file)name for the new relation. Attributes and domains may be specified via a data definition file or by reference to an existing relation. A primary key (limited to a single attribute) should be identified. The new relation initially contains no records. drop Delete a (possibly nonempty) base relation and any associated indices. alter Add a new attribute or attributes to an existing base relation. Attributes may be specified explicitly or by reference to another relation. -5- DBIO (Nov84) Database I/O Design DBIO (Nov84) select Create a new relation by selecting records from one or more existing base relations. Input consists of an algebraic expression defining the output relation in terms of the input relations (usage will be similar to filename templates). The output relation need not have the same set of attributes as the input relations. The SELECT operator shall ultimately implement all the basic operations of the relational algebra, i.e., select, project, join, and the set operations. At a minimum, selection and projection are required in the initial interface. The output of SELECT is not a named relation (base relation), but is instead intended to be accessed by the record level operators discussed in the next section. edit Edit a relation. An interactive screen editor is entered allowing the user to add, delete, or modify tuples (not required in the initial version of the interface). Field values are verified upon input. sort Make the storage order of the records in a relation agree with the order defined by the primary key (the index associated with the primary key is always sorted but index order need not agree with storage order). In general, retrieval on a sorted relation is more efficient than on an unsorted relation. Sorting also eliminates deadspace left by record deletion or by updates involving variant records. Additional nonalgebraic operators are required for examining the structure and contents of relations, returning the number of records or attributes in a relation, and determining whether a given relation exists. The SELECT operator is the primary user interface to DBIO. Since most of the relational power of DBIO is bound up in the SELECT operator and since SELECT will be driven by an algebraic expression (character string) there is considerable scope for future enhancement of DBIO without affecting existing code. 3.2 RECORD (TUPLE) LEVEL OPERATORS While the user should see primarily operations on entire relations, record level processing is necessary at the program level to permit data entry and implementation of special operators. The basic record level operators are the following. -6- DBIO (Nov84) Database I/O Design DBIO (Nov84) retrieve Retrieve the next record from the relation defined by SELECT. While the tuples in a relation theoretically form an unordered set, tuples will normally be returned in either storage order or in the sort order of the primary key. Although all fields of a retrieved record are accessible, an application will typically have knowledge of only a few fields. update Rewrite the (possibly modified) current record. The updated record is written back into the base table from which it was read. Not all records produced by SELECT can be updated. insert Insert a new record into an output relation. The output relation may be an input relation as well. Records added to an output relation which is also an input relation do not become candidates for selection until another SELECT occurs. A retrieve followed by an insert copies a record without knowledge of its contents. A retrieve followed by modification of selected fields followed by an insert copies all unmodified fields of the record. The attributes of the input and output relations need not match; unmatched output attributes take on their default values and unmatched input attributes are discarded. INSERT returns a pointer to the output record, allowing insertions of null records to be followed by initialization of the fields of the new record. delete Delete the current record. Additional operators are required to close or open a relation for record level access and to count the number of records in a relation. 3.2.1 CONSTRUCTING SPECIAL RELATIONAL OPERATORS The record level operations may be combined with SELECT in compiled programs to implement arbitrary operations upon entire relations. The basic scenario is as follows: [1] The set of records to be operated upon, defined by the SELECT operator, is opened as an unordered set (list) of records to be processed. [2] The "next" record in the relation is accessed with RETRIEVE. -7- DBIO (Nov84) Database I/O Design DBIO (Nov84) [3] The application reads or modifies a subset of the fields of the record, updating modified records or inserting the record in the output relation. [4] Steps [2] and [3] are repeated until the entire relation has been processed. Examples of such operators are conversion to and from DBIO and LIST file formats, column extraction, mimimum or maximum of an attribute (domain algebra), and all of the DBMS and IMAGES operators. 3.3 FIELD (ATTRIBUTE) LEVEL OPERATORS Substantial processing of the contents of a database is possible without ever accessing the individual fields of a record. If field level access is required the record must first be retrieved or inserted. Field level access requires knowledge of the names of the attributes of the parent relation, but not their exact datatypes. Automatic type conversion occurs when field values are queried or set. get Get the value of the named scalar or vector field (typed). put Put the value of the named scalar or vector field (typed). read Read the named fields into an SPP data structure, given the name, datatype, and length (if vector) of each field in the output structure. There must be an attribute in the parent relation for each field in the output structure. write Copy an SPP data structure into the named fields of a record, given the name, datatype, and length (if vector) of each field in the input structure. There must be an attribute in the parent relation for each field in the input structure. access Determine whether a relation has the named attribute. 3.4 STORAGE STRUCTURES The DBIO storage structures are the data structures used by DBIO to maintain relations in physical storage. The primary design goals are simplicity and efficiency in time and space. Most actual relations are expected to fall into three classes: -8- DBIO (Nov84) Database I/O Design DBIO (Nov84) [1] Relations containing only a single record, e.g., an image stored alone in a relation. [2] Relations containing several dozen or several hundred records, e.g., a collection of spectra from an observing run. [3] Large relations containing 10**5 or 10**6 records, e.g., the output of an analysis program or an astronomical catalog. Updates and insertions are generally random access operations; retrieval based on the values of several attributes requires efficient sequential access. Efficient random access for relations [2] and [3] requires use of an index. Efficient sequential access requires that records be accessible in storage order without reference to the index, i.e., that records be chained in storage order. Efficient field access where a record contains several dozen attributes requires something better than a linear search over the attribute list. The use of an index shall be limited initially to a single index for the primary key. The primary key will be restricted to a single attribute, with the application defining the attribute to be used (in practice few attributes are usable as keys). The index will be a standard B+ tree, with one exception: the root block of the tree will be maintained in dedicated storage in the datafile. If and only if a relation grows so large that it overflows the root block will a separate index file be allocated for the index. This will eliminate most of the overhead associated with the index for small relations. Efficient sequential access will be provided in either of two ways: via the index in index order or via the records themselves in storage order, depending on the operation being performed. If an external index is used the leaves will be chained to permit efficient sequential access in index order. If the relation also happens to be sorted in index order then this mode of access will be very efficient. Link information will also be stored directly in the records to permit efficient sequential access when it is not necessary or possible to use the index. Assuming that there is at most one index associated with a relation, at most two files will be required to implement the relation. The relation itself will have the file extension ".db". The index file, if any, will have the extension ".dbi". The root name of both files will be the name of the relation. The datafile header structure will probably have to be maintained in binary if we are to keep the overhead of datafile access to acceptable levels for small relations. Careful design of the basic header structure should make most future refinements to the header possible without modification of existing databases. The revision number of DBIO used to create the datafile will be saved in the header to make at least detection of obsolete headers possible. -9- DBIO (Nov84) Database I/O Design DBIO (Nov84) 3.4.1 STRUCTURE OF A BINARY RELATION Putting all this together we come up with the following structure for a binary relation: BOF relation header -+ magic | dbio revision number | creation date | relation name | number of attributes |- fixed size header primary key | record size | domain list | attribute list | miscellaneous | string buffer | root block of index -+ record 1 physical record length (offset to next record) logical record length (implies number of attributes set) field storage record 2 ... record N EOF Vector valued fields with a fixed upper size will be stored directly in the record, prefixed by the length of the actual vector (which may vary from record to record). Storage for variant fields will be allocated outside the record, placing only a pointer to the data vector and byte count in the record itself. Variant records are thus reduced to fixed size records, simplifying record access and making sequential access more efficient. Records will change size only when a new attribute is added to an existing relation, followed by assignment into a record written when there were fewer attributes. If the new record will not fit into the physical slot already allocated, the record is written at EOF and the original record is deleted. Deletion of a record is achieved by setting the logical record length to zero. Storage is not reclaimed until a sort occurs, hence recovery of deleted records is possible. To minimize buffer space and memory to memory copies when accessing a relation it is desirable to work directly out of the FIO buffers. To make this possible records will not be permitted to straddle logical block boundaries. A file block will typically contain several records followed by a gap. The gap may be used to accomodate record expansion without moving a record to EOF. The size of a file block is fixed when -10- DBIO (Nov84) Database I/O Design DBIO (Nov84) the relation is created. 3.4.2 THE ATTRIBUTE LIST Efficient lookup of attribute names suggests maintenance of a hash table in the datafile header. There will be a fixed upper limit on the number of attributes permitted in a single relation (but not on the number of records). Placing an upper limit on the number of attributes simplifies the software considerably and permits use of a fixed size header, making it possible to read or update the entire header in one disk access. There will also be an upper limit on the number of domains, but the domain list is not searched very often hence a linear search will do. All information about the decomposition of a record into fields, other than the logical length of vector valued fields, is given by the attribute list. Records contain only data with no embedded structural information other than the length of the vector fields. New attributes are added to a relation by appending to the attribute list. Existing records are not affected. By comparing the logical length of a record to the offset for a particular field we can tell whether storage has been allocated for that field in the record. Domains are used to limit the range of values a field can take on in an assignment, and to flag attribute comparisons which are likely to be erroneous (e.g. order comparison of a pixel coordinate and a wavelength). The domains "bool", "char", "short", etc. are predefined. The following information must be stored for each user defined domain: name may be same as attribute name datatype bool, char, short, etc. physical vector length 0=variant, 1=scalar, N=vector default default value, INDEF if not given minimum mimimum value (ints and reals) maximum maximum value (ints and reals) enumval enumerated values (strings) The following information is required to describe each attribute. The attribute list is maintained separately from the hash table of attribute names and can be used to regenerate the hash table of attribute names if necessary. name no embedded whitespace domain index into domain table offset offset in record -11- DBIO (Nov84) Database I/O Design DBIO (Nov84) All strings will will be stored in a fixed size string buffer in the header area; it is the index of the string which is stored in the domain and attribute lists. This eliminates the need to place an upper limit on the size of domain names and enumerated value lists and makes it possible for a single attribute name string to be referenced in both the attribute list and the attribute hash table. 4. SPECIFICATIONS