Èåðàðõèè èëè äåðåâüÿ. Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ. Áèíàðíûå è n-àðíûå äåðåâüÿ, |
ðàçìåðíîñòü äåðåâà. Ñáàëàíñèðîâàííûå è íå ñáàëàíñèðîâàííûå äåðåâüÿ.
"Äåðåâî" ìîæåò áûòü îïðåäåëåíî êàê èåðàðõèÿ óçëîâ ñ ïîïàðíûìè ñâÿçÿìè, â êîòîðîé: ñàìûé âåðõíèé óðîâåíü èåðàðõèè èìååò åäèíñòâåííûé óçåë, íàçûâàåìûé êîðíåì; êàæäûé óçåë, êðîìå êîðíÿ, ñâÿçàí ñ îäíèì è òîëüêî îäíèì óçëîì, íàõîäÿùèìñÿ íà áîëåå âûñîêîì óðîâíå ïî ñðàâíåíèþ ñ íèì ñàìèì. "Äåðåâî" ìîæåò áûòü ïðåäñòàâëåíî êàê ñïåöèàëüíûé âèä íàïðàâëåííîãî ãðàôà. Ãðàôû – ñòðóêòóðû äàííûõ, ñîñòîÿùèå èç óçëîâ, ñâÿçàííûõ äóãàìè. Êàæäàÿ äóãà ïîêàçûâàåò îäíîíàïðàâëåííóþ ñâÿçü ìåæäó äâóìÿ óçëàìè. Âåðøèíà ãðàôà íàçûâàåòñÿ êîðíåì. Îñòàëüíûå ýëåìåíòû íàçûâàþò óçëàìè èåðàðõèè. Óçåë, ñâÿçàííûé ñ äàííûì óçëîì è íàõîäÿùèéñÿ íà áîëåå íèçêîì óðîâíå â èåðàðõèè, íàçûâàþò äî÷åðíèì óçëîì èëè ïîòîìêîì äàííîãî óçëà. Óçåë, ñâÿçàííûé ñ äàííûì óçëîì è íàõîäÿùèéñÿ íà áîëåå âûñîêîì óðîâíå â èåðàðõèè, íàçûâàþò ðîäèòåëüñêèì óçëîì èëè ïðåäêîì äàííîãî óçëà. Ïîòîìêè, èëè äåòè, ðîäèòåëüñêîãî óçëà – âñå óçëû â ïîääåðåâå, èìåþùèå ðîäèòåëüñêèé óçåë êîðíåì. Óçëû äåðåâà, êîòîðûå íå èìåþò ïîòîìêîâ, íàçûâàþò ëèñòüÿìè. Áèíàðíîå (äâîè÷íîå) äåðåâî (binary tree) - ýòî óïîðÿäî÷åííîå äåðåâî, êàæäàÿ âåðøèíà êîòîðîãî èìååò íå áîëåå äâóõ ïîääåðåâüåâ. Áèíàðíîå äåðåâî íàçîâåì èäåàëüíî ñáàëàíñèðîâàííûì, åñëè äëÿ êàæäîé åãî âåðøèíû êîëè÷åñòâî âåðøèí â ëåâîì è ïðàâîì ïîääåðåâå ðàçëè÷àþòñÿ íå áîëåå ÷åì íà 1.
 îáùåì ñëó÷àå, äåðåâî íàçûâàåòñÿ n-ìåðíûì, åñëè åãî íåêîòîðûé óçåë ìîæåò èìåòü íå áîëåå ÷åì n óçëîâ - ïîòîìêîâ. Óðîâíè èåðàðõèè. Äèàãðàììà ìàêñèìàëüíîãî ïóòè. Ãëóáèíà ïóòè â èåðàðõèè. Ñåìåéñòâî è ðàçìåðíîñòü ñåìåéñòâà èåðàðõèè. Ñòàíäàðòíîå ãðàôè÷åñêîå ïðåäñòàâëåíèå èåðàðõèè â ÎÑ MS Windows
Äðóãîé ñïîñîá ïðåäñòàâëåíèÿ èåðàðõèé – âëîæåííûå ìíîæåñòâà. Çäåñü êîðåíü äåðåâà – ýòî âíåøíåå èëè îáúåìëþùåå ìíîæåñòâî, ñîäåðæàùåå âñå óçëû äåðåâà. Êàæäûé óçåë â äåðåâå ðàññìàòðèâàåòñÿ êàê ìíîæåñòâî ñâîèõ ïîòîìêîâ.
 êà÷åñòâå ïðèìåðîâ èñïîëüçîâàíèÿ èåðàðõèé äëÿ ìîäåëèðîâàíèÿ îáúåêòîâ ðåàëüíîãî ìèðà ìîæíî îòìåòèòü îðãàíèçàöèîííûå äèàãðàììû (ãðàôû), ãåíåàëîãè÷åñêèå äåðåâüÿ, êàðòû êàê îïèñàíèÿ ãåîãðàôè÷åñêèõ îáúåêòîâ è ò.ï.
Äëÿ ðàáîòû ñ äàííûìè ýòîãî òèïà åùå â 60-70 ãã. ïðîøëîãî âåêà áûëè ðàçðàáîòàíû èåðàðõè÷åñêèå ÑÓÁÄ, íàïðèìåð IBM IMS, âûïîëíÿþùàÿñÿ íà êîìïüþòåðàõ IBM ñ àðõèòåêòóðîé System/360, System/370. Îäíàêî ïîäîáíûå ïðîäóêòû â íàñòîÿùåå âðåìÿ â íàøåé ñòðàíå íå èìåþò øèðîêîãî ðàñïðîñòðàíåíèÿ. Äðóãèå ñðåäñòâà ðàáîòû ñ èåðàðõèÿìè ïðåäîñòàâëÿþòñÿ XML.
2)Ïðåäëîæåíèå DELETE ÿçûêà SQL. Óäàëåíèå åäèíñòâåííîé çàïèñè. Óäàëåíèå ìíîæåñòâà çàïèñåé. Óäàëåíèå ñ ïîäçàïðîñîì.
DELETE FROM "table_name" WHERE {condition} – Óäàëåíèå çàïèñè
Íàïðèìåð: DELETE FROM Store_Information WHERE store_name = ‘Los Angeles’; - óäàëåíèå ñòðîê, â êîòîðûõ store_name- Los Angeles.
3)Ïðîåêòèðîâàíèå ðåëÿöèîííûõ ÁÄ ñ èñïîëüçîâàíèåì íîðìàëèçàöèè: íîðìàëüíàÿ ôîðìà Áîéñà-Êîääà, ÷åòâåðòàÿ íîðìàëüíàÿ ôîðìà.
Ïðîöåññ íîðìàëèçàöèè ýòî ïîñëåäîâàòåëüíîå ïðåîáðàçîâàíèå èñõîäíîé ÁÄ ê ÍÔ, ïðè ýòîì êàæäàÿ ñëåäóþùàÿ ÍÔ îáÿçàòåëüíî âêëþ÷àåò â ñåáÿ ïðåäûäóùóþ (÷òî, ñîáñòâåííî, è ïîçâîëÿåò ðàçáèòü ïðîöåññ íà ýòàïû è ïðîèçâîäèòü åãî îäíîêðàòíî, íå âîçâðàùàÿñü ê ïðåäûäóùèì ýòàïàì). Âñåãî â ðåëÿöèîííîé òåîðèè íàñ÷èòûâàåòñÿ 6 ÍÔ: Ïåðâàÿ íîðìàëüíàÿ ôîðìà (îáû÷íî îáîçíà÷àåòñÿ òàêæå 1ÍÔ). Âòîðàÿ íîðìàëüíàÿ ôîðìà. Òðåòüÿ íîðìàëüíàÿ ôîðìà. Íîðìàëüíàÿ ôîðìà Áîéñà-Êîääà (ÍÔÁÊ). ×åòâ¸ðòàÿ íîðìàëüíàÿ ôîðìà. Ïÿòàÿ íîðìàëüíàÿ ôîðìà, èëè íîðìàëüíàÿ ôîðìà ïðîåêöèè-ñîåäèíåíèÿ (5NF èëè PJ/NF).
Ðàññìîòðèì ñëåäóþùèé ïðèìåð ñõåìû îòíîøåíèÿ: ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ (ÑÎÒÐ_ÍÎÌÅÐ, ÑÎÒÐ_ÈÌß, ÏÐÎ_ÍÎÌÅÐ, ÑÎÒÐ_ÇÀÄÀÍ) Âîçìîæíûå êëþ÷è: ÑÎÒÐ_ÍÎÌÅÐ, ÏÐÎ_ÍÎÌÅÐ; ÑÎÒÐ_ÈÌß, ÏÐÎ_ÍÎÌÅÐ Ôóíêöèîíàëüíûå çàâèñèìîñòè: ÑÎÒÐ_ÍÎÌÅÐ -> CÎÒÐ_ÈÌß; ÑÎÒÐ_ÍÎÌÅÐ -> ÏÐÎ_ÍÎÌÅÐ; ÑÎÒÐ_ÈÌß -> CÎÒÐ_ÍÎÌÅÐ; ÑÎÒÐ_ÈÌß -> ÏÐÎ_ÍÎÌÅÐ; ÑÎÒÐ_ÍÎÌÅÐ, ÏÐÎ_ÍÎÌÅÐ -> CÎÒÐ_ÇÀÄÀÍ; ÑÎÒÐ_ÈÌß, ÏÐÎ_ÍÎÌÅÐ -> CÎÒÐ_ÇÀÄÀÍ
 ýòîì ïðèìåðå ìû ïðåäïîëàãàåì, ÷òî ëè÷íîñòü ñîòðóäíèêà ïîëíîñòüþ îïðåäåëÿåòñÿ êàê åãî íîìåðîì, òàê è èìåíåì.  ñîîòâåòñòâèè ñ îïðåäåëåíèåì îòíîøåíèå ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ íàõîäèòñÿ â 3NF. Îäíàêî òîò ôàêò, ÷òî èìåþòñÿ ôóíêöèîíàëüíûå çàâèñèìîñòè àòðèáóòîâ îòíîøåíèÿ îò àòðèáóòà, ÿâëÿþùåãîñÿ ÷àñòüþ ïåðâè÷íîãî êëþ÷à, ïðèâîäèò ê àíîìàëèÿì. Íàïðèìåð, äëÿ òîãî, ÷òîáû èçìåíèòü èìÿ ñîòðóäíèêà ñ äàííûì íîìåðîì ñîãëàñîâàííûì îáðàçîì, íàì ïîòðåáóåòñÿ ìîäèôèöèðîâàòü âñå êîðòåæè, âêëþ÷àþùèå åãî íîìåð. Äåòåðìèíàíò - ëþáîé àòðèáóò, îò êîòîðîãî ïîëíîñòüþ ôóíêöèîíàëüíî çàâèñèò íåêîòîðûé äðóãîé àòðèáóò.
Íîðìàëüíàÿ ôîðìà Áîéñà-Êîääà Îòíîøåíèå R íàõîäèòñÿ â íîðìàëüíîé ôîðìå Áîéñà-Êîääà (BCNF) â òîì è òîëüêî â òîì ñëó÷àå, åñëè êàæäûé äåòåðìèíàíò ÿâëÿåòñÿ âîçìîæíûì êëþ÷îì. Î÷åâèäíî, ÷òî ýòî òðåáîâàíèå íå âûïîëíåíî äëÿ îòíîøåíèÿ ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ. Ìîæíî ïðîèçâåñòè åãî äåêîìïîçèöèþ ê îòíîøåíèÿì ÑÎÒÐÓÄÍÈÊÈ è ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ: ÑÎÒÐÓÄÍÈÊÈ (ÑÎÒÐ_ÍÎÌÅÐ, ÑÎÒÐ_ÈÌß) Âîçìîæíûå êëþ÷è: ÑÎÒÐ_ÍÎÌÅÐ; ÑÎÒÐ_ÈÌß Ôóíêöèîíàëüíûå çàâèñèìîñòè: ÑÎÒÐ_ÍÎÌÅÐ -> CÎÒÐ_ÈÌß; ÑÎÒÐ_ÈÌß -> ÑÎÒÐ_ÍÎÌÅÐ; ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ (ÑÎÒÐ_ÍÎÌÅÐ, ÏÐÎ_ÍÎÌÅÐ, ÑÎÒÐ_ÇÀÄÀÍ) Âîçìîæíûé êëþ÷: ÑÎÒÐ_ÍÎÌÅÐ, ÏÐÎ_ÍÎÌÅÐ Ôóíêöèîíàëüíûå çàâèñèìîñòè: ÑÎÒÐ_ÍÎÌÅÐ, ÏÐÎ_ÍÎÌÅÐ -> CÎÒÐ_ÇÀÄÀÍ
Âîçìîæíà àëüòåðíàòèâíàÿ äåêîìïîçèöèÿ, åñëè âûáðàòü çà îñíîâó ÑÎÒÐ_ÈÌß.  îáîèõ ñëó÷àÿõ ïîëó÷àåìûå îòíîøåíèÿ ÑÎÒÐÓÄÍÈÊÈ è ÑÎÒÐÓÄÍÈÊÈ-ÏÐÎÅÊÒÛ íàõîäÿòñÿ â BCNF, è èì íå ñâîéñòâåííû îòìå÷åííûå àíîìàëèè.
Ðàññìîòðèì ïðèìåð ñëåäóþùåé ñõåìû îòíîøåíèÿ: ÏÐÎÅÊÒÛ (ÏÐÎ_ÍÎÌÅÐ,ÏÐÎ_ÑÎÒÐ, ÏÐÎ_ÇÀÄÀÍ)
Îòíîøåíèå ÏÐÎÅÊÒÛ ñîäåðæèò íîìåðà ïðîåêòîâ, äëÿ êàæäîãî ïðîåêòà ñïèñîê ñîòðóäíèêîâ, êîòîðûå ìîãóò âûïîëíÿòü ïðîåêò, è ñïèñîê çàäàíèé, ïðåäóñìàòðèâàåìûõ ïðîåêòîì. Ñîòðóäíèêè ìîãóò ó÷àñòâîâàòü â íåñêîëüêèõ ïðîåêòàõ, è ðàçíûå ïðîåêòû ìîãóò âêëþ÷àòü îäèíàêîâûå çàäàíèÿ. Êàæäûé êîðòåæ îòíîøåíèÿ ñâÿçûâàåò íåêîòîðûé ïðîåêò ñ ñîòðóäíèêîì, ó÷àñòâóþùèì â ýòîì ïðîåêòå, è çàäàíèåì, êîòîðûé ñîòðóäíèê âûïîëíÿåò â ðàìêàõ äàííîãî ïðîåêòà (ìû ïðåäïîëàãàåì, ÷òî ëþáîé ñîòðóäíèê, ó÷àñòâóþùèé â ïðîåêòå, âûïîëíÿåò âñå çàäàíèÿ, ïðåäóñìîòðåííûå ýòèì ïðîåêòîì). Ïî ïðè÷èíå ñôîðìóëèðîâàííûõ âûøå óñëîâèé åäèíñòâåííûì âîçìîæíûì êëþ÷îì îòíîøåíèÿ ÿâëÿåòñÿ ñîñòàâíîé àòðèáóò ÏÐÎ_ÍÎÌÅÐ, ÏÐÎ_ÑÎÒÐ, ÏÐÎ_ÇÀÄÀÍ, è íåò íèêàêèõ äðóãèõ äåòåðìèíàíòîâ. Ñëåäîâàòåëüíî, îòíîøåíèå ÏÐÎÅÊÒÛ íàõîäèòñÿ â BCNF. Íî ïðè ýòîì îíî îáëàäàåò íåäîñòàòêàìè: åñëè, íàïðèìåð, íåêîòîðûé ñîòðóäíèê ïðèñîåäèíÿåòñÿ ê äàííîìó ïðîåêòó, íåîáõîäèìî âñòàâèòü â îòíîøåíèå ÏÐÎÅÊÒÛ ñòîëüêî êîðòåæåé, ñêîëüêî çàäàíèé â íåì ïðåäóñìîòðåíî.
Ìíîãîçíà÷íûå çàâèñèìîñòè  îòíîøåíèè R (A, B, C) ñóùåñòâóåò ìíîãîçíà÷íàÿ çàâèñèìîñòü R.A -> -> R.B â òîì è òîëüêî â òîì ñëó÷àå, åñëè ìíîæåñòâî çíà÷åíèé B, ñîîòâåòñòâóþùåå ïàðå çíà÷åíèé A è C, çàâèñèò òîëüêî îò A è íå çàâèñèò îò Ñ.  îòíîøåíèè ÏÐÎÅÊÒÛ ñóùåñòâóþò ñëåäóþùèå äâå ìíîãîçíà÷íûå çàâèñèìîñòè: ÏÐÎ_ÍÎÌÅÐ -> -> ÏÐÎ_ÑÎÒÐ; ÏÐÎ_ÍÎÌÅÐ -> -> ÏÐÎ_ÇÀÄÀÍ
Ëåãêî ïîêàçàòü, ÷òî â îáùåì ñëó÷àå â îòíîøåíèè R (A, B, C) ñóùåñòâóåò ìíîãîçíà÷íàÿ çàâèñèìîñòü R.A -> -> R.B â òîì è òîëüêî â òîì ñëó÷àå, êîãäà ñóùåñòâóåò ìíîãîçíà÷íàÿ çàâèñèìîñòü R.A -> -> R.C.
×åòâåðòàÿ íîðìàëüíàÿ ôîðìà
Îòíîøåíèå R íàõîäèòñÿ â ÷åòâåðòîé íîðìàëüíîé ôîðìå (4NF) â òîì è òîëüêî â òîì ñëó÷àå, åñëè â ñëó÷àå ñóùåñòâîâàíèÿ ìíîãîçíà÷íîé çàâèñèìîñòè A -> -> B âñå îñòàëüíûå àòðèáóòû R ôóíêöèîíàëüíî çàâèñÿò îò A.
 íàøåì ïðèìåðå ìîæíî ïðîèçâåñòè äåêîìïîçèöèþ îòíîøåíèÿ ÏÐÎÅÊÒÛ â äâà îòíîøåíèÿ ÏÐÎÅÊÒÛ-ÑÎÒÐÓÄÍÈÊÈ è ÏÐÎÅÊÒÛ-ÇÀÄÀÍÈß:
ÏÐÎÅÊÒÛ-ÑÎÒÐÓÄÍÈÊÈ (ÏÐÎ_ÍÎÌÅÐ, ÏÐÎ_ÑÎÒÐ)
ÏÐÎÅÊÒÛ-ÇÀÄÀÍÈß (ÏÐÎ_ÍÎÌÅÐ, ÏÐÎ_ÇÀÄÀÍ)
Îáà ýòè îòíîøåíèÿ íàõîäÿòñÿ â 4NF è ñâîáîäíû îò îòìå÷åííûõ àíîìàëèé.
×åòâ¸ðòàÿ íîðìàëüíàÿ ôîðìà çàïðåùàåò ñóùåñòâîâàíèå ìíîãîçíà÷íûõ çàâèñèìîñòåé ìåæäó ñòîëáöàìè. Åñëè ñòîëáåö âìåñòî òîãî, ÷òîáû óíèêàëüíî èäåíòèôèöèðîâàòü äðóãîé ñòîëáåö, îãðàíè÷èâàåò åãî çíà÷åíèÿ íåêîòîðûì ïðåäîïðåäåë¸ííûì ìíîæåñòâîì çíà÷åíèé – ýòî îçíà÷àåò, ÷òî ìåæäó íèìè ñóùåñòâóåò ìíîãîçíà÷íàÿ çàâèñèìîñòü.
Íà ïðàêòèêå, êàê ïðàâèëî, îãðàíè÷èâàþòñÿ 3ÍÔ, åå îêàçûâàåòñÿ âïîëíå äîñòàòî÷íî äëÿ ñîçäàíèÿ íàäåæíîé ñõåìû ÁÄ. ÍÔ áîëåå âûñîêîãî ïîðÿäêà ïðåäñòàâëÿþò ñêîðåå àêàäåìè÷åñêèé èíòåðåñ èç-çà èõ ñëîæíîñòè. Áîëåå òîãî, ïðè ðåàëèçàöèè àáñòðàêòíîé ñõåìû ÁÄ â âèäå ðåàëüíîé áàçû èíîãäà ðàçðàáîò÷èêè âûíóæäåíû ñäåëàòü øàã íàçàä – ïðîâåñòè äåíîðìàëèçàöèþ ñ öåëüþ ïîâûøåíèÿ ýôôåêòèâíîñòè, ò.ê. èäåàëüíàÿ, ñ òî÷êè çðåíèÿ òåîðèè, ñòðóêòóðà ìîæåò îêàçàòüñÿ ñëèøêîì íàêëàäíîé íà ïðàêòèêå.
Ñåðèÿ ñîîáùåíèé "Áàçû äàííûõ":
×àñòü 1 - Ôàéëîâûå ñèñòåìû. Íàçíà÷åíèå ôàéëîâûõ ñèñòåì.
×àñòü 2 - Îñîáåííîñòè îðãàí õðàíåíèÿ äàííûõ
...
×àñòü 6 - Êîëëåêòèâíûé äîñòóï ê äàííûì. Ïðîáëåìû êîëëåêòèâíîãî äîñòóïà.
×àñòü 7 - Ëèíåéíûå ñòðóêòóðû. Ïîíÿòèå ñïèñêà. Òèïû ñïèñêîâ («øèíà», «êîëüöî»).
×àñòü 8 - Èåðàðõèè èëè äåðåâüÿ. Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ. Áèíàðíûå è n-àðíûå äåðåâüÿ,
×àñòü 9 - 6 Ïîíÿòèå ñåòåâîé îðãàíèçàöèè äàííûõ. Ñòðóêòóðû òèïà «çâåçäà», îáúåäèíåíèå çâ¸çä, ïîëíîñâÿçíàÿ ñåòü, ïðîèçâîëüíûé ãðàô.
×àñòü 10 - Ïðåäëîæåíèå SELECT ÿçûêà SQL. Âûáîðêà ñ èñïîëüçîâàíèåì IN, âëîæåííûé SELECT.
...
×àñòü 43 - Ìåòîä âñïîìîãàòåëüíîé òàáëèöû äëÿ ñëó÷àÿ ïðîèçâîëüíîãî ãðàôà. Îòëè÷èÿ îò ñëó÷àÿ ìîäåëèðîâàíèÿ èåðàðõèé
×àñòü 44 - Îáúåêòíî-îðèåíòèðîâàííàÿ ìîäåëü è ðåëÿöèîííàÿ ìîäåëü. Ñõîäñòâî è îòëè÷èÿ.
×àñòü 45 - Èñïîëüçîâàíèå «êîîðäèíàòíîãî» ìåòîäà äëÿ ìîäåëèðîâàíèÿ èåðàðõèé è ïðîèçâîëüíûõ ãðàôîâ. Åãî äîñòîèíñòâà è
| Ðóáðèêè: |
| Êîììåíòèðîâàòü | « Ïðåä. çàïèñü — Ê äíåâíèêó — Ñëåä. çàïèñü » | Ñòðàíèöû: [1] [Íîâûå] |