What is the minimal proof that a database relation is not in BCNF?












1














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?










share|improve this question
























  • 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
















1














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?










share|improve this question
























  • 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














1












1








1


1





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?










share|improve this question















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








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


















  • 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












1 Answer
1






active

oldest

votes


















2














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).






share|improve this answer























  • 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













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
});


}
});














draft saved

draft discarded


















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









2














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).






share|improve this answer























  • 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


















2














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).






share|improve this answer























  • 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
















2












2








2






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).






share|improve this answer














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).







share|improve this answer














share|improve this answer



share|improve this answer








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




















  • 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




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

If I really need a card on my start hand, how many mulligans make sense? [duplicate]

Alcedinidae

Can an atomic nucleus contain both particles and antiparticles? [duplicate]