Query optimization by using knowledge about data semantics

In this paper we address the problem of query optimization by using semantic properties of data. The discussion is in terms of the relational data model. We present some rules for Relational Algebra (RA) queries that can be used to transform a query into an equivalent one which is more efficient to process, and provide a formal proof of their correctness, such rules, called semantic rules, allow to eliminate joins, to introduce clustering indexes and to test for query emptiness according to the database properties stated by a set of integrity constraints. The correctness of these rules is formally proved by Showing that the obtained queries define exactly the same set of tuples as the original query. We also investigate the problem of using semantic rules within transactions, where any arbitrary sequence, or queries and modify operations may occur and semantic integrity can be violated during intermediate steps of processing. Conditions are provided under which the semantic rules presented in this paper can be correctly applied within compiled transactions.