 |
 | 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 / January 2008Foreign keys
Always a physical issue. Never a theory issue.Agree? Evan > Always a physical issue. Never a theory issue.Agree? No.  SignatureJonathan Leffler #include <disclaimer.h> Email: jleffler@earthlink.net, jleffler@us.ibm.com Guardian of DBD::Informix v2007.0914 -- http://dbi.perl.org/ publictimestamp.org/ptb/PTB-2277 whirlpool 2008-01-15 03:00:05 3EBE3DF90EFE9D63DD387E6518C998E38B8DEF00F4A9F6171CB09FE34E5F75CB82E552 BC9E9539E6ED2645CBD0B2C0E9ADAAA653A3949A320F6E6EC7181AF27 > Always a physical issue. Never a theory issue.Agree? > > Evan Not just no, but Hell No! > Always a physical issue. Never a theory issue.Agree? Foreign keys are functional dependencies across two relations. More specifically, let R1(K1, A1, B1) be a relation with attribute sets K1, A1 and B1 where K1 is R1's primary key and B1 is a foreign key to the relation R2(K2, A2) where K2 is R2's primary key and A2 is the set of its remaining attributes. Then the foreign key B1 represents the functional dependency B1 --> A2, which is the functional dependency across two relation I mentioned in the first sentence. Furthermore, through transitivity by the functional dependency K1 --> B1, the foreign key also represents the inter-relational functional dependency K1 --> A2. Am I correct to say this? Signature-kira >> Always a physical issue. Never a theory issue.Agree? > [quoted text clipped - 18 lines] > > Am I correct to say this? I don't think so. A functional dependency A --> B is surjective, meaning not only that for every A there must be one and only one B, but also that for every B there must be at least one A. The relationship between B1 and A2 above is injective, as is the relationship between K1 and A2. >>> Always a physical issue. Never a theory issue.Agree? >> [quoted text clipped - 23 lines] > for every B there must be at least one A. The relationship between B1 and > A2 above is injective, as is the relationship between K1 and A2. Hmm... According to Atzeni/De Antonellis's book "Relational Database Theory" (section 1.6) he does not include surjectivity as a requirement for functional dependency. Signature-kira >>>> Always a physical issue. Never a theory issue.Agree? >>> [quoted text clipped - 33 lines] > > -- Functional dependencies are defined in terms of sets of attributes within the same relation schema. A functional dependency is a statement, A --> B, where A and B are sets of attributes. A relation satisfies the functional depencency if and only if whenever two tuples agree on values for A they also agree on values for B. Since both A and B appear in the same relation schema, whenever there is a value for B, there must also be a value for A. So it does not matter whether it is a stated requirement, surjectivity is a property that functional dependencies exhibit. > -kira >>>>> Always a physical issue. Never a theory issue.Agree? >>>> [quoted text clipped - 42 lines] > So it does not matter whether it is a stated requirement, surjectivity is a > property that functional dependencies exhibit. I think you're confusing the domain of an attribute with the set of attributes itself. An *attribute* is a variable that can participate in a relation. Each attribute has an associated set of values, which is called the *domain* of the attributes. For example, "age" is an attribute in the relation "person". The possible values of "age" can be defined as the set of non-negative integers. A functional dependency is a statement concerning the mapping between the domains of the attributes, not the set of attributes themselves. So, if I have a "person" relation with a finite number of tuples, then I cannot possibly have all possible non-negative integers. But yet, we still do have a functional dependency from the ID of the person to the person's age. Signature-kira >>>>>> Always a physical issue. Never a theory issue.Agree? >>>>> [quoted text clipped - 53 lines] > I think you're confusing the domain of an attribute with the set of > attributes itself. Are you not a native english speaker? Did my use of "values for A" confuse you? Suppose that you have two tuples, then you have a value for A in one tuple and a value for A in the other, so that would mean that there are "values for A," right? Especially before those values are compared? Or was it my use of the singular, "value for A," that confused you? If A is a set of attributes, then a value for A would be a set of attribute values, one for each attribute, right? > An *attribute* is a variable that can participate in a relation. Each > attribute has an associated set of values, which is called the *domain* of [quoted text clipped - 5 lines] > A functional dependency is a statement concerning the mapping between the > domains of the attributes, not the set of attributes themselves. I don't think so. What about a determinant that is composed of more than one attribute? For example, {SalesOrderNo, LineNo} --> PartNo. What if both the determinant and the dependent draw their values from the same domain? For example, EmployeeId --> ManagerId, since managers are also employees. > So, if I have a "person" relation with a finite number of tuples, then I > cannot possibly have all possible non-negative integers. But yet, we > still do have a functional dependency from the ID of the person to the > person's age. >>>>>>> Always a physical issue. Never a theory issue.Agree? >>>>>> [quoted text clipped - 55 lines] > > Are you not a native english speaker? You are quite right that I am not a native English speaker. > Did my use of "values for A" confuse > you? Suppose that you have two tuples, then you have a value for A in one [quoted text clipped - 16 lines] > I don't think so. What about a determinant that is composed of more than > one attribute? For example, {SalesOrderNo, LineNo} --> PartNo. If you have a composite key, then the domain of the key is simply the cartesian product of the domains of the attributes in the key. So, in you case, the domain for {SalesOrderNo, LineNo} is simply Z x Z. > What if > both the determinant and the dependent draw their values from the same > domain? For example, EmployeeId --> ManagerId, since managers are also > employees. What about it? How does that require surjectivity on the domain of PartNo? Conceivably, the domain of PartNo would include all possible integers. But the relation will not necessarily have all tuples where *every* possible values of PartNo are in some tuple of the relation. >> So, if I have a "person" relation with a finite number of tuples, then I >> cannot possibly have all possible non-negative integers. But yet, we >> still do have a functional dependency from the ID of the person to the >> person's age. Signature-kira >>>>> On 2008-01-15 04:37:23 -0500, "Brian Selzer" >>>>> <brian@selzer-software.com> [quoted text clipped - 100 lines] > cartesian product of the domains of the attributes in the key. So, in you > case, the domain for {SalesOrderNo, LineNo} is simply Z x Z. The domain for SalesOrderNo need not be Z, it could be SalesOrderNumbers. The domain for LineNo could be SalesOrderLineNumbers. Also, the domain of a composite key is not necessarily the cartesian product of its attributes' domains: it could be a subset of that product, since there may be constraints that limit the possible combinations of values from those domains. >> What if >> both the determinant and the dependent draw their values from the same [quoted text clipped - 7 lines] > But the relation will not necessarily have all tuples where *every* > possible values of PartNo are in some tuple of the relation. I think you're confusing what is possible and what is actual. What is represented by the domains and the intension of a database specifies /what can be/, but due to the domain closure assumption, what is represented by values in the extension of a database states /what is/. A functional dependency does not limit the possible values in each domain: it instead controls which combinations of values are possible. Lets take that one step further, a functional dependency A --> B does not directly limit the possible values for A or for B; instead it limits the possible combinations of values for A and B. Since A --> B only limits AB combinations, then for each value for B there must be at least one value for A, otherwise there wouldn't be an AB combination, would there? >>> So, if I have a "person" relation with a finite number of tuples, then I >>> cannot possibly have all possible non-negative integers. But yet, we >>> still do have a functional dependency from the ID of the person to the >>> person's age. >>>>>> On 2008-01-15 04:37:23 -0500, "Brian Selzer" >>>>>> <brian@selzer-software.com> [quoted text clipped - 22 lines] > possible values for A or for B; instead it limits the possible combinations > of values for A and B. So, a functional dependency does not limit the possible values in each domain. Ok. Rather, it limits the possible combinations of A x B. Ok. > Since A --> B only limits AB combinations, then for > each value for B there must be at least one value for A, otherwise there > wouldn't be an AB combination, would there? I still don't see the surjectivity requirement. In mathematics, a function is not necessarily surjective. For example, let R be the set of real numbers. Then the function f : R --> R defined by f(x) = x^2 is not a surjective function because f(x) can never be a negative number. In relational algebra, say I have a relation Person(Name, Age). Then there is functional dependency Name --> Age. Now, the domain for Age can be any non-negative integer. However, the extensional relation will not have a tuple for every possible value of Age. Are you saying that Name --> Age is not a functional dependency because it is not surjective? Signature-kira >>>>> On 2008-01-15 11:51:43 -0500, "Brian Selzer" >>>>> <brian@selzer-software.com> [quoted text clipped - 54 lines] > extensional relation will not have a tuple for every possible value of > Age. The functional dependency does not affect the set of all possible values for Age; it controls the possible combinations of values for Name and Age. If there is only one tuple with Name 'Brian' in the database, then the functional dependency would hold no matter what the value for Age is. The dependency holds, or is satisfied, so long as there aren't two tuples with the same Name but different Ages. > Are you saying that Name --> Age is not a functional dependency because it > is not surjective? No. What I'm saying is that not only is it the case that for every Name in the extension there is one and only one Age, but also that whenever there is an Age in the extension, there must also be a Name. This is due to the fact that Name and Age appear in the same relation schema. So in that sense Name --> Age /is/ surjective. I keep wanting to mention active domains, and for a database with a single relation, it would be valid to say that Name --> Age describes a surjection between the active domain for Name and the active domain for Age, but for databases with multiple relations, an active domain is the set of all values from a domain that are in any relation in the database. >> In relational algebra, say I have a relation Person(Name, Age). Then >> there is functional dependency [quoted text clipped - 19 lines] > databases with multiple relations, an active domain is the set of all values > from a domain that are in any relation in the database. Ok. I'm beginning to see your point. So, in the case of a single relation, the surjectivity holds trivially from the definition of functional dependency. However, in the case of foreign key where 2 relations are involved, the foreign key does not necessarily maps to every possible primary key in the other relation. So, it is possible to not have surjectivity between attributes across 2 relations. So, I do have one more question. Why do we want to require functional dependencies to be surjective? What desirable property of relational algebra do we lose if we introduct functional dependencies that are not surjective? Thanks. Signature-kira >>> In relational algebra, say I have a relation Person(Name, Age). Then >>> there is functional dependency [quoted text clipped - 43 lines] > > Thanks. Since functional dependencies are surjective, it can be said that A --> BC IFF A --> B /AND/ A --> C; if they weren't, then it could only be said that A --> BC IFF A --> B /OR/ A --> C. Similarly, the relation schema, R {A, B, C} where A --> BC, can represent exactly the same information as the pair of relation schemata, S {A, B} where A --> B, T {A, C} where A --> C, if and only if the cyclical inclusion dependency, S[A] = T[A] (mutual foreign keys) also holds. >>>> In relational algebra, say I have a relation Person(Name, Age). Then >>>> there is functional dependency [quoted text clipped - 47 lines] > > A --> BC IFF A --> B /AND/ A --> C; This property sounds like what Date, in his book "Introduction to Database System," defines as Join-dependency. > if they weren't, then it could only be said that > > A --> BC IFF A --> B /OR/ A --> C. Or that we can only say that if A --> B and A --> C, then A --> BC. However, the converse statement is not necessarily true. > Similarly, the relation schema, > [quoted text clipped - 9 lines] > > also holds. Ok. So the property we want with surjectivity is that of equivalence of representation through joins. Signature-kira > > Always a physical issue. Never a theory issue.Agree? > [quoted text clipped - 18 lines] > > Am I correct to say this? Not really. Your observation that sometimes the inference rules are the same for functional and inclusion dependencies is correct, but unfortunately this is not true in general. For example, the augmentation rule does not always hold for inclusion dependencies. In fact, axiomatizing the combination of functional and inclusion dependencies is a notoriously difficult problem and in the past there has been intensive research on that subject. -- Jan Hidders > -- > > -kira >>> Always a physical issue. Never a theory issue.Agree? >> [quoted text clipped - 27 lines] > dependencies is a notoriously difficult problem and in the past there > has been intensive research on that subject. I think my initial confusion came from my misunderstanding that functional dependencies can be defined across relations. However, after reading the definition more carefully, functional dependency is only defined within a single relation. Foreign keys, on the other hand, represent inter-relational constraints. It takes on a different definition. Consequently, they take on different inference rules, as you stated. I apologize for my confusion. Especially to Brian Selzer. And thanks for both yours and his corrections. Signature-kira > > Always a physical issue. Never a theory issue.Agree? > [quoted text clipped - 18 lines] > > Am I correct to say this? Not reading the whole thread (big mistake on my part), but how about the instance where a foreign key can be null?. No functional dependecy but legit. Evan >>>Always a physical issue. Never a theory issue.Agree? >> [quoted text clipped - 26 lines] > > Evan The legitimacy is predicated on the legitimacy of NULL in the first place. > >>>Always a physical issue. Never a theory issue.Agree? > >> [quoted text clipped - 28 lines] > > The legitimacy is predicated on the legitimacy of NULL in the first place. Absolutely agree. Evan > Not reading the whole thread (big mistake on my part), but how about the > instance where a foreign key can be null?. No functional dependecy but > legit. The response to this is the same as what has been given dozens of times before. Decompose the table into two tables, one of which only contains the PK and the FK under discussion. Now, when the FK would have received a null, omit the entire tuple (row), since it conveys no information. Nulls drop out of the discussion, and it proceeds as before. |
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
|
©2010 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.