How to show that something increases relational expressive power?

Question

How do I show that something increases relational expressive power? For example I have been given a problem in which I need to show whether adding some certain functionality to the select-project-join queries of SQL increases the expressive power. Do I give an example and show that it is not expressible?

Answer 1

First you must decide what is that is being expressed by two notations. (Ie what it is that they are expressing, ie are expressive of, ie are denoting.) Otherwise, the problem doesn't make much sense.

Eg: As long as two notations' sets of expressions are countably infinite they can be set in 1:1 correspondence. So anything that one set's expressions can express the corresponding expression from the other set can be assigned to express. So they are in this trivial sense equally expressive. (Which sense is, essentially, equally expressive of each other's expressions.)

In being told what our two notations are expressing we are generally given for each:

• some primitive expressions
• some rules for generating expressions
• some primitive things
• some rules for generating things
• a mapping from expressions to things

Sometimes the mapping is from terminal expressions to primitive things and from non-terminal expressions to structured things, but it doesn't have to be like that.

To show that one notation is more expressive (of whatever they are expressing) is to show that one notation can express all the things that the other can plus some that it cannot.

It is ok for the "things" to actually be expressions of one of the notations, with a trivial mapping from each of its expressions to itself, and the other (the less expressive) notation mapping only to a proper subset of it (the more expressive). (The reason that expressibility here is able to differ from the example above is that here each expresssion of the two notations is being defined to express something different than it is in that example.)

See discussions in the Alice book or Maier's book. These deal with database querying languages. Eg expressively equivalent versions of relational algebra, relational tuple calculus and relational domain calculus, and also other languages like predicate logic and versions of Datalog.