Semantic Equivalence

In a spoken language it is possible to create different statements, that have the same meaning. This is called semantic equivalence of statements. Similarly, in your query language, it may be possible to specify the same action by different statements. These statements can be said to be semantically equivalent

  1. If they are deterministic i.e. one statement gives same result every time it is executed on the same data.
  2. All the statements have different syntax, but all give the same result.

semantic-equvalence

It may be evident that some queries may give better performance than others. A database should ideally be able to identify the semantically equivalent queries for a given query. This helps in finding out a better performing alternative to user submitted query. This has been implemented in almost all the commercial databases.

A set of transformation rules can be defined to create semantically equivalent queries. Some such transformations are joins-subquery, distinct-groupby transformation.