Дәріс №8. Қатынасты қарапайымдау

1. 
   Қатынасты қарапайымдау.
   
2. 
   Бірінші қарапайым форма.
   
3. 
   Екінші қарапайым форма.
   
4. 
   Үшінші қарапайым форма.
   

Бірдей деректер кестеде әр түрлі әдістермен топтасуы мүмкін, яғни байланысқан ақпараттық объектілер қатынастының әр түрлі жиынтығын ұйымдастыру мүмкін. Қатынаста атрибуттарды топтау рационалды болуы керек, яғни деректердің көшірмесін минимизациялайтын және оларды өңдеу мен жаңарту процедурасын жеңілдететін.

Қатынастың белгілі жиынтығы деректерді қосу, модификациялау, жою кезінде қатынастың барлық қалған мүмкін жиынтықтарына қарағанда жақсы құрамдармен қамтамасыз етіледі.

Қатынасты қарапайымдау – көшіруді жоюға мүмкіндік беретін қатынастарды (кестелер) қалыптастыруға формальды аппарат шегі.

Е.Коддпен қатынастың үш қарапайымдау формасы ерекшеленген және кез келген қатынасты үшінші қарапайымдау формасына айналдыруға мүмкіндік беретін механизмді ұсынды.

Егер барлық атрибуттары қарапайым болса, қатынас бірінші қарапайымдау формасына келтірілген деп аталады. Қатынастың бірінші қарапайымдау формасына айналуы қатынас реквизиттер (өрістер) санының өсуіне және кілттің өзгеруіне әкелуі мүмкін.

Мысалы, Студент=(Номер, Фамилия, Аты, Отчество, Күні, Тобы) қатынасы бірінші қарапайымдау формасында тұр.

Екінші қарапайымдау формасы

Қатынасты екінші қарапайымдау формасына келтіру сұрағын қарастыру үшін функционалды тәуелділік және толық функционалды тәуелділік сияқты түсініктерге сипаттама беріп кету қажет.

Ақпараттық объектінің бейнеленген реквизиттері оларға арналған жалпы кілтпен логикалық байланысқан, бұл байланыс реквизиттердің функционалды тәуелділігін сипаттайды.

Реквизиттердің функционалды тәуелділігі – кілттік реквизиттің анықталған мәнінде ақпараттық объектінің көшірмесі кезіндегі тәуелділік суреттелген реквизиттің бір ғана мәніне сәйкес келеді.

Функционалды тәуелділіктің мұндай анықтамасы пәндік облыс реквизиттерінің барлық қарым-қатынастарын анализдеу кезінде жеке ақпараттық объектілерді бөлуге мүмкіндік береді.

Мысал 4. Студент реквизитінің функционалды тәуелділігін графиктік бейнелеу мысалы суретте көрсетілген, мұнда кілттік реквизит * түрінде берілген.

Номер*

Фамилия

Отчество

Тобы
Құрама кілт жағдайында функционалды толық тәуелділік түсінігі енгізіледі.

Кілттік емес атрибуттардың функционалды толық тәуелділігі әрбір кілттік емес атрибут функционалды түрде кілтке байланысты, бірақ құрама кілттің ешқандай бөлігінің функционалды тәуелділігінде жатпайтынымен анықталады.

Қатынас екінші қарапайымдау формасында жатады, егер ол бірінші бірінші қарапайымдау формасынада жатса, және әрбір кілттік емес атрибут құрама кілттен функционалды байланысты болады.

Үшінші қарапайымдау формасы түсінігі транзитивтік емес тәуелділік түсінігіне негізделген.

Транзитивтік тәуелділік егер екі суреттелген реквизиттердің біреуі кілтке тәуелді, ал басқа суреттелген реквизит бірінші суреттелген реквизитке тәуелді болған жағдайда бақыланады.

Қатынас үшінші қарапайымдау формасында болады, егер ол екінші қарапайымдау формасында тұрса, және әрбір кілттік емес атрибут бастапқы кілттен транзитивті емес тәуелді болады.

Суреттелген реквизиттердің транзитивті тәуелділігін жою үшін берілген ақпараттық объектінің «бөліктеуін» (расшепление) жүргізу қажет. Бөліктеу нәтижесінде реквизиттер бөлігі берілген ақпараттық объектіден жойылады және басқа ақпараттық объектілер (мүмкін жаңа құрылған) құрамын қосады.

Топ студенті Студент Топ

Номер* Номер* Топ*

Фамилия Фамилия Староста

Аты Аты

Отчество Отчество

Топ Топ

1. 
   Қарапайымдау дегеніміз не?
   
2. 
   1-ші қарапайым формаға түсініктеме беріңіз.
   
3. 
   Функционалдық қатыстылық дегеніміз не?
   
4. 
   Толық функционалды қатыстылық дегеніміз не?
   
5. 
   Транзитивті қатыстылық дегеніміз не?
   
6. 
   2-ші қарапайым формаға түсініктеме беріңіз.
   
7. 
   3-ші қарапайым формаға түсініктеме беріңіз.
   

1. 
   Деректердің физикалық құрылымының жалпы сипаттамасы.
   
2. 
   Деректерді физикалық сақтаудың әдістері.
   
3. 
   Деректер базасына кіру әдістері.
   
4. 
   Деректер базасында ақпаратты іздеу тәсілдері.
   
5. 
   Деректердің физикалық форматы.
   

Физикалық жобалау нәтижесі физикалық модель болып табылады, ол сақтау ортасына даталогиялық модельді байланыстыру үшін пайдаланылады.

Деректер базасының физикалық құрылымын сипаттау сақтау схемасы деп аталады.

Деректер базасын физикалық өндіру сұрақтары осы уақытқа дейін өте маңызды орын алып келді. Егер логикалық модельді таңдау ақпараттың құрылымын анықтаса және сұралатын ақпаратты іздеу үшін қажет орындалатын операциялардың құрамымен деректер базасының тиімділігі жинақталса, онда физикалық өңдіру ақпараттың элементін іздеу операциясына қатысты тиімді орындауды анықтайды. Қазіргі деректер базасын басқару жүйелері физикалық жадыға деректердің логикалық құрылымын автоматты түрде сипаттауды өндіреді және іздеу процедурасының шексіз жиынын береді.

Жалпы, деректер базасының физикалық өнімі келесіні қарастырады:

• 
  Деректерді физикалық сақтауды ұйымдастыру;
  
• 
  Деректердің қажетті элементтерін іздеу процедураларын анықтау.
  

Деректер базасын басқару жүйесі ақпараттың физикалық тасымалдағышында ақпаратты адрестемейді, ал тек қана жадыны бөлу ережелерін анықтайды. ЭЕМ жадында деректерді сақтаудың ең қарапайым және таралған формасы бірөлшемді сызықты тізім болып табылады. Сызықты тізім – бұл X[1], X[2], ..., X[n] объектілерінің (тораптарының) n  0 жиынтығы, құрылымдық құрамы тораптардың сызықты орналасуымен ғана байланысқан. Сызықты тізім элементтердің сызықты реттелуі ретінде анықталатын құрылымды өндіреді.

X сызықты тізім X[1], X[2], ..., X[i], ..., X[n] ретінде қарастырылады, оның компоненттері X–те орналасуын көрсететін реттік номермен идентификацияланған.

ЭЕМ жадында логикалық деректерді көрсету кезінде ДББЖ-мен шешілетін негізгі мәселе Деректердің логикалық құрылымын сақтаудың физикалық құрылымында көрсетудің тиімді әдістерін табу болып табылады. Мұндай бейнелеу адрестік функция деп аталады. Адрестік функцияны өндіру кезінде екі негізгі әдіс пайдаланылады: жадыны тізбектей бөлу және жадыны байланыстыра бөлу.

Жадыны тізбектей бөлу жадының тізбектелген эдлементтерінде тізімнің тораптарын орналастыруға негізделген. Тізбектей бөлудің адрестік функциясы қарапайым жағдайда мына түрде болады:

мұнда i – жазба номері;

 - ізделінді адрес;

 - жадыда деректер векторының басын көрсететін базаның адресі.

Жадыны тізбектей бөлудің негізгі құндылығы деректердің физикалық тәуелсіздігінің жоғары деңгейі мен қарапайым өндірілуі болып табылады. Кемшіліктеріне деректердің иерархиялық және желілік құрылымын өндіру қиындығы мен ақпаратты өңдеу және іздеу тиімсіздігін жатқызуға болады.

Сызықты тізімді байланыстыра бөлу байланысқан тізім деп аталады. Құрылымды құру үшін жадыны байланыстыра бөлу кезінде көрсеткіштер көмегімен элементтерді іздеу қатынасын беру қажет. Көрсеткіштерге мәлімет жазбаларында сақталған адрестер жатады. Адрестік функция көмегімен келесі элементтің адресі есептелетін жадыны тізбектей бөлуге қарағанда адрестік функция мәнін жадыны байланыстыра бөлу кезінде сақталған көрсеткіштерді көру жолымен ғана алуға болады. Жадыны бөлудің мұндай әдісі ЭЕМ жадында деректердің өзін ауыстырмай-ақ деректер құрылымын ұлғайтуға және қысқартуға мүмкіндік береді. Бірақ жадыны тізбектей бөлумен салыстырғанда құрылымды сақтау үшін көп жады қажет.

Байланысқан бөлу - өте қиын, бірақ сызықты тізімді сақтаудың иілгіш әдісі. Әрбір торап құрамында тізімнің басқа тораптарына көрсеткіштері бар. Байланыстыра бөлу кезінде жадының реттелген элементтерінде тізімнің сақталғанын қажет етпейді. Сақтаудың берілген әдісінде байланыс адрестерінің бар болуы жадының кез келген бос жерінде жеке тізім тораптарын орналастыруға мүмкіндік береді. Тізімнің сызықты құрылымы көрсеткіштермен қамтамасыз етіледі.

Байланысқан тізім келесідей өндірілуі мүмкін:

• 
  бір жаққа бағытталған тізім – берілген тізімде бір ғана көрсеткіш пайдаланылады, онда тізімнің келесі торабының адресі болады;
  

• 
  екі жаққа бағытталған тізім – берілген тізімде екі көрсеткіш пайдаланылады, олардың біріншісі алдыңғы торап адресі, ал екіншісі – тізімнің келесі торабының адресінен тұрады;
  

Қарастырылып отырған тізімдердің негізгі кемшілігі ақпаратты іздеудің төмен тиімділігі болып табылады (қажет торапты іздеу үшін тораптардың жеткілікті үлкен санын көру қажет болуы мүмкін).

• 
  өткізу мүмкіндігі бар тізім – мұнда сызықты тізім өзара кері көрсеткіштермен байланысқан тораптар тобына бөлінеді. Басында қажет торап табылатын топқа кері көрсеткіш бойынша кіру жүзеге асады, ал содан кейін түзу көрсеткіштер бойынша қажет торап табылмағанша топтың торабы іріктеледі. Топтың оптималды өлшемін табайық. Топтар саны анық
  

Қажет торапқа кіру кезінде топтар ішінен торапты табу үшін орташа тобын, ал әрбір топта - қарап шығу керек. Демек, көріністердің жалпы саны

Әрбір топта элементтер саны минималды

Алынған мәнді нөлге теңестіре отырып, аламыз.

Бұл жағдайда тізімнің арнайы торабын - head (басы) құру және оны арнайы тіркелген ұяшықта сақтау керек. Бұл торапқа тізімнің бірінші элементіне көрсеткіш, сонымен қатар тізімді өңдеу (идентификатор, тізімдегі тораптар саны және т.с.с.) үшін арналған қызметші ақпарат орналасады.

Практикалық өндіру үшін көрсеткіштердің үш типі пайдаланылады:

• 
  нақты адрес – тізім түрінде ұйымдастырылған деректерді өңдеудің жоғары жылдамдығын қамтамасыз етеді;
  

• 
  қатысты адрес – жазбаларды жадының кез келген жеріне және көрсеткіштер мәнін өзгертпей әртүрлі құрылғыларға орналастыруға мүмкіндік береді, сонымен қатар тізім орнын ауыстыру кезінде жазбадағы көрсеткіштер өзгермейді, ал нақты адресті есептеу кезінде базалық адрес қана өзгереді.;
  

• 
  символдық адрес (идентификатор) – тізімді түгелдей, сонымен қатар бір-біріне қатысты оның жеке жазбаларының орнын ауыстыруға мүмкіндік береді. Тізімнің барлық қалған жазбаларынан көрсеткіштерді өзгертпей тізімге жазбаларды қосуға және жоюға мүмкіндік береді.
  

Тоғай тәрізді және желілік құрылымды физикалық ұйымдастыру кезінде екі сұрақты шешу қажет:

• 
  құрылымның төбесімен (тораппен) көрсетілген деректерді ұйымдастыру;
  
• 
  құрылым доғасымен көрсетілген деректер арасында байланыстарды ұйымдастыру.
  

1) Адрестік арифметика әдісі. Берілген әдісті жетілдірудің екі әдісі бар – олардың бірі бірінші тораптан бастап, тізімдер торабын тізбектей орналастыруға негізделген. Берілген жоба балансталған тоғайларды жетілдіру үшін ыңғайлы, яғни кез келген тораптан туындаған тораптар саны, соңғысынан басқа, тоғайлар бірдей болады. Кез келген тораптың адресі алдында келтірілген адрестік функция көмегімен табылады; бірақ ең қызықтысы торап-ұрпақтардың (потомок) адрестік функциясы болып табылады. Үшінші ретті тоғай үшін белгілі бір k торабының ұрпағы 3k-1, 3k, 3k+1 тізімінің ерекшеленген торабына жады квантасында орналасады. Негізді кемшілігі төртінші және одан да жоғары ретті балансталған тоғайлар үшін адрестік функция күрделілігі болып табылады. Екінші әдіс екілік тоғайлар (екінші ретті балансталған тоғайлар) үшін ғана қолданбалы және тізімді орналастыру үшін бөлінген жады векторының ортасына тізімнің бірінші торабын орналастыруға негізделген, яғни адресімен жады ұяшығына, мұндағы i және j – тізімді орналастыру үшін бөлінетін жадының бастапқы және соңғы квантасының адресі. i -ден l-1-ге дейін жады квантасында сол жақ тоғайасты деп аталатын, ал l+1 –ден j-ге дейін оң жақ тоғайасты орналастырылады.

1) Туындаған жазбаларға көрсеткіштер әдісі – берілген әдіс тоғай бойымен түзу бағытта қозғалуды өндіруге мүмкіндік береді. Бұл әдісті пайдаланған жағдайда кез келген жазба, төменгі деңгейдің жазбасынан басқа, туындаған жазбада бар көрсеткіштер санымен тең болуы керек.

3) Алғашқы және туындаған жазбаларға көрсеткіштер әдісі – берілген әдіс тоғайдың түзу де, кері де бағытта жүріп өтуін қамтамасыз етеді, өйткені екібағытты тізім пайдаланылады. Әдістің кемшілігі – туындаған жазбаларға көрсеткіштер әдісі сияқты, өйткені тораптарда көрсеткіштер саны ауыспалы және туындаған жазбалар санымен анықталады.

Желілік құрылымды көрсету үшін желілік құрылымды өндіруге мүмкіндік беретін жоғарыда қарастырылған әдістердің белгілі бір комбинациясын пайдаланады. Мысалы, туындаған, сол сияқты және алғашқы жазбаларға көрсеткіштермен әдістердің комбинациясын пайдаланады. Көбінесе сақиналы құрылым пайдаланылады.

Егер жазбада көрсеткіштер саны шектеулі болған жағдайда, онда күрделі емес желілік құрылым өндіруге болады. Күрделі желілік құрылым үшін айнымалының әрбір жазбасы үшін көрсеткіштер енгізу қажет.

Желілік құрылымды ұйымдастырудың ең тиімді әдісі анықтамаларды пайдалану болып табылады. Сонымен қатар, көрсеткіштер жазбалардан алынып, жеке файлдарға – анықтамаларға орналастырылады. Анықтаманы сәйкес бөлімде деректерді іздеуді тез орындайтындай етіп оптималды түрде ұйымдастыруға болады. Анықтамаларды пайдалану желілік құрылым күрделілігіне тура пропорционал деп айтуға болады.

Адресті кілтке түрлендіру ретінде белгілі «адресті есептеу әдісі» термині кілт атауымен адресті есептеуден басталатын ақпаратты іздеу және сақтау әдістерінің үлкен тобын қамтиды. Мұндай әдістер жады қасиетін толықтай пайдаланады. Адресті есептеу әдістерінде деректер жазбасының кілт мәнін оған сәйкес жады адресін түрлендіретін белгілі бір есептеу операциясы пайдаланылады, яғни адрестерті функция өндіріледі.

Мысал қарастырайық – адреске эквивалентті кілт көмегімен адрестеу әдісі – адрес ретінде әмбебап идентификатор, мысалы, сынақ кітапшасының номері пайдаланылуы мүмкін. Берілген әдістің дамуы кілттің адреске түрлену алгоритмін пайдалану көмегімен адрестеу әдісі болып табылады. Әдіс адрестеу орындалатын файлда жазбалардың сызықты реттілігін және фиксацияланған ұзындықтың жазбасын пайдалануды болжайды. (НОМЕР, ЖҮРУ_УАҚЫТЫ, БОС_ОРЫННЫҢ_БОЛУЫ) ақпарат берілсін. НОМЕР 1 ден 699 аралығында, ЖҮРУ_УАҚЫТЫ 1 ден 366 аралығында өзгерсін және бір жазбаға 20 байт берілсін, сонда жазба адресі былайша анықталуы мүмкін

Ұсынылған әдістердің басты кемшілігі, егер кілттер адрестердің үзіліссіз жиынына түрленбеген жағдайда, жадыны толтырудың төмен дәрежесі болып табылады.

Ең көп таралған әдістерге араластыру немесе хэштеу (кейде рандомизация әдісі термині пайдаланылады) жатады. Берілген әдістің негізгі идеясы мынандай: сақталатын жазбаның әрбір экземпляры кілт мәні бойынша белгілі бір псевдокездейсоқ функция (хэш-функция) көмегімен есептелетін ардеспен жадыға орналастырылады. Бұл жағдайда алғашқы кілт мәнімен сәйкестендіріп жазбаны ұйымдастыру қажет емес.

Кілтті, эквивалентті адресті және кілтті адреске түрлендіру алгоритмін пайдалану көмегімен адрестеудің қарастырылған әдісі көбінесе қолданбалы емес, өйткені алғашқы кілт мәнінің диапазоны жады адресінің диапазонынан өте үлкен болуы мүмкін. Хэш-функция алғашқы кілт мәнін жазбаны сақтау үшін оқшауланған жады адресі мәнінің диапазонына түрлендіруге мүмкіндік береді.

Деректер базасының көлемі бірнеше гигабайтқа жетуі мүмкін. Деректер базасымен басқару жүйесінде деректер базасында ақпараттың белгілі бір бөлігін іздеу бойынша функция артылған. Деректер базасын басқару жүйесінің операциялық жүйемен өзара іс-әрекеті физикалық жазба деңгейінде ғана өндіріледі. Осыған байланысты деректер базасын басқару жүйесінде логикалық жазбалар адресін физикалық жазбалар адресіне түрлендіру және логикалық жазбаларды физикалық жазбалардан ерекшелеу механизмі құрылған.

Бірақ, физикалық жазбалар адресін есептеу процедурасы деректер базасының логикалық жазбаларын іздеу процедурасынан оңай. Деректер базасында ақпаратты іздеу әдістерінің ең кең таралғандары мыналар:

• 
  тізбектей іздеу;
  
• 
  бинарлы (екілік) іздеу;
  
• 
  индекс бойынша іздеу;
  
• 
  екінші кілт бойынша іздеу (файлдарды инверттау);
  
• 
  хэш-функцияны пайдалану арқылы іздеу.
  

мұндағы - енгізу-шығару операциясы орындалуының орташа уақыты; - деректер базасы файлының сақтаулына берілген физикалық блоктар саны.

Бинарлы немесе екілік іздеу бір немесе бірнеше өрістер мәнінің өсу немесе кемуі бойынша реттелген деректер файлында қолданылады. Егер іздеу жазбадан тұратын белгілі бір өріс мәнінің өсуі бойынша реттелген файлда жүргізілсе, онда бірінші тексерілетін жазба номері бар жазба болады. Егер бойынша іздеу жүргізілетін өріс мәні Q іздеу шартымен сәйкес келсе, онда іздеу сәтті аяқталады; кері жағдайда, егер >Q , файлдың сол жағында жалғасса. Сонымен қатар сәйкесінше жазбалар таңдап алынады:

және

Іздеу аяқталады, егер іздеу шартын қанағаттандыратын жазба табылса, онда =Q. Берілген әдісті пайдалану кезінде іздеу тиімділігі жоғары.

Индекс бойынша іздеу индекс деп аталатын қосымша ақпаратты алдын ала құру және пайдалануды қарастырады. Индекс пен анықтаманы ұйымдастыруда аналогиясы бар – индекстің де анықтаманың да ақпараты жазба кілтінің мәнінен және оның адресі туралы ақпараттан тұрады. Сонымен қатар, индекс ешқандай басқа ақпаратты сақтамайды және барлық жазбалар туралы мағлұматты сақтауы мүмкін емес, сонда толық және толық емес индекстерді ерекшелейді.

Белгілі бір файл қандайда бір К өрісі бойынша реттелген болсын. Сонда индексті файл мынандай құрылымнан тұрады: К1- деректер файлының К өріс мәнінен тұратын өріс; RefK – деректер файлының сәйкес жазбасына сілтемеден тұратын өріс.

Толық емес индекс жағдайында индексті файл жеке жазбаларға көрсеткіштерден тұрады. Толық емес индексті пайдалану арқылы іздеу кезінде индексті-реттелген кіру өндіріледі – ең алдымен физикалық жазба басталатын жазба адресі анықталады

Толық индекс жағдайында деректер файлын кілт бойынша реттеу қажет емес.

Бұл жағдайда индексті файл деректердің барлық жазбаларына көрсеткіштерден тұрады. Толық индексті пайдалану кезінде индексті файлда логикалық жазба адресі анықталады.

Толық индексті пайдалану тиімді. Толық емес индекс артықшылығы индекстер тоғайын құру мүмкіндігі деп есептеу болады. Кемшіліктері деректер файлының іздеу кілті бойынша реттілігін қажет етумен байланысты. Толық индекс артықшылығы деректердің бір физикалық файлы бойынша жазбалардың бірнеше логикалық тізбегін құру мүмкіндігі болып табылады, іздеудің жоғары тиімділігі. Кемшілігі толық емес индекспен салыстырғанда индексті файлдың үлкен көлемімен анықталады.

Екінші кілт бойынша іздеу инвертталған файлдар – белгілі бір өріс мәнінен және сәйкес жазбалар номерінен тұратын массивтерді құруды болжайды. Инвертталған файлда элементтер саны деректер файлының өрістер мәнінің санына тең. Қазіргі уақытта екінші кілт бойынша іздеу пайдаланылмайды.

Хэш-функцияны пайдалану арқылы іздеу тек қана хэш-функцияны пайдалану арқылы ұйымдастырылған деректер файлында мүмкін. Іздеу хэш-функция көмегімен іздеу кілтін адреске түрлендіруге негізделген. Сонымег қатар, ақпаратты сақтау және іздеуді ұйымдастыру үшін дәл сол хэш-функцияны пайдалану қажет. Хэш-адресация әдісін пайдаланудың негізгі артықшылығы іздеудің жоғары тиімділігі болып табылады.