Constraint Satisfaction in Semantic Data Model Databases

Grant holder: Peter M.D. Gray
Research Fellow: Suzanne M. Embury

The aim of this project is to investigate novel uses of semantic domain information in improving the support given to the users of complex database applications. The main focus is on support for complex updates, by using declaratively stated domain constraints in both a restrictive and a generative fashion. The context of the project is a database of three-dimensional protein structure data, stored in a functional data model database.

The two strands of the project are:

to develop a compiler for an extended version of the Daplex language, which allows the declarative specification of complex updates in terms of the constraints that the update must cause to be satisfied by the resulting database state. The compiler will produce a CHIP program which uses constraint logic programming techniques to search for an update strategy that meets the user's requirements.

to develop a subsystem for automatic transaction repair, in the context of long-duration, design transactions. The subsystem will use constraint logic programming techniques to analyse the information returned by the constraint checking process on transaction commit, and to search for update sequences which will restore consistency. The subsystem is intended to be advisory rather than prescriptive, with the user being the final arbiter of which update strategy is selected.

These two strands work together to solve a problem which is too difficult for either of them to solve individually. Many update problems are too complex for the post-hoc analysis of a repair mechanism - a far better solution is to use the integrity constraint information to help the user to make a semantically valid update in the first place. This is what our declarative update language allows. However, it cannot ensure than integrity is preserved between one complex update and the next. This is where the transaction repair mechanism comes in, since it supports the user in tidying up any inconsistencies that may exist after a sequence of individually valid complex updates.

Examples of our constraint language syntax can be found here and here.

Constraint related publications can be found here.

This project is funded by the EPSRC.

Progress Report for 1994

Our main focus so far has been to stabilise the implementation of the P/FDM database system, and to make the alterations necessary for the addition of the new language features and the transaction repair subsystem. This has included:

the redesign of the Daplex compiler to allow individual modules, such as the optimiser and code generator, to be used in new ways

the underlying storage schemas have been altered and the update primitives rewritten to give better performance under transactions and, as a by-product, better general performance

the syntax of our constraint language has been altered in the light of a study of the constraints present in a complex domain (protein structure), and the constraint compiler has been extended to cover all constraints expressible in the new language

While implementing these changes we have also completed the port of P/FDM to SICStus (which was begun in another project at Aberdeen), with a view to producing an easily-distributable final product.

The implementation of the Daplex-to-Chip compiler is under way. The basic framework is almost complete, and we are beginning to consider compilation strategies for the kinds of constraints found in our application domain.

Future Plans for 1995

The next major steps in the project are to complete the Daplex-to-Chip compiler (and to validate it by experimenting with problems in the protein structure database), and to implement our proposed algorithm for checking constraints on transaction-commit. The algorithm uses partially-instantiated templates in order to reduce the amount of data retrieval required to check a large set of constraints, and produces output in a form suitable for use in transaction repair.

For the remainder of the project, we will explore the combined use of the Daplex-to-Chip compiler and the constraint handling techniques provided by Chip in generating update strategies which will restore consistency to long-duration design transactions, in the context of the protein database.

Progress Report for 1995

The semantics of Angelic Daplex have been formalised, in conjunction with a formal description of the standard Daplex language. A prototype version of the Angelic Daplex compiler (which generates CHIP code) has been built, and integrated with the CHIP system via an RPC mechanism developed for another project at Aberdeen. We hope eventually to achieve a more complete integration using the foreign language interface provided for CHIP, which will be more efficient and make the resulting system less dependent on the Aberdeen setup.

In addition, the P/FDM system has been upgraded to compile with SICStus V.3, to increase the possibilities for distributing the results generated by this project.

The automatic transaction repair subsystem has been designed, and the role of CHIP in the repair process has been made more concrete. The design process high-lighted certain problems with our current approach to constraint checking on transaction commit. This subsystem has been redesigned and is being re-implemented. Once that is complete, the remainder of the project can focus on implementation of the automatic transaction repair system.