Using relational discrete event systems and models for prediction of future behavior of databases

Candidate: Tuzhilin,Alexander Sergei

Abstract

The following prediction problem is studied in this dissertation: given a specification of the future behavior of a system and the current state of the system described with a relational database, predict what will happen to the system in the future. The behavior is defined in terms of Relational Discrete Event Systems (RDESes) and Models (RDEMs). An RDES is a set of possible non-deterministic trajectories of future states of a system. An RDEM is a finite formal description of a generally infinite RDES set. Various production system RDEMs and a recurrence equation RDEM are defined and formally compared in terms of expressive power in this dissertation. It is shown that one of the production system RDEMs is better than other considered RDEMs not only in terms of expressive power but in other respects as well. Also, the suitability of various control strategies to restrict non-determinism and improve system's performance is considered. In order to obtain predictions about possible future states of a database, Predictive Query Language (PQL) is defined with the syntax based on a predicate temporal logic and the semantics on RDEM models. It is shown how PQL is related to relational queries for Datalog and its extensions. Finally, the prototype of the Cassandra system is described. Cassandra supports PQL with the semantics based on a production system RDEM. An example of a small Flexible Manufacturing System is used throughout the dissertation to illustrate various points about the described methods.