 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
| HomeDiscussion Groups Database Servers DB2InformixIngresMS SQLOraclePervasive.SQLPostgreSQLProgressSybaseDesktop Databases FileMakerFoxProMS AccessParadoxGeneral General DB TopicsDatabase TheoryRelated Topics Java Development.NET DevelopmentVB DevelopmentMore Topics ... |
Database Forum / General DB Topics / DB Theory / October 2008?? Functional Dependency Question ??
Hi all, I'm reading Elmasri & Navathe's "Fundamentals of Database Systems, 4th ed.". The authors discuss how, given a set if FDs, additional FDs can be inferred. The authors provide six "Inference Rules". At one point the authors say this: "Although X->A and X->B implies X->AB by the union rule stated above, X->A, and Y->B does *not* imply that XY->AB." I'm not seeing this. It seems to me that X->A, and Y->B *DOES* imply that XY->AB. I'm sure I'm wrong but I'm not seeing it. Can someone explain? Thanks > Hi all, > [quoted text clipped - 12 lines] > > Thanks If I understand it right, XY does not imply X and Y. > Hi all, > [quoted text clipped - 12 lines] > > Thanks I'm not seeing it either. By these truth tables, it seems to: XY AB X->A Y->B (X->A)(Y->B) XY->AB (X->A)(Y->B)->(XY->AB) 00 00 1 1 1 1 1 00 01 1 1 1 1 1 00 11 1 1 1 1 1 00 10 1 1 1 1 1 01 10 1 0 0 1 1 01 11 1 1 1 1 1 01 01 1 1 1 1 1 01 00 1 0 0 1 1 11 00 0 0 0 0 1 11 01 0 1 0 0 1 11 11 1 1 1 1 1 11 10 1 0 0 0 1 10 10 1 1 1 1 1 10 11 1 1 1 1 1 10 01 0 1 0 1 1 10 00 0 1 0 1 1 (View with a fixed width font) Can anyone find a mistake in the above truth tables? Is there a difference between functional dependency and implication that I need to learn? ... > I'm not seeing it either. By these truth tables, it seems to: > [quoted text clipped - 21 lines] > difference between functional dependency and implication that I need to > learn? The table looks right to me. > ... Is there a > difference between functional dependency and implication that I need to > learn? Just a not very well read guess, but I'd think no important difference for practitioners as long as they don't try to record negations, which is be confusing anyway, at least for me. Always seemed more than coincidence that the usual ascii fd notation was reminiscent of both notions. I seem to recall wondering years ago why the db design IDE's of the time, at least the ones I saw, didn't have a simple feature that would let one validate fd's one had in mind. Seemed to me that most of the time they wouldn't be affected by explosive execution times if they emulated truth tables rather than try to cleverly compile axioms and theorems. All very vague I know but the sun and the plonk are shining here on the west coast. Hope it's not just the sulphites. > tlbaxte...@yahoo.com wrote: > [quoted text clipped - 33 lines] > difference between functional dependency and implication that I need to > learn? Your truth table is correct. You can also prove this with Boolean algebra (below ~ = not, + = or, * = and): given : (1) 1 = ~X + A : X implies A (2) 1 = ~Y + B : Y implies B prove : (3) 1 = ~(XY) + AB : XY implies AB proof : (4) 1 = (~X + A)(~Y + B) : conjuction of (1) and (2) (5) 1 = ~X~Y + ~XB + ~YA + AB : distributive and commutative (6) 1 = ~X~Y + ~X~Y + ~XB + ~YA + AB : idempotent (7) 1 = ~X(~Y + B) + ~Y(~X + A) + AB : distributive and commutative (8) 1 = ~X + ~Y + AB : substitute (1) and (2) (9) 1 = ~(XY) + AB : De Morgan QED KHD >> tlbaxte...@yahoo.com wrote: >> [quoted text clipped - 54 lines] > > KHD Nice, step 6 seems cute (to an amateur like me). It's seeing the parallels that fascinates me, seeing parallels seems to be important in the RM, perhaps more important than seeing ways to express structure in precise abstract terms, eg mathematical terms, as opposed to graphical or visual ways or ways that resort to particular imprecise programming methods. > > tlbaxte...@yahoo.com wrote: > [quoted text clipped - 56 lines] > > QED It's interesting how people come up with such different ways to prove things. I personally tend to use a conditional proof where possible: RTP: (X->A)(Y->B) -> XY->AB (X->A)(Y->B) : premise X->A, Y->B : conjunction elimination XY : premise X,Y : conjunction elimination A : modus ponens on X,X->A B : modus ponens on Y,Y->B AB : conjunction introduction XY->AB : conditional proof (X->A)(Y->B) -> XY->AB : conditional proof ... > RTP: (X->A)(Y->B) -> XY->AB > [quoted text clipped - 7 lines] > XY->AB : conditional proof > (X->A)(Y->B) -> XY->AB : conditional proof I can see that the second step is eliminating a "conjunction" but the fourth step doesn't seem to me to involve a conjunction. > ... > [quoted text clipped - 12 lines] > I can see that the second step is eliminating a "conjunction" but the > fourth step doesn't seem to me to involve a conjunction. Step 3: Premise XY (the conjunction of X and Y). Step 4: From XY deduce X and deduce Y (known as conjunction elimination). >> ... >> [quoted text clipped - 12 lines] > > Step 3: Premise XY (the conjunction of X and Y). ... But XY (in the usual FD notation) is a union, not a conjunction. (If step 4 is valid, there must be a subtlety here that goes beyond just conjunction elimination, ie., some other notion must be involved, but so far it could be eludes me.) thanks, p > >> ... > [quoted text clipped - 20 lines] > conjunction elimination, ie., some other notion must be involved, but so > far it could be eludes me.) Ah, Ok I understand your point now. (X->A)(Y->B) -> XY->AB is a formula in the propositional calculus, which is shown to be a theorem. In that context XY is definitely a logical conjunction. In FD notation we think of X,Y as sets of attributes and as you say XY is a notation for the union of those sets. However there is this idea of translating an FD sentence into a formula in the propositional calculus. This mapping can be done as follows - sets of attributes can be mapped to proposition symbols - unions of sets of attributes can be mapped to logical conjunction - a functional dependency can be mapped to a logical implication Consider that in the FD world symbol X represents a set of attributes from some relation R. Let some tuple of R be given. Then as a proposition we interpret X as implying that we are given or can deduce (for the given tuple) the values of all the attributes associated with X. This interpretation makes it obvious that unions of attributes map to logical conjunctions, and that an FD maps to a logical implication. ... > Consider that in the FD world symbol X represents a set of attributes > from some relation R. Let some tuple of R be given. Then as a [quoted text clipped - 3 lines] > map to logical conjunctions, and that an FD maps to a logical > implication. Thanks, but how does that interpretation work when R has no attributes? > ... > [quoted text clipped - 7 lines] > > Thanks, but how does that interpretation work when R has no attributes? What’s the problem? If there are no attributes then the only FD we can state is {} -> {} which is an example of a trivial FD (because rhs is a subset of the lhs). In the propositional calculus this maps to true -> true. The empty set of attributes (union identity) maps to true (conjunctive identity). >> ... >> [quoted text clipped - 19 lines] > The empty set of attributes (union identity) maps to true (conjunctive > identity). Okay, but isn't this changing the original mapping which was from VALUES of attributes? > >> ... > [quoted text clipped - 22 lines] > Okay, but isn't this changing the original mapping which was from VALUES > of attributes? I agree that as stated the interpretation isn’t very clear when R is empty – because it asks for a tuple of R to be given. Note also that I didn’t distinguish between intension and extension, and I understand that an FD has more to do with the former than the latter. By definition the empty set maps to ‘true’. This is consistent with saying that the proposition ‘true’ is interpreted as stating that for any given tuple the values of all the attributes in the empty set are knowable. This of course tells us nothing – as we expect from the information-less proposition ‘true’. >>>> ... >>>>> Consider that in the FD world symbol X represents a set of attributes [quoted text clipped - 26 lines] > knowable. This of course tells us nothing – as we expect from the > information-less proposition ‘true’. Thanks, that might have given me a clue for a slightly different mapping interpretation, (the old trick question "when there are no purple parts, which suppliers supply purple parts? answer is: all of them"). >>>>> ... >>>>> [quoted text clipped - 37 lines] > interpretation, (the old trick question "when there are no purple parts, > which suppliers supply purple parts? answer is: all of them"). I think the answer is actually "none of them". If you changed the question slightly to "When there are no purple parts, which suppliers supply all of the purple parts?" then the answer would be "all of them". >>>>>> ... >>>>>> [quoted text clipped - 44 lines] > question slightly to "When there are no purple parts, which suppliers > supply all of the purple parts?" then the answer would be "all of them". Right. thanks > > ... If you changed the > > question slightly to "When there are no purple parts, which suppliers > > supply all of the purple parts?" then the answer would be "all of them". Reminds me of first year Uni, when my maths lecturer asked us whether every hippopotamus in the room was wearing pink panties. > > > ... If you changed the > > > question slightly to "When there are no purple parts, which suppliers > > > supply all of the purple parts?" then the answer would be "all of them". > > Reminds me of first year Uni, when my maths lecturer asked us whether > every hippopotamus in the room was wearing pink panties. Which is it then logicists? Ax [ inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] = false Ax [ inRoom(x) ^ isHippo(x) -> Wearing(x, pink panties) ] = true > > > > ... If you changed the > > > > question slightly to "When there are no purple parts, which suppliers [quoted text clipped - 8 lines] > > Ax [ inRoom(x) ^ isHippo(x) -> Wearing(x, pink panties) ] = true I'm no logicist but I think only the second is a faithful translation. Otherwise, wouldn't statements like every frog is an animal be deemed false? > Ax [ inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] = false Is this actually the case? There doesn't appear to be any defined set over which the universal quantification is defined, so I think the left hand side is meaningless not false. I think a meaningful universal quantification must be able to be written in the form Ax [ P(x) -> Q(x) ] where { x | P(x) } is a well defined set. We can write Ax [ inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] as Ax [ true -> inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] So it seems that we must define P(x) = true, but then { x | P(x) } is the set of all things which is meaningless. > > Ax [ inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] = false > [quoted text clipped - 19 lines] > So it seems that we must define P(x) = true, but then { x | P(x) } is > the set of all things which is meaningless. Apologies for double click posting. > > Ax [ inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] = false > > Is this actually the case? There doesn't appear to be any defined set > over which the universal quantification is defined, so I think the > left hand side is meaningless not false. While you're right, could you not read that first statement as: Ax [Exists(x) -> inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] How do you like them apples! Either way, false or meaningless, its clearly not what the lecturer was saying so the second statement was the banker: Ax [inRoom(x) ^ isHippo(x) -> Wearing(x, pink panties) ] which is true (material implication is always true if the antecedent is false). Hence, as far as formal logic is concerned all the hippos in the room are indeed wearing pink panties. And blue panties too in fact. And no panties as well... > I think a meaningful universal quantification must be able to be > written in the form [quoted text clipped - 13 lines] > So it seems that we must define P(x) = true, but then { x | P(x) } is > the set of all things which is meaningless. Why is the "set of all things" meaningless? > Apologies for double click posting. > [quoted text clipped - 6 lines] > While you're right, could you not read that first statement as: > Ax [Exists(x) -> inRoom(x) ^ isHippo(x) ^ Wearing(x, pink panties) ] Assuming that someone has properly defined these relations, and in particular Exists(x) (or equivalently its extension is well defined), that translation would presumably be false. > How do you like them apples! Either way, false or meaningless, its > clearly not what the lecturer was saying so the second statement was [quoted text clipped - 25 lines] > > Why is the "set of all things" meaningless? An axiom of set theory states that it is always meaningful to define a subset of a given set according to some well defined predicate. ie the axiom states that given set S, and predicate f, { x in S | f(x) } is a well defined set. In particular we can take the subset of the extension of P(x) defined as the set of all sets that are not members of themselves, leading to Russell's paradox. ... > I think the answer is actually "none of them". If you changed the > question slightly to "When there are no purple parts, which suppliers > supply all of the purple parts?" then the answer would be "all of them". Maybe a useful principle to follow when phrasing db queries out loud is to preface all possible parameters with one of the adjectives "all" or "any". > Bob Badour wrote: ... >> [quoted text clipped - 6 lines] > is to preface all possible parameters with one of the adjectives > "all" or "any". or "none of" which might not add any capability but which might make the phrasing more amenable. People who are prone to long sentences, me included, must remember that the rm is what it is, as they say, and no more, so we are on safer ground if we try to talk in language that parallels what it is capable of. There are many honourable modes of language and abstractions of thought that are important to us, but the RM claims to be useful for organizing only a small part. A quote I like from SICP: The acts of the mind, wherein it exerts its power over simple ideas, are chiefly these three: 1. Combining several simple ideas into one compound one, and thus all complex ideas are made. 2. The second is bringing two ideas, whether simple or complex, together, and setting them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations. 3. The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made. John Locke, An Essay Concerning Human Understanding (1690) > ... > [quoted text clipped - 7 lines] > > Thanks, but how does that interpretation work when R has no attributes? The same way DEE works with join. >> ... >> [quoted text clipped - 9 lines] > > The same way DEE works with join. I'm not sure about that. Maybe I'm being too literal in asking about this, but David B is talking about a mapping that involves values of attributes. I don't know what the value of "no attribute" is. >>> ... >>> [quoted text clipped - 13 lines] > this, but David B is talking about a mapping that involves values of > attributes. I don't know what the value of "no attribute" is. Regardless, it is a value. It can either exist in the relation or not. We can test it for equality. What else does one need to know about it? >>>> ... >>>> [quoted text clipped - 16 lines] > Regardless, it is a value. It can either exist in the relation or not. > We can test it for equality. What else does one need to know about it? I can see that the tuple in DEE must have a value, the empty set I presume. But when I think of an empty set of <A,T,V> triples, ie., {}, I'm darned if I can imagine a mental device for preserving a V, concrete or not, that corresponds with an A that isn't present. That's what I was quibbling about in David B's interpretation. (Maybe I shouldn't drift the topic, but I'm guessing there's no problem with DUM! I guess empty relations never have any problem satisfying relational closure as long as their constraints aren't effectively negations, eg., "IS_EMPTY".) > > >> ... > [quoted text clipped - 38 lines] > (for the given tuple) the values of all the attributes associated with > X. This perspective of FD theory into propositional calculus is new to me. So could you please be more specific? Sure propositional calculus has some axioms that have no interpretation in FD world, e.g. A -> (B -> A) or it has? > This interpretation makes it obvious that unions of attributes > map to logical conjunctions, and that an FD maps to a logical > implication.- Hide quoted text - > > - Show quoted text - > > > >> ... > [quoted text clipped - 46 lines] > > or it has? I would say wff’s of FD theory map to a strict subset of wff’s of the propositional calculus. The idea is not mine. I’m trying to make sense of Bob Badour’s post where he suggested a simple connection between FD and logical implication. > tlbaxte...@yahoo.com wrote: > > Hi all, [quoted text clipped - 39 lines] > difference between functional dependency and implication that I need to > learn? The formally correct way to establish boolean algebra <-> FD correspondence (which I saw in one article, although missing the reference, sorry) is to transform the original relation into the one with boolean values the following way. We take the original relation, e.g. Name Age ------ ---- John 20 Kate 20 add tuple # (which is technically not required) # Name Age - ------ ---- 1 John 20 2 Kate 20 and construct the boolean relation Pair NameEq AgeEq ---- --------- -------- 1,2 false true As soon as you have a tuple with "true -> false" you break functional dependency, which is incidentally the same condition as for boolean implication. I forgot how far the autors have driven this idea though.... > Hi all, > [quoted text clipped - 12 lines] > > Thanks Here's what I get using Armstrong's Axioms: i) X -> A (given) ii) XY -> AY (augment i) with Y) iii) Y -> B (given) iv) AY -> AB (augment iii) with A ) v) XY -> AB (ii), iv), transitivity) Maybe the book has a typo? If so, I wonder what they meant to say? Does anyone think there is a possibility that X intersect Y is not empty? Could this be what the authors intended? > Does anyone think there is a possibility that X intersect Y is not > empty? Could this be what the authors intended? I thought the Armstrong Axioms apply to any subset of a header. You could substitute RS for X and ST for Y and show that RST -> AB. Hello all, One of the authors of the book replied to my email and indeed the book is in error. Thanks to all who responded. |
Reply to this Message |
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.