Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!qantel!lll-lcc!lll-crg!seismo!ut-sally!ark
From: ark@ut-sally.UUCP (Arthur M. Keller)
Newsgroups: net.database
Subject: Re: Problem with relational theory
Message-ID: <5717@ut-sally.UUCP>
Date: Thu, 11-Sep-86 20:10:37 EDT
Article-I.D.: ut-sally.5717
Posted: Thu Sep 11 20:10:37 1986
Date-Received: Sat, 13-Sep-86 05:54:51 EDT
References: <595@ur-tut.UUCP> <452@hdsvx1.UUCP> <819@navajo.STANFORD.EDU> <316@unc.unc.UUCP>
Reply-To: ark@sally.UUCP (Arthur M. Keller)
Organization: U. Texas CS Dept., Austin, Texas
Lines: 33
Summary: watch where your quantifiers go

Query:
	retrieve t1  where t1.name = t2.name  or t1.name = t3.name

In article <316@unc.unc.UUCP> rts@unc.UUCP (Rick Snodgrass) writes:
>One must be careful in deciding what the meaning of a statement in
>any language is. The best way is to go back to the formal semantics
>of the language. In his book, Ullman gives the semantics for Quel
>(Section 6.4). For this query, it is
>	{u | (Exists t1)(Exists t2)(Exists t3)
>		(R(t1) and R(t2) and R(t3) and u = t1
>			and (t1[name] = t2[name] or t1[name] = t3[name])
>		) }
>This semantics, which supports Hoffman's reply, is independent of
>the relational algebra.
>
>Rick Snodgrass
>Department of Computer Science, University of North Carolina at Chapel Hill

The problem is where the quantifiers go.  Consider:

{u | (Exists t1)(R(t1) and u = t1 and
	[(Exists t2) (S(t2) and t1[name]=t2[name]) or
	(Exists t3) (T(t3) and t1[name]=t3[name])])}

This query has ordinary union semantics, even if either S or T is
empty.  It is not clear that when given a quantifier-free expression
that quantifiers should always be introduced at the beginning.

Arthur
-- 
------------------------------------------------------------------------------
Arpanet: ARK@SALLY.UTEXAS.EDU
UUCP:    {gatech,harvard,ihnp4,pyramid,seismo}!ut-sally!ark