The ORM Foundation

I am a student on Prof Jennifer Widom's course "Introduction to Databases" which has a section on "Relational Design Theory". This section contains videos that explain the method called "Functional Dependency Theory". (FDT)

Two of the course videos are available on YouTube: Functional Dependencies    and   Boyce Codd Normal Form

As presented, one starts a functional depencency analysis with something called a "mega relationship" and then one uses FDT to "decompose" the mega-relationship down to Boyce-Codd Normal Form or Fourth Normal Form.

Whilst I am sure that there are many questions related to FDT, here are two questions that come to my mind:

1. Where does the "mega-relation" come from in the first place?

2. What procedure is used to validate the mega-relation with the domain experts before one starts the decomposition process.

If anyone reading this thread has had any experience of using FDT to design a relational schema, it would be good to hear about the advantages and disadvantages.

Ken, I haven't heard the term mega-relation before, but I think I know what they mean by it. When commencing a relational model (the way I was taught it) one makes a list of all the "nouns" in the domain. If you regard this list as consisting entirely of the names of things that are somehow related to each other, you can see how you can treat it as a list of column names for a single enormous relation. The population of this relation is the cross-join of all the tables in the eventual fully-normalised schema. The implied exponential size of this population would appear to be the reason for naming it a "mega-relation"

By applying FD theory, this relation is progressively normalised into individual relations, undoing the implied cross-join.

Personally I think this approach stinks. We communicate with each other in facts, and natural speech consists of compounded lists of what are almost always elementary facts. To start with the elementary facts is much more natural, as you know. It doesn't require that we do away with all the knowledge of existing relations that are encoded in our manner of speech, as the "mega-relation" approach does.

The elementary form is almost isomorphic to 6NF, so to reduce this schema to an efficient relational implementation requires only a relatively easy mapping to 5NF, which is what RMap does (also my version of that as implemented in CQL). What's important is that this mapping-down (denormalisation) can be automated, which normalisation cannot.

Clifford,

Thanks for that explanation. Your idea of "list all the nouns" does seem to approximate to what Prof Widom is calling a "Mega-Relation" in the videos.
However she does also say "mega relations plus the properties of the data" so that seems to me a bit more than a list of nouns.

You can read some of Prof Widom's course notes about "Design by Decomposition" here. They say that the "Design by Decomposition" procedure is as follows:

Automatic decomposition
1. The database designer specifies mega-relations plus properties of the data
2. The system decomposes based on properties
Result: The final set of relations satisfies normal form -- guarantees no anomalies, no lost information

Properties and Normal Forms
    If the designer specifies functional dependencies (FDs) =>, the system produces Boyce-Codd Normal Form (BCNF)
    If the designer also specifies multivalued dependencies (MVDs) =>, the system produces Fourth Normal Form (4NF)

So, if your "list of nouns/columns" idea is right then it seems that with the FD approach, all that the designer has to do is to:

1: Get a list of all of the nouns in the Universe of Discourse.
2: Specify the functional dependencies amongst the nouns to generate BCNF.
3. Specify the multi-valued dependencies amongst the nouns to generate 4NF.

It would be interesting to hear from anyone who has actually followed this procedure with a moderately sized database.

Ken 

Ken Evans:

she does also say "mega relations plus the properties of the data"

To me that would mean that the data types are recorded (integer, date, string, lengths, etc), however her example "mega relation" doesn't have that. Instead it has some cardinality information... so perhaps that's what she means.

The standard ER modelling practise is to find dependencies progressively and apply relevant schema transforms as you find them, which is more-or-less what she shows (and I think this is common with other courseware presentations I've seen). The actual transform can be applied automatically in each case, so whether a human automaton follows the rules or a machine does, there's nothing new there. She seems however to require finding all FDs before applying the transforms, but in all the actual situations I've encountered, that would be almost entirely infeasible. One continues to discover new dependencies as the schema unfolds.

Either process will yield a normal form which "guarantees no anomalies, etc" if and only if all dependencies have actually been found. So the only difference with an all-at-once procedure is that it seems less likely to reach the best result.

So are you saying that, in your opinion "Functional Dependency Theory is not practical" ?

And if so, do you know of any examples or "case studies" that would help to support that proposition?

Ken

Ken Evans:

So are you saying that, in your opinion "Functional Dependency Theory is not practical" ?

Quite the contrary. But it cannot be "automated". It's possible to automate the schema transforms, in a tool that can accept instructions about where FDs lie, but the transforms are not the difficult part - finding the FDs is the difficult part.

The notion of elementary fact leads to the same result, but is much easier to learn and to apply, Rather than starting with noun soup and having to sort everything out, you start with no model and add elementary facts (checking each with examples) until everything is connected adequately, then constrain cardinalities and apply Rmap.

Boom! 5NF in one hit, and nobody even whispered "normalise". Nobody had to incant:

Columns must depend on the key, the whole key, and nothing but the key, so help me Codd!

Clifford Heath:

finding the FDs is the difficult part.

OK. So suppose that:

a) you are a database designer and you are going to design a database for a client.

b) you are "required" to use the Functional Dependency method. (Maybe because that is what you have been taught as "the way to design a database schema.")

c) you have some nice software that will automate the schema transforms.   

You know that your goal is to end up with a mega-relation.

Where do you start?

What are the steps?

Sigh. Again you mis-read and attribute thoughts that were not mine. It is never my goal, nor Widom's, to "end up with a mega-relation". She starts with one as a precursor to normalisation. It's this:

Apply(ID, name, campus, sport, HScode, HScity)

If I use FD, I would also start here, and follow the procedure she outlines - but without using the (automated schema transform) tool she makes elliptical reference to. Every FD must be found by experience and intuition, being tested by reference to the business domain. There is no way to automate this. The skills are taught in courses like this one, and mastered only through long experience.

However, I would only work that way in order to illustrate the difficulties presented by the normalisation abstractions, which must be mastered before one may be considered competent; whereas the fact-oriented approach avoids the problem from the start by the simple action of not creating the mega-relation to begin with.

Clifford Heath:

Sigh. Again you mis-read and attribute thoughts that were not mine. It is never my goal, nor Widom's, to "end up with a mega-relation". She starts with one as a precursor to normalisation

Well maybe my wording was a little clumsy and maybe it is the case that I misunderstand what a mega relation is.

Earlier in this thread you said "finding the FDs is the difficult part" 

So when I said "end-up with a mega-relation" , I was intending to say that:
 If the FD based normalisation procedure "starts with a mega-relation" ( and it seems that that is the case that we are discussing).
Then: The mega-relation must come from somewhere. It does not just appear out of thin air.

So I was inferring that there must be some previous process that "ends up with a mega relation" to provide the input for the FD analysis process.

In other words, I was asking you describe either your experience or your knowledge of the procedures that others have used to try to understand what steps are required to go from a blank sheet of paper to a paper on which the mega relation is written down such that all concerned say "Yes - that's it! That is the mega-relation. Now you can start the decomposition process."

You did say:

Clifford Heath:

Every FD must be found by experience and intuition, being tested by reference to the business domain.

On the other hand, maybe I really do misunderstand the term "mega relation".  
What the term brings to my mind is a very large single relation with maybe hundreds of nouns - but maybe that is not it?
You mentioned "Apply(ID,name,campus,sport,HScode,HScity) as being a mega-relation.

If that is indeed the case then I must say that six things in a set of brackets does not seem very "mega" to me.
I thought that the "Apply" relation was just a simple example of the principle rather than a real example of a "mega-relation".

However, if Apply is a mega relation, then it would appear that in any substantial universe of discourse there must be hundreds - (maybe thousands) of such mega relations and when put together they collectively represent the universe of discourse. Which brings me back to my question (slightly modified):

Whether there is just one mega relation or a collection of mega relations, where do the mega-relations come from? By what process are they created?

Ken Evans:

The mega-relation must come from somewhere. It does not just appear out of thin air

I see, that does make more sense.

The mega-relation comes from the idea that everything we care about must be related in some way to all the other things. At this starting point, there is no further structure. It's all one big wash, like in an Oriental religion where everything equally is god. The list of "everything we care about" is extracted by finding every noun and every characteristic (unary FT) of every noun.

In the didactic example at question, there are just six things, so it doesn't seem very "mega". However if you do this in a real business, you have many hundred of nouns. You also tend to have a number of sets of synonyms which gradually resolve as you discover the one-to-ones. It's quite common to miss things, either by actual oversight, or because you think you have a synonym. You'll also have a number of nouns that, on reflection, either don't really exist, or have a relation to other things which is not actually relevant in order to solve the business problem. So the normalisation procedure is never as clear-cut as a didactic example woud lead you to believe. In fact, to construct such an example which demonstrates the various steps of normalisation is quite difficult, and many text-books merely copy examples from one another with minor changes. That is, they are deliberately constructed cases which bear little relation to real life.

It's these complications that support my claim that fact orientation is always preferable to the FD method.

Clifford Heath:

The mega-relation comes from the idea that everything we care about must be related in some way to all the other things.

Clifford Heath:

The list of "everything we care about" is extracted by finding every noun and every characteristic (unary FT) of every noun.

Well, we seem to be getting closer to what seems to me to be a "practical" answer to the question: "Where do the mega relations come from?"

However, I feel that your statement may still be a bit too abstract for many people.(It certainly is for me because it does not tell me what I have to do.).

If you said to me "Go and find every noun and every characteristic (unary FT) of every noun" I'm still not sure of how you envisage that this would be done.

So I'm still wondering exactly what activities a functional dependency oriented database schema designer would have to undertake to "end up with" the mega-relation. 

For example, does the designer just arrange a series of interviews and ask each interviewee a series of questions?
If so, what would those questions be?

For example asking a domain expert to "Please write down your mega relation" is likely to be met with a blank stare.

So what questions are asked? Does the designer simply ask the domain expert to "write down a list of the nouns that you use in your part of the business?" (Activity 1 - Get the Nouns) or is there something else?

And sorry, but I'm not quite sure what you mean by "every characteristic (unary FT) of every noun"

It would help a lot if you explained what questions the designer would ask of a domain expert to get him or her to tell you about  "every characteristic (unary FT) of each of the nouns on the list made during Activity 1?"
 

Ken Evans:

does the designer just arrange a series of interviews and ask each interviewee a series of questions?

I don't usually do it that way, but some people do. You just ask people "tell me about your business" or "tell me how your business works" or even just "tell me all the things that are relevant to your business" and they start talking. It's easier (when you know how) to handle this with facts, but this method does work.

Normally however I start with whatever documents and/or software are being used to manage the business already. Every heading, field on a screen, or in a database, is a candidate noun. A check-box (any yes/no basically) is probably a unary (such as Invoice is paid), but you have to check that those don't reflect a binary FT.

But now I'm the one who is puzzled. Surely you have experienced all this many times in your long career? Do you have a particular goal in mind for this line of questioning? What I've said about ERD is contained in most undergraduate coursework...

Thanks for your answers Clifford. Just what I was trying to get to.

Yes, it is true that over the years , I have interviewed many people about their information systems requirements. However, I have never approached an organisation with a view to identifying a mega-relation. So, the intention behind my questions has been to find out in what way the activity called "Find the mega relation" is different from the methods used by other approaches.

From what you have said, I conclude that the "data collection" phase of a functional dependency(FD) based analysis is different from the ORM approach in that the FD analyst asks questions that will elicit a list of nouns, whereas the ORM analyst asks questions that will elicit a set of facts and their constraints.

So with functional dependency, the hard work starts after you have established mega relation whereas with ORM, once you have agreed and validated the facts then you are finished.

Do you agree with this characterisation of the differences? 

Ken Evans:

So with functional dependency, the hard work starts after you have established mega relation whereas with ORM, once you have agreed and validated the facts then you are finished.

That would seem to be the result of applying the FD approach the way it's taught, but as i said before, that doesn't happen, at least not in my experience. What happens instead is lots of little rounds of finding more nouns and normalising them, finding more and re-normalising, etc. It's a lot more work, because you have to revisit related parts of the schema on every discovery cycle (and modify any affected program which uses that schema); whereas an FBM tool just automatically gives you a new 5NF schema. I also want to get to where the programs are not affected by changes due to re-normalisation; if the facts they want are still present in the new schema, the program will still work. But as far as I know no-one has made that possible yet.