DBMS - (17) functional dependency

DBMS - (17) functional dependency

Relational desgin by decomposition
- 'mega' relations + properties of the data
- system decomposes based on properties
- final set of relations satisfies normal form
(*normal form? no anomaly, no lost information)
- functional dependency -> BCNF
- multivalued dependency -> 4NF

Functional dependency is generally useful concept.
- Data storage ( compression )
- Reasoning about queries ( optimization )

Example.
Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
Apply(SSN, cName, state, date, major)

Suppose priority is determined by GPA.
= Two tuples with same GPA have same priority.
= GPA -> priority

Functional Dependency
임의의 tuple t, u ∈ R
t[A1,A2,...,An] = u[A1,A2,...,An] then t[B1,B2,...,Bm] = u[B1,B2,...,Bm]

어떤 테이블 R에 존재하는 필드들의 부분집합을 각각 X와 Y라고 할 때, X의 한 값이 Y에 속한 오직 하나의 값에만 사상될 경우에 "Y는 X에 함수 종속 (Y is functionally dependent on X)"이라고 하며, X→Y라고 표기한다.

Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
SSN -> sName
SSN -> address
HScode -> HSname
HScode -> HScity
(HSname, HScity) -> HScode
SSN -> GPA
GPA -> priority

Apply(SSN, cName, state, date, major)
cName -> date
(SSN, cName) -> major
SSN -> state

Funtional dependency and key
- Relation with no duplicate
- Suppose {A1,A2,...,An} -> all attributes
=> set of attributes가 all attributes를 결정한다면 그 set of attributes를 key라 한다.

Trivial Functional dependency
A* = {A1,A2,...,An}이라 하면,
A* -> B* and B*⊂A*

Non-trivial FD
A* -> B* and NOT B*⊂A*

Completely nontrivial FD
A* -> B* and A*∩B* = ∅

Rules for functional dependency
Splitting rule
A*->B1,B2,...,Bn then A*->B1, A*->B2, ..., A*->Bn

Combining Rule
A*->B1, A*->B2, ..., A*->Bn then A*->B1,B2,...,Bn

Transitive Rule
A*->B* and B*->C* then A*->C*

Closure of attribute
- given relation, FDs, set of attributes(A*)
- Find all B such that A* -> B

Closure Example
Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
SSN -> sName, address, GPA
GPA -> priority
HScode -> HSname, HScity

A+ = {SSN, HScode}
use SSN -> sName, address, GPA
GPA -> priority
HScode -> HSname, HScity
then
{SSN, HScode} -> {SSN, sName, address, HScode, HSname, HScity, GPA, priority} // all attr

Reference
https://www.youtube.com/watch?v=Mkm1h5AtsXI&list=PL6hGtHedy2Z4EkgY76QOcueU8lAC4o6c3&index=20