Re: teaching relational basics to people, questions

From: <>
Date: Sun, 13 Dec 2009 11:16:03 -0800 (PST)
Message-ID: <>

On Dec 11, 1:29 pm, Kevin Kirkpatrick <> wrote:
> Hello Mr. Scott,
> If I'm understanding your explanation properly, in a database with
> only table:
> (that is, lacking table STATES {STATE_CODE}) one must logically infer,
> from the CWA, that states with no big cities, e.g. 'RI', do not exist?

On Dec 11, 1:36 pm, Gene Wirchenko <> wrote:
> Effectively yes.

On Dec 11, 8:15 pm, "Mr. Scott" <> wrote:
> There isn't anywhere to record the assertion that there is a
> state with no big cities, so there can't be any.

It is more reasonable to say that the database is silent about the existence of states and cities. But even if it did, the inference that some state doesn't exist is wrong.

If the predicate is "the city named city_name in state state_code is big", then what you know is that for every tuple <c, s> in big_us_cities "city named c in state s is big", and that (by the cwa) for every tuple <c, s> typed by but not in in big_us_cities "it is not the case that: the city named c in state s is big". (Maybe there is no such named city anywhere; or maybe there's one in one or more in other states; and/or maybe they're just not big; or there's no such state; or that city in s is small; etc.) (If it were the case, the tuple would have been in the relation. The use of this interpretation of relations, which is done in a relational dbms and the relational algebra needs in order to answer queries, is "assuming a closed world".) This particular database (ie relation variable plus predicate) has nothing to say about the existence of states or cities. There is no way to write a relation expression whose predicate involves existence starting from only the given predicate.

Now, if the user is allowed to assume (which they would using the everyday meaning of the predicate above) that "exists c: the city named c in state s is big" implies "there is a state named s" then they could reason from <c,s> being in big_us_cities that "there is a state named s". But from <c,s> not in big_us_cities they still couldn't infer that "s is not a state". (Maybe there's just no such city; or it's small in state s; etc.)

Note that the database has no idea what the predicate is, let alone what "big" means or what a "state" is or the consequences (like "existence") of there being or not being a big city named c in state s. With this relation and predicate you can write a query that tells you whether (ie its predicate is) for some city c "there exists an s such that the city named c in state s is big". But there is no query that answers "is there a state s". (But I told you how to derive it).

This should not be surprising since if we change the predicate for big_us_cities to "the number of characters in string city_name is not the age of any dog whose tag says state_id" we wouldn't expect any query to give a different answer for any given value of big_us_cities. Regarding silence on existence, we also wouldn't expect any such change if we do add explicit information about existence.

Also regarding non-existence: Suppose existence is made explicit by the predicate being something like "state state_code exists and city city_name exists in that state and that city is big". Then when <c, s> is in big_us_cities you know "state s exists" because it follows from "state s exists and ...". But if <c,s> is not in big_us_cities you still don't know which (one or more) of the conjuncts is false to make the whole thing false. You only know the whole predicate is fakse using <c,s>. So you don't know that "state s doesn't exist".

philip Received on Sun Dec 13 2009 - 20:16:03 CET

Original text of this message