Database Design   «Prev

# SQL Relationally Complete and Semantically Equivalent Expressions

Question: What is a semantically equivalent expression?
A semantically equivalent expression refers to two or more expressions that, although they may have different syntactical structures or representations, ultimately convey the same meaning or produce the same result when evaluated. In the context of databases and programming languages, semantically equivalent expressions may be used to achieve the same outcome, but with different syntax, algorithms, or query structures.
For example, let's consider the following two SQL queries:
Query 1:
```SELECT name, age
FROM users
WHERE age >= 18;
```

Query 2:
```SELECT name, age
FROM users
WHERE NOT (age < 18);
```

Both queries have different syntactical structures (one uses >=, and the other uses NOT and <), but they are semantically equivalent because they both retrieve the same set of records - users who are 18 years old or older. Semantically equivalent expressions can be found in various contexts:
1. Mathematical expressions: Two mathematical expressions that simplify to the same result are semantically equivalent. For example, 2 + 3 and 5 are semantically equivalent, as they both represent the same value.
2. Logical expressions: Two logical expressions that evaluate to the same truth values under the same conditions are semantically equivalent. For example, A AND B and NOT (NOT A OR NOT B) are semantically equivalent, as they both represent the same logical operation.
3. Programming constructs: Two pieces of code that produce the same output or side effects when executed are semantically equivalent. For example, a for loop and a while loop that achieve the same iteration can be considered semantically equivalent.

In database query optimization, identifying semantically equivalent expressions can be useful for generating alternative, more efficient query plans that produce the same result. Similarly, in programming languages, semantically equivalent expressions can be used to refactor code for improved readability, performance, or maintainability.
Note: To prove that SQL is relationally complete, you need to show that for every expression of the relational algebra, there exists a semantically equivalent expression in SQL.