Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 7 страница

Сызықты тізім (алгоритмдер және деректер құрылымы)

Стек – бұл сызықты тізім, мұнда орналастыру және жою (қатынау) операциялары тек қана тізімнің бір жақ бетінде ғана орындалады.

Кезек немесе бір жақты кезек – бұл сызықты тізім, орналастыру операциялары бір жақ бетте, ал жою операциялары екінші жақ бетте орындалады.

Дек немесе екі жақты кезек (double-ended queue) – бұл сызықты тізім, мұнда орналастыру және жою (қатынау) операциялары тек қана тізімнің екі жақ бетінде орындалады.

Жоғарыдағыға сүйіне отырып, дек стек пен кезектің жалпылама нұсқасы болып табылады. Сонымен қатар дектерді шектелген кіріс (output-restricted deque) пен шектелген шығыс (input restricted deque)арасында айырмашылықты көруге тиісті, себебі мұнда орналастыру және жоб операциялары бір жақ бетте.

Реляциялық ДБ негізгі ұғымдары, қасиеттері, операциялары.

кі

Реляциялық модельді 1970 жылы Е.Ф.Кодд ұсынды. Қазіргі уақытта, қазіргі замаңғы коммерциялық МББЖ-дың барлығы дерлік осы модельді стандарт ретінде қабылдайды.

Реляқциялық модельдер, иерархиялық немесе желілік модельдерге қарағанда, деректерді абстракциялаудың жоғарғы деңгейінде. Е.Ф.Кодд жоғарыда аталған мақаласында былай дейді: «реляциялық модель мәліметерді сипаттауда, олардың тек табиғы структурасы негізіндегі құралдарды ұсынады, яғни, машиналық түрде көрсету мақсаты үшін ешқандай қосымша структура еңгізу қажеттілігі жоқ». Басқаша айтқында, деректерді көрсету олардың физикалық ұйымдастыруынан тәуелсіз. Бұл математикалық қатынас теориясын пайдалану есебінен қамтамасыздандырылады («реляциялық» деген аттың өзі ағылшынның relation – «қатынас» деген сөзінен шығады).

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

Қатынас: жиынында анықталған R қатынасы деп декарттық көбейтіндінің ішкі жиының айтамыз. Бұл жағдайда жиыны домендер деп аталады, декарттық көбейтінді элементтері кортеждер деп аталады, n саны қатынас дәрежесін анықтайды, ( n=1 - унарлық, n=2 - бинарлық, ..., n-арлық) кортеждер саны қатынас қуаты деп аталады.

Қатынасты кесте түрінде көрсету қолайлы. Суретте, өнеркәсіп жұмысшылары туралы бірқатар деректербар кесте өрнектелген (қатынас дәредесі 5). Кесте жолдары кортеждерге сәйкес келеді. Әрбір жол, сипаттамалары бағанада орналасқан, нақты әлемнің бір объектісінің сипаттамасын білдіреді. Реляциялық қатынасты білдіретін кесте жолдары атрибуттар деп аталады.

Әрбір атрибут доменде анықталған, сондықтан доменді берілген атрибуттың мүмкін мәндер жиына ретінде қарастыруға болады. Бір қатынастың бірнеше атрибуттары және де әртүрлі қатынастың атрибуттары бір доменде анықталуы мүмкін.

«Атрибут аты – домен аты» жиындардың аттары бар жұптары «атрибут аты – домен аты» қатынас схемасы деп аталады. Бұл жиынның қуаты – қатынас дәрежесі немесе «арнылығы». Аттары бар қатынастар схемасы деректер базасының схемасы деп аталады. Атрибут мәні кортежді бірмәнді анықтаса, онда ол кілттік (немесе жай ғана кілт) деп атайды. Біздің жағдайымызда, «Табель нөмірі» атрибуты кілт болады. Себебі, өнеркәсіптің әрбір жұмысшысы үшін оның мәні ерекше болады. Егер кортеждер бірнеше атрибуттар мәнің қоса алғанда ғана қайталанса, онда қатынастың қосымша кілті бар болады.

Қатынастың бірнеше кілті болуы мүмкін. Бір кілт әрқашанда бірінші болып хабарланады, оның мәні жаңартылмайды. Қатынастың қалған кілттері мүмкін кілттер деп аталады.

Иерархиялық және желілік модельдердің реляциялық модельден айырмашылығы онда топтық қатынас ұғымы жоқ. Әртүрлі қатынас кортеждері арасындағы ассоциацияны көрсету үшін олардың кілттерінің қайталануы қолданылады. Мысалы, БӨЛІМ және ЖҰМЫСШЫ қатынастары арасындағы байланыс, бірінші қатынастан екіншіге бірінші кілтті «Бөлім нөмірі» көшіру арқылы жүзеге асады.

Басқа қатынастар кілтінің көшірмесі түріндегі атрибуттар ішкі кілттер деп аталады.

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

Сурет.Өнеркәсіптің жұмысшылары мен бөлімдері туралы деректер базасы.

Қатынас қасиеттері.

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

· Кортеждердің реттілігінің болмауы.

· Атрибуттардың реттілігінің болмауы. Атрибуттың мәніне сілтеу жасау үшін әрқашанда атрибут аты қолданылады.

· Атрибуттардың атомарлығы, яғни, домен мәндері ішінде мәндер (қатынастар) жиыны болмауы керек.

Қатынас схемасы, деректер базасының схемасы

Қатынас схемасы – атауы бар жұптар жиыны {атрибуттар аты, домен аты(немесе түрі, егер домен ұғымы қолданылмаса)}. Қатынас схемасының дәрежесі «арлығы» осы жиынның қуатын анықтайды. СОТРУДНИКИ қатынасының дәрежесі төртке тең, яғни ол төрт арлы болып табылады. Егер бір қатынастың барлық атрибуттары әр түрлі домендерде анықталса, атрибуттар атауына сәйкесінше домендер атауларын қолданған дұрыс. Деректер базасының схемасы(құрылымдық мағынада) – атауы бар қатынастар схемаларының жинағы.

Кортеж, қатынас.Берілген қатынас схемасына сәйкес кортеж – қатынас схемасына тәуелді атрибуттар әр атауының бір кірісі бар жұптар жиыны {атрибут атауы, мәні}. «Мән» берілген атрибуттың доменінің мүмкін болатын мәні болып табылады. Сонымен қатар кортеждің дәрежесі мен «арлығы», яғниондағы элементтер саны сәйкес қатынас схемасының «арлығына» сәйкес келеді, яғни кортеж берілген типтің атауы бар мәндердің жинағы.

Қатынас – бір қатынас схемасынасәйкес кортеждер жиыны. Кейде қатынас схемасын қатынас тақырыбы дейді, ал қатынасты қатынас денесі деп атайды. Күнделікті қатынастың көрсеткіші болып кесте табылады, оның тақырыбы болып қатынас схемасы, ал жолдары қатынас-экземпляр кортеждері болып табылады. Осы кезде атрибуттар аттарын осы кестенің бағандары атайды. Сондықтан кейбір кезде «кесте бағаны» айтқанда оны «қатынас атрибуттары» деп ұғынады. Реляциялық ДҚ – атаулары ДҚ схемаларындағы қатынас схемаларының атауларымен сәйкес келетін қатынас жинағы.

Қатынастың фундаментальды қасиеті

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

Кортеж реттілігінің болмауыБұл қасиет қатынас-экземплярдың кортеж жиыны ретінде анықталуынан шығады. Деректер базасының сыртқы жадта сақтау және деректер базасына сұраныс дасау кезінде қатынас кортеждері жиынында ретті сақтауға талаптың болмауы ДҚБЖ иілгіштігін береді. Бұл ДҚ-на сұраныс жасау кезінде , мысалы SQL тілінде, нәтижелеуші кестенің кейбір бағаналар мәндерімен сәйкесінше сұрыпталуын талап етуге қайшы емес.

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

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

Реляциялық ДҚ сыртқы жадының құрылымыРеляциялық ДҚ-ның сыртқы жадының ұйымдастырылуына әсер ететін бірнеше ерекшеліктері бар. Ең маңызды ерекшеліктері мыналар:

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

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

- Деректер базасы объектілірінің физикалық қасиеттерін сипаттайтын ішкі каталогтар, мысалы қатынас атрибуттарының саны, олардың өлшемі, деректер типі; индекс сипаттамасы және т.б.

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

- Бір қатынастың беттерін байланыстыру. Егер сыртқы жадының бір файлында бірнеше қатынастың беттері араласуы мүмкін болса, онда бір қатынастың беттерін қолайлы болса байланыстыру керек. Беттер арасында тікелей сілтемелердіқолданудың тривиальды әдісі транзакцияларды синхрондау кезінде қиыншылықтарға әкеледі. Сондықтан қызмет индектерін пайдалана отырып беттерді жанама түрде байланыстыруға тырысады. Жеке жағдайларда B-ағаштар негізінде беттерді байланыстыру және сыртқы жадыны сипаттаудың жалпы механизмі белгілі.

- Деректер қорын сенімді сақтау талаптарын орындау үшін деректерді сақтаудың үстемдеп тұру керек.

- Жүйенің екі деңгейінің болуы: сыртқы жадының деректерін басқару деңгейі (сонымен қатар жедел жадының буферлерін, транзакцияларды, ДҚ өзгерістерін журналдауды басқару) және тілдік деңгей

Әрине, бұл жағдайда деректер базасының соңғы келісілген қалпын ала алмаймыз, бірақ бұл жоқтан жақсы.

Деректер базасының архивті көшірмесін құрудың әдістері:

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

Ақырлы автоматтың ішкі күйлерін кодтау.

C және D кластарының автоматикасын синтездеудегі ішкі жағдайларды кодтаудың басты мақсаты соңғы автоматтың ішкі күйлерінің барлық кодтарының өзара ортогоналдығын қамтамасыз ету болып табылады. Өйткені, әртүрлі жағдайларда автоматтың (C классының автоматын синтездеу кезінде) немесе әртүрлі мемлекеттерге (D сыныбының автоматының синтезінде) ауысу кезінде ортогоналды шығу векторлары пайда болуы мүмкін. Егер бұл орын алса, ішкі кодтардың өзара ортогоналдығын қамтамасыз ету үшін қосымша кодты енгізу қажет [9].

Cурет автоматының S автоматының синтезінде ішкі күйлерді кодтау туралы қарастырайық. 7. Осыны жасау үшін біз ішкі регламенттерге сәйкес келетін үшөлшемді матрицасы W және түпкілікті автоматтың шығу айнымалыларына арналған бағандарды саламыз. В матрицасының жолдары сәйкес күйлерде қалыптасатын шығыс векторларының мәндерімен толтырылады (2-кесте, бағандар e3, e2 және e1).

Таблица 2. Матрица W для кодирования внутренних состояний автомата класса C

	e₃	e₂	e₁	e₀
s0	0	0	0	0
s1_1	0	0	1	0
s1_2	1	0	0	1
s2	0	1	0	0
s3	1	0	0	0
s4	0	1	1	0

жеке разрядтар шығыс векторлары анықталмаған мәндер болуы мүмкін, өйткені, жалпы, матрица W үштік, және Boolean емес екенін ескеріңіз. матрица Вт Қосымша бағандар өзара ортогоналды шарттарына кодтарын қамтамасыз ету үшін енгізіледі қосымша кері байланыс айнымалыны сәйкес келеді. міндет енді қосымша коды бит (матрицалық W қосымша бағандар) ең төменгі санын енгізу болып табылады және матрицалық W барлық жолдар өзара ортогоналды етіп М коды бит (матрицалық W қосымша бағандарының мәндерін анықтау) қосымша жолдарды кодтау. матрица W келесі жолдарда кодтары сынып автомат С ішкі күйлерін анықтауға болады

Дата добавления: 2018-08-06; просмотров: 571; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒

Мы поможем в написании ваших работ!