A.V. Malikov, A.A. Evdokimov, D.K. Parkhomenko

Data integrity is a crucial property of database systems. Relational theory assumes that records within a single relation are independent and integrity check procedures deal with domain values and references between records of different relations. Yet in many cases data in a relation can be considered integral only if each subset of records remains in a semantically correct (from an application domain-s standpoint) state assuming that each record is also correct and conformant to the application domain. Such cases emerge when application domain rules define an order relation on a set of records of a particular database table. Temporal and hierarchical data can be considered an example. The focus of this paper is to utilize the concept of a finite state machine to check for semantic integrity of a subset of records in a relational table. Semantic integrity rules of a certain relation can be represented as state-transition function of the state machine, where a subset of records in the table along with records being added serves as a sequence of inputs. If machine accepts this sequence (finishes at some accepting state) then data integrity check is considered successful. Implementation of a state machine implies putting its state-transition graph in some form of a relational structure. First suggested approach utilizes «parent-child» schema where possible transitions of adjacent states are stored as pairs of state identifiers in the state machine table. This schema is considered versatile as it allows complex graphs with loops to be implemented. Input sequence of the state machine is consequently analyzed, checking if a certain state transition exists. Another approach makes use of a «materialized path» concept where state-transition paths are stored as string keys comprised of sequences of state identifiers. Input sequence of the state machine is converted to a key and is compared to the keys already stored in the state machine table. Both methods are provided with detailed description, database schemas, use cases, and performance considerations.