Driver: What the hell? We seem to be crashing!

Passenger: I removed the front left wheel

Driver: You what?!

Passenger: I removed the wheel. Then you turned left and it caused instability. Don’t you think your claim to have a reliable car is invalid?

Driver: You’re not supposed to remove the bloody wheels while we’re moving!

Removing a function at runtime (runtime being the programming equivalent of a car being in motion) that other functions rely on is usually a guaranteed way to break your program. Fortunately, statically-typed languages don’t allow you to do this. Changing the nature of a given function at runtime would also break the referential transparency of any function that depended on it, because the dependent functions might then produce different results. Again, statically-typed languages protect us from that kind of foolishness.

Composing new functions at runtime is possible in such languages, on the other hand. But a) the basic function signature will be known in advance and b) the function won’t change once created. So that’s not a problem.

Dynamically-typed languages do tend to allow this kind of thing, which is one of the reasons that pure functional programming is rather difficult to guarantee in those languages. If you are using one of those languages to do functional programming, deleting existing functions from the dependency graph is high on the list of things you shouldn’t do.

First, let me point out that normalization procedures do not “decompose until you cannot further decompose”. They usually decompose until you reach the normal form that has the desired properties, but not further, and it is quite possible and even likely that in the highest normal form further decomposition is still possible, but not desirable. For example, a relation R(A, B, C) with functional dependencies A->B and A->C can be decomposed into R1(A, B) and R2(A, C), but R is already in BCNF so this is not required by BCNF normalization procedures.

With that that settled, let us get to the task of normalizing this to BCNF. Let us name the dependencies:

FD1 : A -> CDE

FD2: ABGH -> FIJK

FD3: GHIJ -> ABF

First step: computing the candidate keys.

I will not repeat the algorithm, because you can easily find that elsewhere. In this case the candidate keys are: ABGH and GHIJ.

Second step: determining the current normal form.

The check for 1NF succeeds trivially, since we assume that R is a relation as defined by the relational model. The check for 2NF already fails for FD1 because A is not the superset of a candidate key, and in fact a proper subset of a candidate key. So the current relation is in 1NF only.

We will follow the normalization procedure that splits off violating dependencies into separate relations.

Third step: splitting of FD1. This means we create from R a relation R2 with all the attributes of the FD, and R1 which contains all the attributes of R minus those in the right-hand side of the FD. So our new schema becomes:

R1(A, B, F, G, H, I, J, K) and R2(A, C, D, E)

Fourth step: determine the candidate keys of the new relations. This is needed to check in what normal form the result is. The result of this is:

R1 has candidate keys: ABGH and GHIJ

R2 has candidate keys: A

NOTE: It is not correct to determine the keys in a schema with several relations by only considering the dependencies that contain only attributes from that relation. In this case it happens to produce the right answer, but does not always do so.

Fifth step: determine the normal form of the new relations. For each of R1 and R2 it holds that the local dependencies start from candidate keys, so both relations are in BCNF.

“Pure” functional languages are only pure with respect to some level of abstraction. It doesn’t matter what kind of guarantees your language gives if somebody pulls the power cord before your computation is finished¹. The real world is our eternal enemy². Language design, like law, is an adversarial system—a language can only be understood along with the context of what it can fight against and what it cannot.

A language’s being “pure” gives us guarantees about what you can do within the language that can be observed within the language. The meaning of “within the language” is built up on layers and layers of abstraction; if you pierce any of these layers, all bets are off. This includes everything from making the computer architecture run differently³ (which you can achieve on real chips with too much voltage or insufficient cooling) or having the operating system break its own abstractions (threads, virtual memory…) to twiddling with the garbage collector, hooking up a debugger or running in profiling mode. All these factors can affect how a program written in the purest of languages actually runs but, crucially, these are all actions explicitly outside the language.

In practice, unless your language is formalized in terms of a well-defined model of computation, the line between “within the language” and “outside the language” can be a bit fuzzy. Different languages draw it in different places. A language’s level of abstraction may or may not cover things like termination, runtime errors, asymptotic time/space performance, memory allocation, or wall clock execution time. Most aspects of computation, however, clearly fall on one side or another. Languages explicitly depend on the meanings of primitive operations and constructs as well as explicit effects like mutable state and I/O, while not exposing deficiencies in hardware behavior or problems with the laws of physics.

One of the fundamental assumptions that languages rely on is that the code being executed does not change except in ways explicitly allowed by the language. If you are using a pure language, there are only two possibilities:

• a function is modified or removed using facilities explicitly exposed by the language
• a function is modified or removed through some outside method like an external process editing the program’s binary directly

We would expect these to result in different behavior from the language:

• if code can be modified within the language, this can be managed in the same way as any other kind of effect from mutability through external I/O—pure languages either disallow this completely or have an effect system like Haskell’s IO type to manage it
• if code is modified outside the language, we’ve broken the fundamental abstraction on which everything is built; the program can now fail or behave in arbitrary ways without having any effect on whether the language is “pure”

There is no fundamental difference between mutable data and mutable code. The implementation of the two is different—especially on modern systems with a secure separation between executable and non-executable memory—but they are the same from a language design and semantics standpoint.

footnotes
¹ I can imagine pure distributed languages (Unison, perhaps?) which have guarantees for what happens if a subset of the machines they are running on fail. But you’re still screwed if somebody pulls all the plugs or if WWIII starts and all your data centers get nuked.

² Along with hardware companies, hardware, hardware drivers, operating systems, other software, the NSA and anybody writing real programs in our language.

³ If your physical computer doesn’t behave the way it should, well, there isn’t much you can do. You can try to compensate for hardware issues in software but anything you do is limited and it’s damn hard. People have actually explored using robust software to work around instability in hardware designs, but the approach has practical issues. In the wise words of James Mickens:

He discovered several papers that described software-assisted hardware recovery. The basic idea was simple: if hardware suffers more transient failures as it gets smaller, why not allow software to detect erroneous computations and re-execute them? This idea seemed promising until John realized THAT IT WAS THE WORST IDEA EVER. Modern software barely works when the hardware is correct, so relying on software to correct hardware errors is like asking Godzilla to prevent Mega-Godzilla from terrorizing Japan. THIS DOES NOT LEAD TO RISING PROPERTY VALUES IN TOKYO.

In general the existence of functional dependencies is regarded as a Bad Thing. They may be momentarily useful, but are almost guaranteed to bite your bum at the most inopportune moment, such as when you’re racing to meet a deadline.

In the ideal world, functional dependencies do not exist. In the real world, sometimes they are unavoidable. That said, you should strive to eliminate as many occurrences as possible, and in those cases remaining, ensure that the source header documents the dependencies thoroughly.

A lot of coders hate writing docs. That is because they approach the problem backwards. They should write the docs first, then write the code, and finally amend the docs to suit deviations the code took from the original spec.

A very good question, very important in practice, and often neglected in academic database classes because it is something that is hard and not so much fun to teach.

First note that there is of course no method that can guarantee a correct and complete result. We are just talking here about methods and heuristics that can help you find many of the dependencies in most of the cases in practice, but there is no guarantee that there will be no false positives or false negatives. Having said that, I will discuss two ways of looking for dependencies.

Method 1: Mining Example Instances of the Relation

Take one or more examples of instance of the relation and see which dependencies happen to hold there. Let us say, for example, we have the following (abstract) instance of a relation:

A  B  C  D 
----------- 
a1 b1 c1 d1 
a1 b1 c1 d1 
a2 b1 c1 d2 
a1 b2 c1 d2 

You can check which FDs hold in this instance, and you can even automate this. For example, the FD A -> B can be checked for table R with the SQL query:

SELECT A 
FROM R 
GROUP BY A 
HAVING COUNT (DISTINCT B) > 1; 

If any A values are returned, these violate the FD since they have more than one B value associated with them. If the result is empty then the FD holds. You can repeat this for all potential FDs , and determine which ones hold for this particular instance. In this case this includes the FDs AB->D and B->C. You ideally should repeat this for several representative instances, and then maintain only those dependencies that hold in all of them. Obviously this is a lot of work and can and should be automated. Also keep in mind that your set of FDs is likely to be redundant since it will include trival FDs and FDs that would follow logically from a subset of the found FDs. For example, in the given example you would also find AB->C, which follows from B->C.

Method 2: Entity-Relationship Analysis

This approach is the more practical one, but relies on your ER-modelling skills. It is based on determining the Entities, Relationships and Attributes that are modelled within the relation. Essentially you are making an ER model of all information in the relation under analysis. For illustration consider the following example where we have a relation with the following header.

(StudName, StudNr, StudAddr, CourseNr,  
 CourseName, Semester, Year, ProfName, Grade) 

This describes students, with their name, student number and address. It also describes courses, also with name and number, and editions of these courses in a particular year and semester. Finally it also contains the relationship between an edition of a course and the professor(s) teaching it. Other presented relationships are the one between students and course editions, with the obtained grade as an attribute of that relationship. Finally, there is the relationship between the edition of a course and the professors teaching it.

So how do we get the FDs? The first step is to identify the Entity Types, the sets of columns that identify them (there might be multiple) and their attributes. In this case:

• Student: {StudName}, {StudNR}
• attributes: StudAddr
• Course: {CourseNr}, {CourseName}
• Course Edition: {CourseNr, Semester, Year}
• Professor: {ProfName}

From this we can derive FDs with the following rules:

(ER2FD1) If an Entity Type has keys K1 and K2, then the FD K1 -> K2 holds

(ER2FD2) If an Entity Type has a key K and single-valued attribute A then FD K -> A holds

So in this case we derive:

1. StudName -> StudNR (ER2FD1)
2. StudNr -> StudName (ER2FD1)
3. StudNR -> StudAddr (ER2FD2)
4. CourseNr -> CourseName (ER2FD1)
5. CourseName -> CourseNr (ER2FD1)

The second step is to identify the Relationships, between which Entity Types they hold, and what attributes they have:

• Student-followed-Course-edition: (Student, Course Edition)
• attributes: Grade
• Prof-teaches-Course-edition: (Professor, Course Edition)

From this we derive FDs with the following rules:

(ER2FD3) If a Relationship is one-to-many or one-to-one, then there holds an FD from one of the keys of the many-Entity to one of the keys of the one-Entity.

(ER2FD4) If a Relationship has a single-valued attribute, then there holds an FD from a combination of the keys of the participating Entity Types to the attribute.

So in this case we derive:

1. StudNr, CourseNr, Semester, Year -> Grade (ER2FD4)
2. CourseNr, Semester, Year -> ProfName (ER2FD3)

Note: We assume here that each edition only has one professor, and so Prof-teaches-Course-Edition is indeed one-to-many.

For ER2FD3 and ER2FD4 it is sufficient that this is done for only one combination of keys, since the others are implied. So we could, but do not also derive the following FDs:

• StudName, CourseNr, Semester, Year -> Grade
• StudNr, CourseName, Semester, Year -> Grade
• StudName, CourseName, Semester, Year -> Grade

The rule ER2FD3 also has a variant for n-ary relationships where n>2, which is somewhat more complex. Consider, for example, a relationship that holds between Entity Types A, B and C. Then it should be checked if perhaps one of the participating Entity Types, say C, is functionally determined by the two others, i.e., if for every combination of A entity and B entity there is at most one C entity in this relationship with them. If that is the case, then an FD should be derived from a combination of keys of A and keys of B to the keys of C. An example of this would be a relation Supplies(Supplier, Part, Project) where each Project has for each Part at most one Supplier.

Your question could be rephrased, “is functional dependency symmetric?”

The answer is no in general.

There are cases in which A and B are each F.D. for each other:

• A and B are identical sets of attributes (that is, A is a subset of B and B is a subset of A).
• A and B are both individually unique in the relation (that is, they are not the same set of attributes, but they are both candidate keys). For each value in A, there can be exactly one value in B, and vice-versa.

But in general, functional dependency means that given a value of A, you can identify the row, and therefore you can unambiguously get the value of B in the same row.

If B is not a candidate key, and is not the same set of attributes as A, then there can be multiple rows with the same value of B for any given value of A.

Example: Name -> Social Security Number

Assume Social Security Number is a unique column, i.e. a candidate key. Each person has a unique SSN. Therefore if you know the SSN, you can get the person’s name in the respective row.

But Name is not a unique column. There can be multiple people with the same name, and each has a different SSN. Given a name, you cannot unambiguously know the SSN for a person with that name.

This terminology has nothing to do with functional programming or programming languages. Transitive functional dependencies arise in relational databases.

Let [math]R[/math] be a relation over a family of sets [math]\{ A_1, \ldots, A_k \}[/math], that is, [math]R \subset A_1 \cdots A_k[/math] – we call these sets attributes. Now suppose [math]X \subset \{ A_1, \ldots, A_k \}[/math] is a subfamily of attributes and [math]Y[/math] is one of the attributes in [math]\{ A_1, \ldots, A_k \}[/math]. Then we say that [math]X[/math] functionally determines [math]Y[/math] in [math]R[/math] if whenever we have two tuples in [math]R[/math] with the same values for the attributes in [math]X[/math], then they also have the same value for the attribute [math]Y[/math]. In other words, the values of the attributes in [math]X [/math]uniquely determinedly the value of the attribute [math]Y[/math]. Thus, when restricted to [math]X[/math], [math]R[/math] can be thought of as a function from the Cartesian product of the sets in [math]X[/math] to [math]Y[/math]. This is why one speaks of functional dependencies.

A simple example is a relation whose attributes are

• [math]N: [/math]Name of person
• [math]D: [/math]Date of birth
• [math]A: [/math]Address

Clearly, [math]N[/math] functionally determines [math]D[/math] – any person can only be born once.

A transitive functional dependency is a functional dependency that comes from the transitive closure of the “functionally determines” relation. If [math]A[/math] functionally determines [math]B[/math] (and [math]B[/math] does not functionally determine [math]A[/math]) and [math]B[/math] functionally determines [math]C[/math], then [math]A [/math]functionally determines [math]C[/math].

This is how i would do it, and i'll try my best to be clear in explaining it.
Let me know if you have further questions.

Problem: you have People(User) with Properties for Rental to other People(also a User).

So we have three tables USERS, PROPERTIES and RENTS/RENTALS, and they're related to each other.

Users ( they can either be a costumer or owner of a property or both).
Properties (Users can have many Properties, so the relation is 1:N ).
Rentals/Rents ( User(customer) can rent Properties, 1:N and Properties are available for Renting/Rentals 1:N).

I drew a scheme, hope it helps out:

You are not missing anything. Heath’s theorem only states that your decomposition will be lossless, but not that it will be dependency preserving. Indeed, it can be possible that among all the decompositions that would be possible by Heath’s theorem, none is actually dependency preserving. Consider for example the canonical example for the difference between 3NF and BCNF:

R(A, B, C) with F ={ AB -> C, C -> B }

Note that the candidate keys are: AB, AC.

It is in 3NF, but not in BCNF, since we have an FD C -> B where C is not a superkey. But splitting of that dependency will make you loose the dependency AB -> C.

Also note that Heath’s theorem does not tell you when to stop. Consider the following schema:

R(A, B, C) with F = { A -> B, A -> C }

You can split this according to Heath’s theorem, but is in fact already in BCNF, so splitting this further would not remove any redundancy.

It someone depends on the associated risks. If it’s in production and not bothering anyone, then cleaning it up has to add enough value that it overcomes the risks of touching it and introducing bugs. If you’re just nitpicking and want to add whitespace or reformat comments, then no. If there is some phenomenon or outright error in production that you’re trying to triage/investigate and the only way to understand this code or compartmentalize what is happening is to [incrementally?] refactor the code, then do what you have to do.

There’s also a case to be made for refactoring this if it’s considered to be technical debt by the team. If people are worried that there are bugs or dragons hidden within and there is a desire to do a preemptive strike on the code before it negatively effects production, then that’s the responsible thing to do.

Note that unit-tests play a big part here. Unit-tests are an indispensable tool to allow us to sometimes make or experiment with high-risk, dramatic changes to sensitive code from development and get a very reasonable gauge of the likeliness of breaking production. With excellent coverage, you can be reasonably certain that production is safe, but, even with “good” coverage, you can tell whether you can make a quick change and have them be good or whether, if after five successive waves of changes, you’re still struggling with weird issues that keep taking different forms and you should just circle back some other time. As engineers, our job is to gauge effort and risk, and unit-tests are a very big gun to have in your holster, to be used to gauge the ferocity of the unknown.

To check if the sets [math]S_1[/math] and [math]S_2[/math] of functional dependencies are equivalent you can check if every dependency in S1 logically follows from the dependencies in [math]S_2[/math], and vice versa.

Alternatively, you could check if [math]S_1^+=S_2^+[/math] where [math]S_1^+[/math] and [math]S_2^+[/math] are the closures of [math]S_1[/math] and [math]S_2[/math] (so the set of all dependencies that logically follow). It holds that [math]S_1[/math] and [math]S_2[/math] are equivalent if, and only if, [math]S_1^+=S_2^+[/math]. Note that [math]S_1^+[/math] and [math]S_2^+[/math] can get very large, but are in fact finite, so this can be an effective algorithm.

One possible way of checking if [math]X \to Y[/math] logically follows from a set of dependencies [math]S[/math] can be done by (1) computing the completion [math]X^+[/math] under [math]S[/math], i.e., the set of all attributes that functionally depend on [math]X[/math], and (2) checking if [math]Y[/math] is a subset of [math]X^+[/math]. If (2) holds then [math]X \to Y[/math] logically follows from [math]S[/math], if not, then not.

A->B

1)A functionally determines B

Or

2)B is functionally dependant on A

Given the value of A you will be able to uniquely identify B. A&B can be any subset of attributes.

Let's workout some examples

If we have a table with two attributes A&B

If T1(A)=T2(A) then

T1(B)=T2(B) where T1 &T2 are two tuples

Here a will always be associated with 1 & b with 2

If we have a table like this

We see that A->B. We also see that whenever A is repeating B is also repeating .This is data redundancy. So we delete attribute B and create a new table with attributes A &B . The attribute or attributes on left hand side (LHS) of A->B here A will act as primary key in new table.

Let's take a relation which does not satisfies Functional dependency.

B->C here we see that we have two different values of C for single value of B

A functional dependency is a particular type of database constraint, i.e., a restriction that should hold for an instance of a particular database schema if that instance is to be considered valid.

Specifically a functional dependency states that within a particular relation R a set of columns {A1, .., An} functionally determines a column B . This is usually denoted as A1 .. An -> B. The exact meaning of this is that in any valid instance of R it must hold that if two tuples / records agree on their values for all of A1, ..., An, then they must also agree on the value for B.

For example, assume R has columns {A, B, C, D}, then the functional dependency A B -> D states that if two tuples have the same A value and the same B value, then they also must have the same D value. The following instance of R satisfies this:

A B C D 
------- 
1 2 3 4 
1 2 5 4 
1 3 2 3 
1 3 3 3 

As you can see, all tuples with values (1, 2) for (A, B) agree on the value (4) for (D), and all tuples with values (1, 3) for (A, B) agree on the value (3) for (D).

An example of an instance that does not satisfy A B -> D is:

A B C D 
------- 
1 2 3 4 
1 2 5 6 

Here we have two tuples that agree on (A, B) but not on (D).

There can be several reasons why a functional dependency might hold for a particular relation.

One is that that the value in the dependent column can be computed or derived from the columns on which it depends. For example, the age of somebody can be derived from his or her birth date.

Another more common reason is that the dependent column describes a property of some entity that plays a role in the described relationship and is identified by the attributes on which it is dependent. For example, consider a relation DogOwners(OwnersID, DogID, OwnersAddress) where OwnersID identifies an dog owner, DogID identifies a dog of the owner and OwnersAddress is the address of the owner. Assume that the relation will contain a record for each dog a person owns. Then the address of the owner will be repeated for each dog owned, but it will for a particular owner always be the same. Thus, if two records agree on the OwnersName then they also agree on the OwnersAddress, and so the functional dependency OwnersID -> OwnersAddress holds.

Of course, the latter case is clearly a badly designed relation and causes unnecessary redundancy. It is the theory of database normalization, where functional dependencies play a key role, that explains how such redundancy is caused by certain combinations of functional dependencies and how this can be resolved.

Depends (could not help myself).

If you have the time and knowledge on how exactly to address all issues in a project and you are sure on stability and performance then by all means yes, having no dependency is the best way!!

Now if that is possible?

Unless you are creating a hardware platform from scratch and you are willing to write Basic Input Output System (BIOS) and then an Operating System and then all the required drivers (should you decide to go with modular kernel architecture) then an assembler and then a new compiler for at least a mid-to-low-level language (and so on and so forth), you will have to accept that parts of your code are by definition depended on code created by others.

In theory you can do all the above, of course not solo. Plus you will have to make available a serious budget.

So reality check: Define “Dependency”, estimate the trade-off(s) against already available code-base (do you really need to re-write Linux Kernel / Widows HAL etc). In most cases programmers refer to dependency as an include / import from a library (open / closed source no matter). If this is the actual query I will respond as follows: a library is a tool, so if you need it and you know how and when and why to use it, you will save time, budget and most probably will get a better result. As with any tool take a look at libraries’ reputation and comments / open issues by other users / developers. This should provide sufficient info to make the next step and test the tool stressing it to at least 10 times the load you have been told you need to handle. If your tests are considered successful, go for the lib, otherwise you may end-up with a never-ending-story (project infinity).

I agree with Richard Rombouts . Functional dependencies differ from framework to framework. Are you asking functional dependencies of a relation?? if so

A functional dependency (FD) on a relation schema R is a constraint X → Y, where X and Y are subsets of attributes of R.

Explanation: an FD is a relationship between an attribute "Y" and a determinant (1 or more other attributes) "X" such that for a given value of a determinant the value of the attribute is uniquely defined.

• X is a determinant
• X determines Y
• Y is functionally dependent on X
• X → Y
• X →Y is trivial if Y ⊆ X

Definition: An FD X → Y is satisfied in an instance r of R if for every pair of tuples, t and s: if t and s agree on all attributes in X then they must agree on all attributes in Y

A key constraint is a special kind of functional dependency: all attributes of relation occur on the right-hand side of the FD:

• SSN → SSN, Name, Address

Reference : Functional Dependencies

This is often deduced before a table is designed, just by knowledge of the data source.

But suppose the data is loaded in an SQL table without a primary key and we wish to deduce whether column A is functionally dependent on column B. Here’s one way:

select count(distinct B) from table;

select count(*) from (select distinct A,B from table) as t(A,B);

The first query gives the count of distinct values of column B. The second query gives the count of distinct values of tuples (A,B). We know that the latter is at least the former, because every distinct value of B will give rise to a different value of a tuple (A,B). If they are equal, though, we know there is at most one value of A for each value of B. Therefore, for the data in the table at least, we know that A depends on B.

Of course that is no guarantee that later rows added to the table would break this dependency.

This answer assumes the reader understands what functional dependencies are. If that is not the case, view this Quora thread for some background information first.

So what are their uses?

Functional dependencies are used in the design (or redesign) of relational databases to help eliminate redundancy (data duplication), therefore reducing the possibility of update anomalies.

Redundancy is eliminated through a process called normalization.

If a database schema is properly normalized, the following should hold true for all tables: all columns should be functionally dependent on the table’s primary key. Functional dependencies allow you to verify that this is true and if it is not, determine the steps to take to normalize your tables so that it will be true (without losing any data or losing any connections between data that is related).