3NF和关系,函数依赖

问题描述:

的无损分解

我试图找到下面的关系相对于该3NF无损分解到函数依赖:3NF和关系,函数依赖

enter image description here

首先,我开始通过导出密钥从上面给出的函数依赖关系。我认为密钥如下:

{L,T},{E,T}和{T,M},因为关系中的所有属性都可以使用这些密钥中的任何一个来获得。

现在,3NF的,我熟悉的定义是:

A relation schema R is in 3NF if, whenever a function dependency X -> A holds in R, either 
(a) X is a superkey of R, or 
(b) A is a prime attribute of R. 

如果我们将此运用到这个问题给出的文件描述符那么下列成立:

  • LT - > E满足(a)因为LT是关键(因此是超级关键)。
  • ET - > L满足(a)因为ET是一个关键(因此是一个超级键)。 TM - > E满足(a),因为TM是关键(因此是超级关键词)。
  • E-> M满足(b),因为M是一个主要属性。

鉴于此,如何获得关于函数依赖关系的3NF无损分解?我怀疑我可能是错误的,因为我认为这个关系是在3NF中,因为存在传递依赖关系,但不是100%确定的。

如果有人能够就我可能出错的地方提出意见,我们将不胜感激。

你的答案是正确的:

  1. 所有按键实际上是LT,ET,TM,因为它们决定了所有其他的属性,并没有其他按键,因为他们没有子集满足这个属性。

  2. 依赖关系已经是关系的规范封面。

  3. 这个关系已经在3NF中,正是出于您陈述的原因。

请注意,如果您按照正确完成的第三范式的定义进行操作,则不需要检查是否存在传递函数依赖关系。

我们还可以注意到,原来的关系,而不是不BC范式,对于依赖ê→M,并通过应用分析算法,使之在BCNF产生分解:

R1 <(E M), {E → M}> 

R2 <(E L T), {L T → E, E T → L}> 

,它具有依赖关系TM→E丢失的属性。

+0

所以我假设没有无损分解关系到BCNF,其中依赖关系被保留? – cp101020304

+1

实际上,如果我们使用所有书中定义的最常用的算法(“分析”算法),依赖关系就会丢失。然而,还有其他算法在实践中未被使用,它们可能在BCNF中产生不同的分解。其中之一是[Tsou和Fisher](http://portal.acm.org/citation.cfm?doid=990511.990513),在这种情况下,它产生分解:R1(MLT),R2(ELT),它有更多的冗余,但保留了依赖关系。正如我所说的,这个算法并没有被使用,因为它产生了“自然”的分解,并且经常有太多的表格。 – Renzo

+0

最后一点:存在一些模式,我们可以证明BCNF中不存在保留依赖关系的分解(这些在许多书中都有显示),但是一般来说,决定是否存在保留分解的函数依赖关系通用关系是一个NP难题(见[wikipedia](https://en.wikipedia.org/wiki/NP-hardness)),所以我们不知道任何多项式算法来解决这个问题。 – Renzo