Қатынастық деректер базасындағы функционалды тәуелділіктер

Кіріспе

Реляциялық деректер қоры теориясының түсінігі
Реляциялық деректер қоры теориясындағы түсінік

Реляциялық деректер қоры теориясында функционалдық тәуелділік – деректер қорынан алынған қатынастағы екі атрибут жиыны арасындағы шектеу. Басқаша айтқанда, функционалдық тәуелділік – қатынастағы екі атрибут арасындағы шектеу. R қатынасы және атрибуттар жиыны берілген жағдайда, X, Y-ді функционалдық түрде анықтайды (X → Y деп жазылады), егер және тек қана R-дегі әрбір X мәні R-дегі дәл бір Y мәнімен байланысты болса; сонда R функционалдық тәуелділікті X → Y қанағаттандырады деп айтылады. Балама ретінде, проекция функция болып табылады, яғни Y – X-тің функциясы. Қарапайым тілмен айтқанда, егер X атрибуттарының мәндері белгілі болса (мысалы, олар x болсын), онда x-ке сәйкес келетін Y атрибуттарының мәндерін x-ті қамтитын R кез келген түйірден іздеу арқылы анықтауға болады. Көбінесе X – детерминант жиыны, ал Y – тәуелді жиынтығы деп аталады. Функционалдық тәуелділік FD: X → Y егер Y, X-тің ішкі жиыны болса, тривиалды деп аталады. Басқаша айтқанда, FD: X → Y тәуелділігі Y мәндері X мәндерімен анықталады дегенді білдіреді. Бірдей X мәндеріне ие екі түйір міндетті түрде бірдей Y мәндеріне ие болады. Функционалдық тәуелділіктерді анықтау – реляциялық модельде деректер қорын жобалаудың және деректер қорын нормалау мен денормалдаудың маңызды бөлігі. Функционалдық тәуелділіктердің қарапайым қолданылуы – Хит теоремасы; ол R қатынасы U атрибуттар жиынында және функционалдық тәуелділікті X → Y қанағаттандыратын жағдайда, жоғалтусыз біріктіру қасиетіне ие екі қатынасқа, атап айтқанда Z = U − XY – қалған атрибуттар болып бөлінеді. (Атрибуттар жиындарының біріктірілуі деректер қоры теориясында олардың тікелей жазылуымен белгіленеді.) Бұл контексте маңызды түсінік – үміткер кілт, ол қатынастағы барлық атрибуттарды функционалдық түрде анықтайтын атрибуттардың ең кішкентай жиыны ретінде анықталады. Функционалдық тәуелділіктер, атрибут домендерімен бірге, пайдаланушы доменіне сәйкес келмейтін деректерді жүйеден барынша шығарып тастау үшін шектеулерді жасау мақсатымен таңдалады. Функционалдық тәуелділіктер үшін логикалық импликация ұғымы келесідей анықталады: егер кез келген R қатынасы барлық тәуелділіктерді қанағаттандырса, функционалдық тәуелділіктер жиыны басқа тәуелділіктер жиынын логикалық түрде білдіреді, сондай-ақ ол барлық тәуелділіктерді қанағаттандырады; бұл әдетте жазылады. Функционалдық тәуелділіктер үшін логикалық импликация ұғымы Армстронг аксиомалары деп аталатын дұрыс және толық шекті аксиоматизацияны ұсынады.

In relational database theory, a functional dependency is a constraint between two sets of attributes in a relation from a database. In other words, a functional dependency is a constraint between two attributes in a relation. Given a relation R and sets of attributes , X is said to functionally determine Y (written X → Y) if and only if each X value in R is associated with precisely one Y value in R; R is then said to satisfy the functional dependency X → Y. Equivalently, the projection is a function, i. e. Y is a function of X. In simple words, if the values for the X attributes are known (say they are x), then the values for the Y attributes corresponding to x can be determined by looking them up in any tuple of R containing x. Customarily X is called the determinant set and Y the dependent set. A functional dependency FD: X → Y is called trivial if Y is a subset of X. In other words, a dependency FD: X → Y means that the values of Y are determined by the values of X. Two tuples sharing the same values of X will necessarily have the same values of Y. The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization. A simple application of functional dependencies is Heath's theorem; it says that a relation R over an attribute set U and satisfying a functional dependency X → Y can be safely split in two relations having the lossless join decomposition property, namely into where Z = U − XY are the rest of the attributes. (Unions of attribute sets are customarily denoted by there juxtapositions in database theory.) An important notion in this context is a candidate key, defined as a minimal set of attributes that functionally determine all of the attributes in a relation. The functional dependencies, along with the attribute domains, are selected so as to generate constraints that would exclude as much data inappropriate to the user domain from the system as possible. A notion of logical implication is defined for functional dependencies in the following way: a set of functional dependencies logically implies another set of dependencies , if any relation R satisfying all dependencies from also satisfies all dependencies from ; this is usually written The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms.

Көліктер

Мысалы, көліктерді және олардың қозғалтқыштарының қуатын қадағалау үшін жүйе жобалап жатқаныңызды айталық. Әрбір көлік құралының бірегей идентификациялық нөмірі (VIN) болады. VIN → EngineCapacity деп жазамыз, себебі бір көліктің қозғалтқышының бірнеше қуаты болуы мүмкін емес. (Осы жағдайда көліктерде тек бір ғана қозғалтқыш бар деп есептейміз.) Ал, EngineCapacity → VIN жарамсыз, өйткені бірдей қозғалтқыш қуатымен көптеген көліктер болуы мүмкін. Бұл функционалдық тәуелділік EngineCapacity атрибутын VIN кандидат кілтімен бірге бір қатынасқа орналастыруға ұсыныс береді. Дегенмен, мұндай жағдай әрқашан орынды болмайды. Мысалы, егер бұл функционалдық тәуелділік VIN → VehicleModel және VehicleModel → EngineCapacity транзитивті функционалдық тәуелділіктері нәтижесінде туындаса, онда бұл нормаланған қатынасқа алып келмейді.

Атрибуттар жиынтығын жабу

X атрибуттары жиынының жабылуы – X арқылы функционалды түрде анықталатын барлық атрибуттардың X+ жиыны.

Мұқабалар

Анықтама: Егер кез келген FD жиыны + -дан шығарыла алса, онда + қаптама деп аталады, егер + ⊆ + болса. Кез келген функциялық тәуелділіктер жиынының каноникалық қаптамасы болады.

Екі FD жиынтығының теңдігі

Функционалдық тәуелділіктердің екі жиыны және схема бойынша егер + = + болса, ≡ деп жазылады. Егер ≡ болса, онда бірі – екіншісі үшін жамылғы болады, және керісінше. Яғни, эквивалентті функционалдық тәуелділіктер жиындары бір-бірін жамылғы деп аталады.

Хит теоремасы

Функционалдық тәуелділіктердің маңызды қасиеті (тікелей қолданылуға мүмкіндік беретін) – егер R қатынасы U атрибуттар жиынынан аталған бағандармен белгіленген болса және R кейбір функционалдық тәуелділікті қанағаттандырса, онда Z = U − XY. Түсініктірек айтқанда, егер R қатынасында X → Y функционалдық тәуелділігі орындалса, онда қатынасты X бағанымен бірге екі қатынасқа бөлуге болады (ол кілт болып табылады), екі бөлігін қайта біріктіргенде ешқандай дерек жоғалмайтынын қамтамасыз ету, яғни функционалдық тәуелділік R қатынасын екі кіші қатынасқа жоғалмайтын қосылу арқылы ыдыратудың оңай жолын ұсынады. Бұл факт кейде Хитс теоремасы деп аталады; ол деректер базасы теориясының алғашқы нәтижелерінің бірі. Хитс теоремасы, тиімді түрде, Y мәндерін үлкен R қатынасынан алып, оларды жеке қатынасқа сақтауға болады, онда X үшін қатарда мән қайталанбайды және ол X бойынша кілттелген Y үшін анықтамалық кесте болып табылады, сондықтан әр X үшін Y-ті жаңарту үшін тек бір орын бар, ал "үлкен" R қатынасында әр X-тің әртүрлі көшірмелері болуы мүмкін, олардың әрқайсысы Y-тің өз көшірмесімен жаңартулар кезінде синхронды түрде сақталуын қажет етеді. (Бұл артықшылықты жою OLTP контекстінде пайдалы, онда көптеген өзгерістер күтіледі, бірақ OLAP контекстінде олай емес, себебі ол негізінен сұраныстарды қамтиды.) Хитс ыдырауы үлкен кестедегі қалған бөлігінде X-ті сыртқы кілт ретінде қалдырады. Бірақ функционалдық тәуелділіктерді шетелдік кілттердің формализмі болып табылатын кіріктіру тәуелділіктерімен шатастырмау керек; олар нормализация үшін қолданылса да, функционалдық тәуелділіктер бір қатынаста (схема) шектеулерді білдіреді, ал кіріктіру тәуелділіктері деректер базасының схемасындағы қатынас схемалары арасындағы шектеулерді білдіреді. Сонымен қатар, екі түсінік тәуелділіктерді жіктеуде қиылыспайды: функционалдық тәуелділіктер теңдік тудыратын тәуелділіктер, ал кіріктіру тәуелділіктері – туплдарды тудыратын тәуелділіктер. Қатынас схемасын ыдыратудан (нормалданудан) кейін референциалдық шектеулерді сақтау үшін жаңа формализм, яғни кіріктіру тәуелділіктері қажет. Хитс теоремасынан туындайтын ыдырауда, X-тің кейбір мәндері табылмаған туплдарды енгізуге ештеңе кедергі келтірмейді.

An important property (yielding an immediate application) of functional dependencies is that if R is a relation with columns named from some set of attributes U and R satisfies some functional dependency X → Y then where Z = U − XY. Intuitively, if a functional dependency X → Y holds in R, then the relation can be safely split in two relations alongside the column X (which is a key for ) ensuring that when the two parts are joined back no data is lost, i. e. a functional dependency provides a simple way to construct a lossless join decomposition of R in two smaller relations. This fact is sometimes called Heaths theorem; it is one of the early results in database theory. Heath's theorem effectively says we can pull out the values of Y from the big relation R and store them into one, , which has no value repetitions in the row for X and is effectively a lookup table for Y keyed by X and consequently has only one place to update the Y corresponding to each X unlike the "big" relation R where there are potentially many copies of each X, each one with its copy of Y which need to be kept synchronized on updates. (This elimination of redundancy is an advantage in OLTP contexts, where many changes are expected, but not so much in OLAP contexts, which involve mostly queries.) Heath's decomposition leaves only X to act as a foreign key in the remainder of the big table
Functional dependencies however should not be confused with inclusion dependencies, which are the formalism for foreign keys; even though they are used for normalization, functional dependencies express constraints over one relation (schema), whereas inclusion dependencies express constraints between relation schemas in a database schema. Furthermore, the two notions do not even intersect in the classification of dependencies: functional dependencies are equality generating dependencies whereas inclusion dependencies are tuple generating dependencies. Enforcing referential constraints after relation schema decomposition (normalization) requires a new formalism, i. e. inclusion dependencies. In the decomposition resulting from Heath's theorem, there is nothing preventing the insertion of tuples in having some value of X not found in .

Қалыпты нысандар

Нормальды нысандар – кестелердің сапасын анықтайтын деректер базасы нормализация деңгейлері. Әдетте, үшінші нормальды нысан реляциялық деректер базасы үшін «жақсы» стандарт саналады. Нормализация деректер базасын жаңарту, қосу және жою аномалияларынан құтылуға бағытталған. Сондай-ақ, қатынасқа жаңа мән енгізілген кезде, деректер базасына тигізетін әсері ең аз болуын және осы арқылы деректер базасын пайдаланатын қолданбаларға тигізетін әсері де ең аз болуын қамтамасыз етеді.