Supporting Lists in a Data Model (A Timely Approach)
Joel E. Richardson · 1992
This paper considers the problem of adding list as a type constructor to an object-oriented data model. In particular, we are concerned with how lists in a database can be constructed and how they can be queried. We propose that operators from a discrete, linear-time temporal logic provide a natural basis for making assertions about the ordering of elements in a list. We then show how such assertions may be incor-porated into a query algebra by extending the Melam-pus Data Model (MDM) with a list type constructor and by allowing temporal assertions as predicates on lists. The extended algebra allows the expression of a significantly larger class of queries than previously possible. Furthermore, temporal operators provide a basis for creating new lists that satisfy desired order-ing properties. For example, sorting is shown to fall out as a special case. This paper also describes a new framework based on Boolean circuits for evaluating the truth of an assertion on a given list. This framework provides many opportunities for optimization and par-allelism, and it lends insight to the meaning and com-plexity of a temporal formula.