3NF和关系,函数依赖
问题描述:
的无损分解
我试图找到下面的关系相对于该3NF无损分解到函数依赖:3NF和关系,函数依赖
首先,我开始通过导出密钥从上面给出的函数依赖关系。我认为密钥如下:
{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%确定的。
如果有人能够就我可能出错的地方提出意见,我们将不胜感激。
答
你的答案是正确的:
所有按键实际上是LT,ET,TM,因为它们决定了所有其他的属性,并没有其他按键,因为他们没有子集满足这个属性。
依赖关系已经是关系的规范封面。
这个关系已经在3NF中,正是出于您陈述的原因。
请注意,如果您按照正确完成的第三范式的定义进行操作,则不需要检查是否存在传递函数依赖关系。
我们还可以注意到,原来的关系,而不是不BC范式,对于依赖ê→M,并通过应用分析算法,使之在BCNF产生分解:
R1 <(E M), {E → M}>
R2 <(E L T), {L T → E, E T → L}>
,它具有依赖关系TM→E丢失的属性。
所以我假设没有无损分解关系到BCNF,其中依赖关系被保留? – cp101020304
实际上,如果我们使用所有书中定义的最常用的算法(“分析”算法),依赖关系就会丢失。然而,还有其他算法在实践中未被使用,它们可能在BCNF中产生不同的分解。其中之一是[Tsou和Fisher](http://portal.acm.org/citation.cfm?doid=990511.990513),在这种情况下,它产生分解:R1(MLT),R2(ELT),它有更多的冗余,但保留了依赖关系。正如我所说的,这个算法并没有被使用,因为它产生了“自然”的分解,并且经常有太多的表格。 – Renzo
最后一点:存在一些模式,我们可以证明BCNF中不存在保留依赖关系的分解(这些在许多书中都有显示),但是一般来说,决定是否存在保留分解的函数依赖关系通用关系是一个NP难题(见[wikipedia](https://en.wikipedia.org/wiki/NP-hardness)),所以我们不知道任何多项式算法来解决这个问题。 – Renzo