What is the minimal proof that a database relation is not in BCNF?
I have the following functional dependencies (they represent all the functional dependencies on my relation):
(1) BrokerName -> Office
(2) StockName -> Dividend
(3) InvestorId -> BrokerName
(4) InvestorId, Stockname -> Quantity
(5) InvestorId, Stockname -> Office
I know from using the techniques in this YouTube video that (InvestorId, Stockname)
is my one and only candidate key.
According to @nvogel's solution in this SO thread:
A relation, R, is in BCNF iff for every nontrivial FD (X->A) satisfied
by R the following condition is true:
(a) X is a superkey for R
Since I know that (1), (2) and (3) are all non-trivial FDs whose left hand sides are not superkeys or candidate keys for that matter, is that all I need to say to prove that my relation is not in BCNF? Is this process the correct method of demonstrating that a relation is not in BCNF or is there a better way?
database relational-database database-normalization bcnf
add a comment |
I have the following functional dependencies (they represent all the functional dependencies on my relation):
(1) BrokerName -> Office
(2) StockName -> Dividend
(3) InvestorId -> BrokerName
(4) InvestorId, Stockname -> Quantity
(5) InvestorId, Stockname -> Office
I know from using the techniques in this YouTube video that (InvestorId, Stockname)
is my one and only candidate key.
According to @nvogel's solution in this SO thread:
A relation, R, is in BCNF iff for every nontrivial FD (X->A) satisfied
by R the following condition is true:
(a) X is a superkey for R
Since I know that (1), (2) and (3) are all non-trivial FDs whose left hand sides are not superkeys or candidate keys for that matter, is that all I need to say to prove that my relation is not in BCNF? Is this process the correct method of demonstrating that a relation is not in BCNF or is there a better way?
database relational-database database-normalization bcnf
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02
add a comment |
I have the following functional dependencies (they represent all the functional dependencies on my relation):
(1) BrokerName -> Office
(2) StockName -> Dividend
(3) InvestorId -> BrokerName
(4) InvestorId, Stockname -> Quantity
(5) InvestorId, Stockname -> Office
I know from using the techniques in this YouTube video that (InvestorId, Stockname)
is my one and only candidate key.
According to @nvogel's solution in this SO thread:
A relation, R, is in BCNF iff for every nontrivial FD (X->A) satisfied
by R the following condition is true:
(a) X is a superkey for R
Since I know that (1), (2) and (3) are all non-trivial FDs whose left hand sides are not superkeys or candidate keys for that matter, is that all I need to say to prove that my relation is not in BCNF? Is this process the correct method of demonstrating that a relation is not in BCNF or is there a better way?
database relational-database database-normalization bcnf
I have the following functional dependencies (they represent all the functional dependencies on my relation):
(1) BrokerName -> Office
(2) StockName -> Dividend
(3) InvestorId -> BrokerName
(4) InvestorId, Stockname -> Quantity
(5) InvestorId, Stockname -> Office
I know from using the techniques in this YouTube video that (InvestorId, Stockname)
is my one and only candidate key.
According to @nvogel's solution in this SO thread:
A relation, R, is in BCNF iff for every nontrivial FD (X->A) satisfied
by R the following condition is true:
(a) X is a superkey for R
Since I know that (1), (2) and (3) are all non-trivial FDs whose left hand sides are not superkeys or candidate keys for that matter, is that all I need to say to prove that my relation is not in BCNF? Is this process the correct method of demonstrating that a relation is not in BCNF or is there a better way?
database relational-database database-normalization bcnf
database relational-database database-normalization bcnf
edited Nov 20 at 5:20
asked Nov 20 at 4:09
user5814
1,080519
1,080519
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02
add a comment |
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02
add a comment |
1 Answer
1
active
oldest
votes
We need to know all the FDs (functional dependencies) that hold to determine CKs (candidate keys), not just those in some list. Look at a (correct & general) definition of CK or algorithm for finding CKs (in a published textbook, not a youtube video). Is your list appropriately a closure (all the FDs that hold) or cover (FDs that imply the FDs in the closure via Armstrong's axioms), whichever that definition or algorithm uses? Because if not then you can't say that you know the set of CKs. Your original claim that you "have the following functional dependencies" is not enough. Your later claim that "they represent all the [nontrivial?] functional dependencies" is wrong--if those hold, InvestorId, Stockname -> Office also holds. Your later adding item 5 to the list doesn't help--there are others. But even if Armstrong's axioms wouldn't add any FDs to the list, so there wouldn't be any others that hold when the listed ones hold, why do you think the given list is exhaustive in your design if you didn't show it?
We may know that some FDs hold, and Armstrong's axioms give all the FDs that must hold if those do, but to know that given FDs form a cover we must also show that the FDs that are not generated by Armstrong's axioms don't hold. Note that if X doesn't functionally determine Y then no subset of X determines Y & X doesn't determine any superset of Y.
Similarly, that definition of BCNF is talking about all the non-trivial FDs that hold, not just some or those in a cover.
On the other hand, all you need to show that that particular definition of BCNF is violated is that some FD that holds is not out of a superkey. So--given that that is the only CK--yes, any of 1-3 alone is adequate, since none is out of a superkey.
PS Find & follow a (good) published academic textbook on information modeling & database design. Dozens are online free in pdf. See the Stanford University free online course & its youtube videos (& its professor's textbook).
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53386095%2fwhat-is-the-minimal-proof-that-a-database-relation-is-not-in-bcnf%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
We need to know all the FDs (functional dependencies) that hold to determine CKs (candidate keys), not just those in some list. Look at a (correct & general) definition of CK or algorithm for finding CKs (in a published textbook, not a youtube video). Is your list appropriately a closure (all the FDs that hold) or cover (FDs that imply the FDs in the closure via Armstrong's axioms), whichever that definition or algorithm uses? Because if not then you can't say that you know the set of CKs. Your original claim that you "have the following functional dependencies" is not enough. Your later claim that "they represent all the [nontrivial?] functional dependencies" is wrong--if those hold, InvestorId, Stockname -> Office also holds. Your later adding item 5 to the list doesn't help--there are others. But even if Armstrong's axioms wouldn't add any FDs to the list, so there wouldn't be any others that hold when the listed ones hold, why do you think the given list is exhaustive in your design if you didn't show it?
We may know that some FDs hold, and Armstrong's axioms give all the FDs that must hold if those do, but to know that given FDs form a cover we must also show that the FDs that are not generated by Armstrong's axioms don't hold. Note that if X doesn't functionally determine Y then no subset of X determines Y & X doesn't determine any superset of Y.
Similarly, that definition of BCNF is talking about all the non-trivial FDs that hold, not just some or those in a cover.
On the other hand, all you need to show that that particular definition of BCNF is violated is that some FD that holds is not out of a superkey. So--given that that is the only CK--yes, any of 1-3 alone is adequate, since none is out of a superkey.
PS Find & follow a (good) published academic textbook on information modeling & database design. Dozens are online free in pdf. See the Stanford University free online course & its youtube videos (& its professor's textbook).
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
add a comment |
We need to know all the FDs (functional dependencies) that hold to determine CKs (candidate keys), not just those in some list. Look at a (correct & general) definition of CK or algorithm for finding CKs (in a published textbook, not a youtube video). Is your list appropriately a closure (all the FDs that hold) or cover (FDs that imply the FDs in the closure via Armstrong's axioms), whichever that definition or algorithm uses? Because if not then you can't say that you know the set of CKs. Your original claim that you "have the following functional dependencies" is not enough. Your later claim that "they represent all the [nontrivial?] functional dependencies" is wrong--if those hold, InvestorId, Stockname -> Office also holds. Your later adding item 5 to the list doesn't help--there are others. But even if Armstrong's axioms wouldn't add any FDs to the list, so there wouldn't be any others that hold when the listed ones hold, why do you think the given list is exhaustive in your design if you didn't show it?
We may know that some FDs hold, and Armstrong's axioms give all the FDs that must hold if those do, but to know that given FDs form a cover we must also show that the FDs that are not generated by Armstrong's axioms don't hold. Note that if X doesn't functionally determine Y then no subset of X determines Y & X doesn't determine any superset of Y.
Similarly, that definition of BCNF is talking about all the non-trivial FDs that hold, not just some or those in a cover.
On the other hand, all you need to show that that particular definition of BCNF is violated is that some FD that holds is not out of a superkey. So--given that that is the only CK--yes, any of 1-3 alone is adequate, since none is out of a superkey.
PS Find & follow a (good) published academic textbook on information modeling & database design. Dozens are online free in pdf. See the Stanford University free online course & its youtube videos (& its professor's textbook).
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
add a comment |
We need to know all the FDs (functional dependencies) that hold to determine CKs (candidate keys), not just those in some list. Look at a (correct & general) definition of CK or algorithm for finding CKs (in a published textbook, not a youtube video). Is your list appropriately a closure (all the FDs that hold) or cover (FDs that imply the FDs in the closure via Armstrong's axioms), whichever that definition or algorithm uses? Because if not then you can't say that you know the set of CKs. Your original claim that you "have the following functional dependencies" is not enough. Your later claim that "they represent all the [nontrivial?] functional dependencies" is wrong--if those hold, InvestorId, Stockname -> Office also holds. Your later adding item 5 to the list doesn't help--there are others. But even if Armstrong's axioms wouldn't add any FDs to the list, so there wouldn't be any others that hold when the listed ones hold, why do you think the given list is exhaustive in your design if you didn't show it?
We may know that some FDs hold, and Armstrong's axioms give all the FDs that must hold if those do, but to know that given FDs form a cover we must also show that the FDs that are not generated by Armstrong's axioms don't hold. Note that if X doesn't functionally determine Y then no subset of X determines Y & X doesn't determine any superset of Y.
Similarly, that definition of BCNF is talking about all the non-trivial FDs that hold, not just some or those in a cover.
On the other hand, all you need to show that that particular definition of BCNF is violated is that some FD that holds is not out of a superkey. So--given that that is the only CK--yes, any of 1-3 alone is adequate, since none is out of a superkey.
PS Find & follow a (good) published academic textbook on information modeling & database design. Dozens are online free in pdf. See the Stanford University free online course & its youtube videos (& its professor's textbook).
We need to know all the FDs (functional dependencies) that hold to determine CKs (candidate keys), not just those in some list. Look at a (correct & general) definition of CK or algorithm for finding CKs (in a published textbook, not a youtube video). Is your list appropriately a closure (all the FDs that hold) or cover (FDs that imply the FDs in the closure via Armstrong's axioms), whichever that definition or algorithm uses? Because if not then you can't say that you know the set of CKs. Your original claim that you "have the following functional dependencies" is not enough. Your later claim that "they represent all the [nontrivial?] functional dependencies" is wrong--if those hold, InvestorId, Stockname -> Office also holds. Your later adding item 5 to the list doesn't help--there are others. But even if Armstrong's axioms wouldn't add any FDs to the list, so there wouldn't be any others that hold when the listed ones hold, why do you think the given list is exhaustive in your design if you didn't show it?
We may know that some FDs hold, and Armstrong's axioms give all the FDs that must hold if those do, but to know that given FDs form a cover we must also show that the FDs that are not generated by Armstrong's axioms don't hold. Note that if X doesn't functionally determine Y then no subset of X determines Y & X doesn't determine any superset of Y.
Similarly, that definition of BCNF is talking about all the non-trivial FDs that hold, not just some or those in a cover.
On the other hand, all you need to show that that particular definition of BCNF is violated is that some FD that holds is not out of a superkey. So--given that that is the only CK--yes, any of 1-3 alone is adequate, since none is out of a superkey.
PS Find & follow a (good) published academic textbook on information modeling & database design. Dozens are online free in pdf. See the Stanford University free online course & its youtube videos (& its professor's textbook).
edited Nov 21 at 5:26
answered Nov 20 at 4:59
philipxy
11.4k42149
11.4k42149
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
add a comment |
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
Yep, should probably make it clearer that those are all the FDs that exist on the relation. Just to clarify, if 1-4 represents all the FDs, is it called a cover?
– user5814
Nov 20 at 5:02
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
See my edited version. You claim you properly found FDs. But if that list 1-4 isn't a cover then you didn't find the CKs correctly.
– philipxy
Nov 20 at 5:05
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
I understand what you are saying about finding all the FDs - I've edited my post accordingly. The FDs I have listed are exhaustive.
– user5814
Nov 20 at 5:07
1
1
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
No that list is not exhaustive. Eg InvestorId, Stockname -> Office holds. Armstrong's axioms give the closure ie an exhaustive list. I said: is it a closure or cover, per your definition or algorithm. Quote the definition or algorithm to show you used it propery. What (unsound) justification do you (wrongly) think you have that that list is exhaustive?
– philipxy
Nov 20 at 5:15
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53386095%2fwhat-is-the-minimal-proof-that-a-database-relation-is-not-in-bcnf%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Why did you add (5) to the list? Do you understand that there are yet other non-trivial FDs that hold when the FDs in the new (& old) list hold--per Armstrong's axioms? I hope my answer explains.
– philipxy
Nov 20 at 7:02