The Logic of Interacting Levels in Database Schemata

B.N. Rossiter

Database design is concerned with the construction of symbolic models of real world data and embedding in the symbolism the logical structure to be found within the data.

To make application programs independent of the physical representation of the symbolism a conceptual schema must be defined as a global logical definition. This schema relates to the physical definition by a series of mappings from the logical level to the physical address space. The power of databases is to operate across many levels coherently from the conceptual schema right across to the bit address on the physical storage medium.

Each user may have their own, possibly restricted view (external schema) of the database, achieved by a series of mappings providing security, logical data independence, etc. Data structures and data manipulation are controlled by a data model of which the classical types like the hierarchical, network and relational are based on set theory.

At the time database theory was developing[2], it was necessary to customise notation from set theory to represent transformations of common data structures at an abstract level. An example of a common database problem in operating across levels is in handling intension and extension. Set-theoretic methods to specify and distinguish these lack a natural expression of multi-level involvement. In the relational model the extension is normally viewed as a set of tuples and the intension as a set of attributes. The first with order the second independent of order.

The concept of order is not a primitive in the set-theoretic approach. Thus to characterize the order of membership in a tuple it is necessary to ascend to the double power set. This difficulty can be shown with an example using the set theory specification language Z.

Category theory on the other hand, by combining geometry with the algebra, provides an enhanced form of symbolism for multi-level logical structures[1]. Thus intension and extension can be better specified and distinguished as contravariant and covariant functors respectively. Likewise the ordering across levels is more explicit in the categorial representation of naturalism in the adjointness of poset monoids.

[1] Nelson, D A, & Rossiter, B N, Prototyping a Categorical Database in P/FDM. Proceedings of the Second International Workshop on Advances in Databases and Information Systems (AD-BIS’95), Moscow, 27-30 June 1995, Springer-Verlag Workshops in Computing, edd. J. Eder and L.A. Kalinichenko, ISBN 3-540-76014-8, 432-456 (1996).

[2] J.D.Ullman, Principles of Database and Knowledge-base Systems, 1 (1988).

Address: Computing Science, Newcastle University, Newcastle NE1 7RU, UK

E-mail: B.N.Rossiter@ncl.ac.uk