Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a relation:

A B C
1 2 3
4 5 6
7 2 8

Where $A\mapsto B$ and $C \mapsto B$. Doesn't that mean that $AC \mapsto B$? How can you even have this relation? What is the primary key?

I'm looking at this slide 10 on this power point: http://www.cs.utah.edu/~lifeifei/cs5530/slides/lecture13.pdf

I would think that if $A$ and $C$ are the same, then $B$ must also be the same. If you can prove this, please show how. The substitute teacher for the day (prof's PhD student) says it can't be done.

EDIT: Wouldn't you just show it by saying:

$AC \mapsto BC$ by augmentation Then, since $C \mapsto B$... you could write $AC \mapsto $B?

share|improve this question
    
What does AC mean? Element-wise multiplication? Edit: ops. I've just noticed (relation-algebra) tag. Notation might be known there.. –  user2468 Apr 3 '12 at 22:31
    
Sorry, AC being A AND B. –  user13327 Apr 3 '12 at 22:32
    
Are you asking if A and C can be considered a compound primary key in the given relational table? –  hardmath Apr 3 '12 at 22:32
    
@hardmath: Well, yes. It's just that I'm more focused on whether you can prove that AC->B given A->B and C->B. However, if someone can prove to me that it can be a compound primary key of this table, then it'll answer the same question right? –  user13327 Apr 3 '12 at 22:34
    
It's obvious that if B depends functionally on A, and B depends functionally on C, that B depends functionally on the combined values of A and C. The way you phrased things in terms of "if A and C are the same, then B must also be the same" was a little confusing, and perhaps that's why the substitute teacher responded as he/she did. –  hardmath Apr 3 '12 at 22:39

2 Answers 2

up vote 0 down vote accepted

The "slide 10" of the presentation you linked to above illustrates "Lossy Decomposition". That is, if a single table as above (3 rows, 3 columns A/B/C) is such that A and C are each primary keys for the table, then separating the table into two, one having the dependence of B on A, the other having the dependence of B on C, and joining them back together on values of B will produce additional combinations of fields (extra rows) just when the column B contains duplicate values.

But your question seems to be on a different point. If the value of A uniquely determines a row of the table, and a value of C also uniquely determines a row of the table, then a combination of both A and C also uniquely determines a row. I'd double check, but I think this could be restated in terms of how "normalized" the table is.

share|improve this answer

Just proved it to him:

By augmentation: AC->BC By decomposition: AC->B and AC->C

Sorry for such a simple question. I should have figured it out earlier. Blah.

share|improve this answer
1  
Note that your proof only requires A -> B in order to prove AC -> B. In effect either A or C being enough information to determine B will imply the combination of A and C determines B. –  hardmath Apr 3 '12 at 22:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.