这种分解依赖性是否得到保留? [英] Is this decomposition dependency preserving?

问题描述

我试图弄清楚如何查看分解是否保留了依赖关系.关系为:R(ABCDEF)，并且具有以下FD.AB-> CE，C-> EB，E-> D，C->D.然后将关系拆分为:R1(BF)，R2(ACB)和R3(CDE).这种依赖关系得到保留吗?

I'm trying to figure out how to see if a decomposition is dependency preserving or not. The relation is: R(ABCDEF)and have the following FD's. AB -> CE,C -> EB,E -> D,C -> D. We then split the relation into: R1(BF), R2(ACB) and R3(CDE). Is this dependency preserving?

我的印象是，要计算此结果，您需要对FD的所有左侧进行封闭.这给出了:

I was under the impression that to calculate this, you do a closure on all of the left sides of the FD's. This give:

AB + = ABCEBD，其中包括AB-> CE

AB+ = ABCEBD which includes AB -> CE

C + = CEBD，其中包括FD

C+ = CEBD which includes the FD's

E + = ED，其中包括E-> D

E+ = ED which include E->D

因此，在我的世界中，这就是保持依赖关系.但是，根据标记，答案是不是.对于这个概念，我在做什么错和/或误解?

So in my world, this is dependency preserving. However, according to the markings the answer is that it isn't. What am I doing wrong and/or misunderstanding about the concept?

为澄清起见，我确实了解到某些依赖关系在每个分解的关系中均不成立.例如AB-> E，因为我们找不到包含这三个元素的关系.但是，尽管如此，由于AB的闭包仍然包括E，因此无论如何它都将被视为保持依赖关系.这是我出问题的地方吗?对该概念的解释(我的教科书非常简短)将不胜感激.

To clarify, I do understand that some of the dependencies doesn't hold in each decomposed relation. For example AB -> E since we can't find a relation which includes these three together. However, I though that since the closure of AB still includes E it would be considered dependency preserving anyway. Is this where I go wrong? An explanation of the concept (my textbook is VERY brief) would be greatly appreciated.

推荐答案

简单:您是正确的，依赖项已保留.

In brief: you are correct, the dependencies are preserved.

详细解释.

要定义依赖项保留的概念，我们首先需要定义一组功能依赖项的投影的概念:

To define the concept of dependencies preservation first we need to define the concept of projection of a set of functional dependencies:

给出具有一组依赖项F的架构R(T)，并给定T的子集T _i ，则F在T _{i上的投影}定义为:

Given a schema R(T) with a set of dependencies F, and given a subset T_i of T, the projection of F on T_i is defined as:

π _{T i} = {X→Y∈F ⁺ |X，Y⊆T _i }

π_Ti = { X → Y ∈ F⁺ | X, Y ⊆ T_i}

请注意，我们需要考虑F ⁺ 的依赖关系(F依赖关系的闭包)，而不仅仅是F上的依赖.

Note that we need to consider the dependencies of F⁺ (the closure of the dependency of F), not only those on F.

我们现在可以定义依赖项保留的属性以进行分解:

We can now define the property of dependencies preservation for a decomposition:

A分解ρ= {R ₁ (T ₁ )，...，R _n (T _{n T i} (F)≡F时，具有依存关系F的R(T)的R(T)保留依存关系.

A decomposition ρ = {R₁(T₁), ..., R_n(T_n)} of R(T) with dependencies F preserves the dependencies if and only if ∪ π_Ti(F) ≡ F.

这可以通过应用至少在1983年开始在书中描述的算法来正式验证(例如，参见:Ullman，J.(1983).Database Systems Principles.Computer Science Press，Rockville，Maryland)，该算法可以计算多项式时间，一组属性相对于依赖项的投影是闭合的.

This can be formally verified by applying an algorithm, described in books at least from 1983 (see for instance: Ullman, J. (1983). Principles of Database Systems. Computer Science Press, Rockville, Maryland), that computes in a polynomial time the closure of a set of attributes with respect to a projection of dependencies.

在实践中，为了检查示例中是否保留了依赖项，无需应用该算法，但足以计算出依赖项的规范范围:

In practice, in order to check that the dependencies are preserved in your example there is no need to apply that algorithm, but it is sufficient to compute a canonical cover of the dependencies:

A B → C
C → B
C → E
E → D

从中我们可以看到每个依赖关系都包含在分解的关系中，因此我们可以得出结论，这些依赖关系得到保留.

From it we can see that each dependency is contained in a decomposed relation, so we can conclude that the dependencies are preserved.

请注意，在对一组依赖项进行推理时，总是可以对它们进行规范的解释.

Note that, when reasoning on a set of dependencies, it is always convenient to reason on a canonical cover of them.

这篇关于这种分解依赖性是否得到保留?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！