Physical design and query compilation for a semantic data model (assuming memory residence)
Grant Weddell · 1987
In this thesis, we consider some of the problems of physical design for the more recently proposed data models. These newer models, called semantic data models, adopt concepts developed by artificial intelligence researchers investigating the general problem of knowledge representation. Our results apply to a particular choice of model, called LDM, that is also developed in the thesis. LDM incorporates the most common features of other semantic data models including a capability for a generalization hierarchy that supports multiple inheritance, support for many-valued properties and a non-procedural query language. This has the advantage that implementors of these other models can then apply our techniques for physical design to solve similar implementation problems. The performance issues we address are based on the assumption that all encoding of information is memory resident. With this assumption, some problems, such as the choice of representation for entities and simple property values, become important issues. Other issues relating to access strategies for implementing queries or to the choice of index types and their selection, are fundamentally changed. The assumption also permits us to ignore clustering problems (problems concerning the judicious placement of data in order to reduce retrieval overhead), since they then have much less relative significance to overall performance. The problems that are considered include: finding representations of entities and single valued properties, selecting a set of indices to support access to groups of entities occurring as class extensions or as values of many-valued properties, mapping transactions to forms that automatically maintain indices, and compiling queries.