Partial-order databases
W. M. Tompa, Darrell R. Raymond · 1996
Order is a fundamental property of information that is not explicitly captured in model database models. The partial order model introduces the idea of partially ordered sets as the basic construct for modelling data. This model exhibits two novel properties. First, it is capable of describing structure without reference to data types. Second, it inherently separates the structure of data from the objects being structured. These two properties mean that the model naturally facilitates the use of multiple structures for data. We investigate a collection of algebraic operators for manipulating ordered sets. An implementation of these operators is presented, based on the use of realizers as a data structure. An algorithm is provided for generating realizers for arbitrary finite partial orders. The partial order model is useful for data domains that involve containment or dependency relationships. Text databases and software repositories are two examples of such domains. We show how the partial order model can be used to structure text and software data, and how it provides new insights in both areas. In particular, partial orders can be the foundation of better systems for handling both tables and makefiles. Partial orders are prominent not only for data stored in databases, but for database system internals as well. Partial orders play key roles in dependency theory, object-oriented modelling, and the management of redundant data. Thus partial orders are a concept of broad importance both in understanding and implementing the fundamentals of almost any database system.