Dr. Andrew Broad
Computer Science
MPhil Project
MPhil Thesis

Here is my MPhil thesis, available for downloading as gzipped (use gunzip or WinAce) PostScript files.

PostScript files can be viewed using Ghostscript and GSview.

The Application of Case-Based Reasoning to the Understanding of Constraints on Information Models

This thesis explores a case-based reasoning approach to understanding the constraints on information models, in particular those written in the information modelling language EXPRESS. In the context of this thesis, a constraint on a model is any condition (explicit or implicit) that must not be violated by a data repository which conforms to that model.

The underlying motivation for this research is the need to understand the comparative semantics of the constraints on two models of the same domain, for tasks such as schema-to-schema mapping (automatically generating a program to map instances from one data repository to another). This comparative understanding of constraints would enable a system to see to what extent the constraints on one model are respected by another model (e.g. in the case of schema-to-schema mapping, whether mapping valid instances from the source model could violate constraints on the target model).

This thesis presents a method for understanding the constraints on a given EXPRESS model. This understanding is realised by extracting from the model higher-level knowledge about the constraints. This knowledge is represented as higher-level constraints: constraints which are at a higher level of abstraction than the model itself, making explicit their implicit semantics. In the case-based reasoning approach to understanding the constraints on a model, cases that match particular fragments of the model are used to suggest higher-level constraints to extract.

Although the current system only considers one model in isolation, this work will provide a useful building block for future systems which are concerned with the comparative semantics of the constraints on two models. The particular way in which the constraints are understood is driven by the purpose of this comparative understanding: the (manual) process of identifying higher-level constraints entails a comparative investigation of models that have semantically equivalent constraints which are expressed in different ways.

An experimental constraint-understanding system has been implemented, which is capable of extracting higher-level constraints from valid EXPRESS models.

Title page

Contents

List of Figures

Abstract

Declaration

Copyright Notice (must be included in every copy of the thesis)

Acknowledgements

Preface

Part I: Background

Chapter 1: Introduction

Chapter 2: Code Understanding and Generation

Chapter 3: Case-Based Reasoning

Part II: A System for Understanding Constraints

Chapter 4: Architecture of the System

Chapter 5: The Frame System

Chapter 6: The Frames in the Constraint-Understanding System

Chapter 7: Results and Conclusions

References

Appendix A: Frame Class Models

Appendix B: An Ontology of Higher-Level Constraints

Appendix C: The Case Library

Appendix D: Algorithmic Details

Appendix E: Implementation

Appendix F: Example Run

Appendix G: Future Work