Path: dp-news.maxwell.syr.edu!spool.maxwell.syr.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!colt.net!news.tele.dk!feed118.news.tele.dk!postnews.google.com!v46g2000cwv.googlegroups.com!not-for-mail
From: "Mikito Harakiri" <mikharakiri_nospaum@yahoo.com>
Newsgroups: comp.databases.theory
Subject: Functional dependency is multivalued dependency
Date: 28 Apr 2006 09:18:06 -0700
Organization: http://groups.google.com
Lines: 19
Message-ID: <1146241086.922523.280790@v46g2000cwv.googlegroups.com>
NNTP-Posting-Host: 148.87.1.170
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
X-Trace: posting.google.com 1146241092 23250 127.0.0.1 (28 Apr 2006 16:18:12 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 28 Apr 2006 16:18:12 +0000 (UTC)
User-Agent: G2/0.2
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.2) Gecko/20060308 Firefox/1.5.0.2,gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: v46g2000cwv.googlegroups.com; posting-host=148.87.1.170;
   posting-account=jduQMA0AAABKdEh0L1SEqrR3hnlHUlAG
Xref: dp-news.maxwell.syr.edu comp.databases.theory:38853

The proof of proposition 8.2.2 (page 164, the Alice book) begins with
observation that given three sets of attributes X, Y and Z such that
set Z complements sets X an Y in the relation header of the relalation
I, the pi_XY(I) /\ pi_XZ(I) is always a superset of I. Is it obvious?

In RL we do it in couple of steps:

(XY \/ I) /\ (XZ \/ I) <= I  ?

This is the same as

I /\ (XY \/ I) /\ (XZ \/ I) <= I

and the left side reduces to I by 2 applications of the absorption law.


That is about prioving the obvious part of the proposition. I'm stuck
on the non-obvious part. Any ideas?