A Syntactic Method for Enforcing Semantic Database Integrity Constraints

Abstract

An automata theoretic framework is proposed which allows for a syntactic treatment of semantic properties of relational databases.The semantic integrity of a database is defined in terms of predicates on its attributes. These predicates are shown to determine the specification of a finite state automata which detects, in time proportional to the length of the input, whether the semantic integrity of the database has been violated. In addition, this approach leads to efficient techniques for dealing with the problems of consistency, equivalence and redundancy of integrity constraints. These concepts are defined and algorithms for their determination are described.