Formalisation and Optimisation of Active Databases

Funding and Staffing Details

This project was funded by EPSRC grant GR/L 26872 during the period May 1997 to November 2000. Alex Poulovassilis was the Principal Investigator, and James Bailey and Carol Small (Visiting Fellow) were the co-Investigators. The following people worked as RAs/RFs on the project:

Swarup Reddi (May - June 1997): extending PFL with ECA rules.
James Bailey (Oct 1997 - April 1999): analysis and optimisation techniques for ECA rules.
Wilfried Meyer-Viol (May - Sept 1999): application of ECA rules to Natural Language Parsing.
Pete Newson (Nov 1999 - April 2000): extending PFL with ECA rule analysis and optimisation.
Szabolcs Mikulas (Feb 2000 - Oct 2000): optimisation of event queries.

Project Outline and Aims

In order to handle the demands of new application areas, a greater variety of information needs to be stored in the database explicitly, rather than encoded within numerous applications programs, thus improving the robustness and maintainability of database applications. Examples of such information are deductive rules and event-condition-action (ECA) rules.

This project has been investigating

query optimisation techniques, and
analysis and optimisation techniques for ECA rules

in such enhanced databases. In particular,

we have developed new techniques for analysing the behaviour of ECA rules e.g. properties such as termination and confluence, based on abstract interpretation of rule execution; and
we are investigating a partial evaluation approach to optimising ECA rule execution.

Our testbed for this work has been a prototype functional database system called PFL. One of the applications with respect to which we have evaluated our techniques is natural language parsing of Road Accident reports using an event-condition-action based parsing model.

Please contact Alex Poulovassilis if you would like to install a copy of PFL.

Project publications

Optimising Active Database Rules by Partial Evaluation and Abstract Interpretation. J.Bailey, A.Poulovassilis and S.Courtenage. Tech. Rep. BBKCS-01-02, May 2001, Birkbeck College. Proc. DBPL'01, Rome, September 2001. Springer-Verlag LNCS 2397, pp 300-317.

Parsing Traffic Accident Reports with Dynamic Syntax. W. Meyer-Viol, Technical Report, King's College London, March 2001.

Expressiveness issues and decision problems for active database event queries. J. Bailey and S. Mikulas. Proc. ICDT'01, London, January 2001. Springer-Verlag LNCS 1973, pp 68-82.

A Dynamic Approach to Termination Analysis for Active Database Rules. J.Bailey, A.Poulovassilis and P.Newson. Proc D00D'2000, London, July 2000. Springer-Verlag LNCS 1861, pp 1106-1120.

Analysis and Optimisation of Active Database Rules Using Abstract Interpretation and Partial Evaluation. J.Bailey and A.Poulovassilis, Tech. Rep. 27/09/99, Birkbeck College and King's College London.

An Abstract Interpretation Framework for Termination Analysis of Active Rules. J.Bailey and A.Poulovassilis. Proc DBPL'99, Kinloch-Rannoch, September 1999. Springer-Verlag LNCS 1949, pp 252-270.

Abstract Interpretation for Termination Analysis in Functional Active Databases. J.Bailey and A.Poulovassilis, Journal of Intelligent Information Systems, 12 (2/3), pp 243-273, 1999.

PFL: an active, functional DBPL (abstract). S.Reddi, A.Poulovassilis and C.Small. In "Active Rules in Database Systems", ed. Norman Paton, Springer-Verlag, 1999.

Decidability and undecidability results for the termination problem of active database rules. J. Bailey, G. Dong and K. Ramamohanarao. Proc PODS'98, Seattle, Washington, 1998, pp 264-273.

Formal foundations for optimising aggregation functions in Database Programming Languages. A.Poulovassilis and C.Small. Proc DBPL'97, Denver, August 1997. Springer-Verlag LNCS 1369, pp 299-318.