Real Computer Science begins where we almost stop reading ...: Lossless-join Decomposition

Monday, 20 May 2013

Lossless-join Decomposition

Can also be called Nonadditive. If you decompose a relation $R$ into relations $R_1$ and $R_2$ you will guarantee a Lossless-Join if $R_1$ ⋈ $R_2$ = $R$ .
Let $R$ be a relation schema.
Let $F$ be a set of functional dependencies on $R$ .
Let $R_1$ and $R_2$ form a decomposition of $R$ .
The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in $F$ ⁺(where $F$ ⁺ stands for the closure for every attribute in $F$ )

$R_1$ ∩ $R_2$ → $R_1 - R_2$
$R_1$ ∩ $R_2$ → $R_2 - R_1$

Example

Let $R = (A, B, C, D)$ be the relation schema, with $A$ , $B$ , $C$ and $D$ attributes.
Let $F = \{ A \rightarrow BC \}$ be the set of functional dependencies.
Decomposition into $R_1 = (A, B, C)$ and $R_2 = (A, D)$ is lossless under $F$ because $R_1 \cap R_2 = (A)$ and $A \rightarrow BC$ so $R_1 \cap R_2 \rightarrow R_1 - R_2$ .

No comments:

Inspiring Quotes

An inspiring quote may be just what you need to turn your day around. Here are some of the most inspiring quotes ever spoken or written.

I hated every minute of training, but I said, “Don’t quit. Suffer now and live the rest of your life as a champion.”

–Muhammad Ali

“You can have anything you want if you are willing to give up the belief that you can’t have it.”
–Robert Anthony

“There is no man living that can not do more than he thinks he can.”

–Henry Ford

“The best way to predict the future is to create it.”

–Dr. Forrest C. Shaklee

“It’s not about time, it’s about choices. How are you spending your choices?”

–Beverly Adamo

“Success…seems to be connected with action. Successful people keep moving. They make mistakes, but they don’t quit.”
–Conrad Hilton

“Destiny is not a matter of chance; it’s a matter of choice.”

–Anonymous

“The future belongs to those who believe in the beauty of their dreams.”
–Eleanor Roosevelt

“The quality of a person’s life is in direct proportion to their commitment to excellence, regardless of their chosen field of endeavor.”
–Vince Lombardi

“It is never too late to be what you might have been.”
–George Eliot

“Do not let what you can not do; interfere with what you can do.”
–John Wooden

“One man with courage makes a majority.”
–Andrew Jackson

“Failure is the opportunity to begin again more intelligently.”
–Henry Ford

“Try not to become a man of success but rather try to become a man of value.”
–Albert Einstein

“The mind is its own place, and in itself can make a heaven of Hell, a hell of Heaven.”

–John Milton

"If u are student, working and preparing give a little extra effort after regular work. A small sacrifice of TV time, fun time, or facebook time can bring a lot of better things to life than you ever imagined."

-- Naam likhna jaroori nai samajhta.

Thank you for reading, be sure to pass this along!

Monday, 20 May 2013

Lossless-join Decomposition

Example

No comments:

Post a Comment