7

Is it possible to get rid of so-called 'Spurious Tuples' completely?

For example: In this example from a textbook, there is an original table:

enter image description here

I don't see anything wrong with the two projections of it:

enter image description here

But their join is still generating spurious tuples:

enter image description here

(These figures from ToddEverett's answer.]

9

This is a great question. Normalization beyond BCNF is extremely hard to understand. Hopefully I can provide an answer that makes sense. I struggled with these concepts for over 20 years before finally making sense of them thanks to Fabian Pascal's Practical Database Foundation Series.

The example provided is an EmpRoleProj R-table that looks like so:

enter image description here

It then goes on to show projections of the original EmpRoleProj R-table like so:

enter image description here

The reason you don't see anything wrong with the base tables Table 1 and Table 2 is that you aren't considering the dependency rules (in this case multivalued dependency (MVD) rules) defined in the business model describing the business rules. If we assume for the sake of example there are no MVDs defined in the business rules then EmpRoleProj is in 5NF despite the "appearance" of redundancies. It appears for example that the information that Smith is a designer is stored redundantly. It also appears that the information that a designer is needed on the Amazon project is stored redundantly. While this appears to be the case, by learning that in fact these are not MVDs, what is actually the case is that Smith happens to be a designer on a few projects, but it is not a fact that Smith is a designer and thus that fact should not be inferred. When table 1 and table 2 are joined, the result:

enter image description here

shows Jones to be a designer on the Nile project but we know that is not the case.

Let us assume instead the business model did say there were MVDs of empName-->>role and role-->>projName. In this case, what those MVDs mean is that if an employee plays a role, and if that role is on a project, by definition that employee plays that role on that project. In this example, that same EmpRoleProj table is now not in 5NF and now does suffer from redundancy. Now, the facts that Smith is a designer and there is a need for a designer on the Amazon project are stored redundantly as those facts could be inferred from joining Table 1 and Table 2! Likewise, taking the join of Table 1 and Table 2 now does not result in a spurious tuple as the inference that Jones is a designer on the Nile project is a fact now based upon the business rules defined by the MVDs.

This is why you cannot assess the normal form of any R-table without knowing the dependencies and the defined key. Making any assumption, even one that seems to you to make sense, can be dangerous. If you are ever asked what normal form an R-Table is in, you must ask for the dependencies to assess. In addition to Fabian's series of papers, Chris Date's works provide the best information available on normalization theory.

| improve this answer | |
3

A spurious tuple is what you may get if rows in a database are joined incorrectly. This may cause a 'new but spurious' row to be created due to the error.

In your example from the book Databases Illuminated Third Edition by Ricardo and Urban, they show this example:

As you can see, the splitting of the records in 6.8(B) into two tables, but not maintaining the meaning of the data causes the join in 6.8(C) to join Jones Designer to both Amazon (which is correct) and to Nile (which is spurious).

So, join carefully. The join that caused the error in 6.8(C) was due to losing track of the relationships between the data. Easy to do if you do not include the original join criteria.

If you want a slide show discussion here is an example from:

http://classes.engr.oregonstate.edu/eecs/winter2012/cs440/slides/slide9.pdf

   Design relation schemas to be joined with equality conditions 
        on attributes that are appropriately related.

       - Guarantees that no spurious tuples are generated

    Avoid relations that contain matching attributes 
        that are not (foreign key, primary key) combinations
| improve this answer | |
3

In the decomposition of a relational schema a "spurious tuple" is just a hypothetical symptom of lost information. What it means is that some dependency represented in a given relation will be lost as a result of splitting that relation into two or more components. Whether that's a problem you need to solve or not depends on how important the lost dependency is to you.

In the example you refer to, the EmpRoleProj table tells us what projects each employee is working on. In the Table1, Table2 design that information is lost - we can no longer tell that Jones works only on the Amazon project and not on the Nile project.

As a database designer you need to consider what information or integrity has been lost and then decide what action to take: change the design, add extra integrity constraints or decide that the new decomposition is actually an improvement on what went before it.

| improve this answer | |
0

If relation R equals R1 JOIN R2 JOIN ... then we can use R1 JOIN R2 JOIN ... instead of R. Obviously. But R1, R2, ... will be projections of R. Whereas if we take projections R1', R2', ... of R where R does not equal R1' JOIN R2' JOIN ... then we can't use R1' JOIN R2' JOIN ... instead of using R. Obviously. But R1' JOIN R2' JOIN ... will be like R plus some other tuples. They are "spurious tuples" compared to the value of R and R1 JOIN R2 JOIN ... . But they belong in R1' JOIN R2' JOIN ... . That just isn't R. To "get rid of the spurious tuples" just don't use R1' JOIN R2' JOIN ... for R. But then, why would you? Only if you thought that any old projections of R JOIN back to R. But they don't. But then, why would they?

So your question is oddly phrased. We want to replace a table that is the join of some others by those others. We don't want to replace a table that is not the join of some others by those others. So we can always "get rid of the spurious tuples" by not doing that.

Normalization is about replacing a table that is the join of some others by those others. When R = R1 JOIN R2 JOIN ... we say that a JD (join dependency) holds in R. Contrary to received wisdom, it's very easy to see JDs if we are looking and we know what our tables mean. When R holds tuples where "...A1a...A1b... AND ...A2a...A2b... AND ...", it is the join of R1, R2, ... on respective attribute sets {A1a, A1b, ...}, {A2a, A2b, ...}, ... with respective meanings "...A1a...A1b...", "...A2a...A2b...", ... . We naturally use R1, R2, ... most of the time from the start of design. Received wisdom is also that JDs not accompanying FDs (functional dependencies) are rare. They are, but only because most JDs are so obvious that our initial designs avoid them. They are "hard to find" only because they are so easy to find. (It is a bit more complicated to not decompose per JDs that don't cause problems.)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy