The natural universe of discourse.

In order to deal with logical formulas that may generate infinite queries, we define a ``universe'' in which these queries may have a meaning. There are several ways to do this. The only thing they have in common is that the universe they define is finite.

The natural universe of an attribute is defined to be the set of all occurrences of this attribute in all the relations of a database. The natural universe of a set of attributes is the cartesian product of the natural universes of the individual attributes in the set.

Natural universes allow us to convert unsafe formulas into safe ones. For instance, suppose we have a predicate function , where is the name of a publisher and is the title of a book. The formula

$$\{(p,b)\vert\neg \mathrm{publishes}(p,b)\}$$

is unsafe, but in the natural universe it becomes

$$\{(p,b)\vert\exists _{b'}\mathrm{publishes}(p,b')\wedge \exi... ...'}\mathrm{publishes}(p',b)\wedge \neg \mathrm{publishes}(b,p)\}$$

whose logical meaning is

List all objects (which are publishers of something) together with the objects they don't publish (but which are books published by someone).

This is a safe formula since it is an AND of a safe formula (the first two terms) with a formula whose variables are all contained in the safe formula ( and ). This translates into the query

SELECT A.p,B.b

FROM publishers A, publishers B

WHERE (A.p,B.b) NOT IN publishers;