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

• Қолданушының программасының сәтсіз аяқталуы нәтижесінде транзакция сәтсіз аяқталады.

Аталған істен шығулардан соң деректер базасын қалпына келтіру үшін қосымша ақпарат керек. Соның бірі – деректер базасына жасалған өзгерістерді журналға жазып отыру.

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

Қатаң істен шығудан соң деректерді қалпына келтіру үшін ДҚ – ның журналы мен ДҚ – ның архивтік көшірмесі қолданылады. Архивтік көшірме – деректер базасындағы журналды толтырғанға дейінгі деректер базасының толық көшірмесі.

• Деректер базасының тілдерін қолдау (поддержка). Деректер базасымен жұмыс істеу үшін арнаулы тілдерді қолданамыз. Көбінесе екі тіл:

1) Деректер базасының схемасын анықтау тілі (SDL– Schema Definition Language)

2) Деректерді манипуляциялау тілі (DML– Data Manipulation Language)

Қазіргі ДҚБЖ – де бірыңғай біріктірілген тіл SQL қолданылады. SQL тілінде (Structured Query Language) – ДҚ – ның жұмыстарына қажетті, яғни деректер базасын жасаудан бастап, деректер базасымен қолданушылардың интерфейсін қамтамасыз ететін барлық жабдықтар бар.

Қазіргі заманғы реляциялық ДҚБЖ – нің ішкі құрамын былайша анықтауға болады:

1) ДҚБЖ – нің ядросы (көбінесе Data Base Engine деп атайды)

2) Деректер базасының тілінің компиляторы (көбінесе SQL)

3) Орындалу уақытын қолдаудың ішкі жүйесі

4) Утилиттер жиынтығы

Кей ДҚБЖ – де бұл құрам анық байқалады, кейбіреуінде білінбейді. Алайда логикалық түрде барлық ДҚБЖ – ін ішінен осылай бөлуге болады.

ДҚБЖ – ның ядросы – сыртқы жадтағы деректерді басқаруға, жедел (оперативті) жадтағы буферлерді басқаруға, транзакциялар мен журнализацияны басқаруға мүмкіндік береді. Осыған сәйкес оның логикалық түрде мынандай компоненттерін анықтауға болады.:  

a) деректер менеджері;

b) буферлер менеджері;

c) транзакциялар менеджері;

d) журнал менеджері.

Бұл компоненттердің қызметтері өзара байланысқан, ДҚБЖ дұрыс жұмыс істеу үшін бұл компоненттер хаттамалар (протоколдар) арқылы өзара әрекеттеседі. ДҚБЖ – ның ядросының SQL компиляторы жасайтын программаларда және ДҚ – ның утилиттерінде қолданылатын өз интерфейсі бар, қолданушы онымен тікелей жұмыс жасай алмайды, тек SQL арқылы ғана байланыса алады. ДҚБЖ – ның ядросы ДҚБЖ – нің негізгі резидентті бөлігі, ал «клиент – сервер» архитектурасында жүйенің серверлік бөлігінің негізгі құрамы болады. Реляциялық ДҚБЖ – нің негізгі проблемасы бұл жүйенің тілдері (SQL) процедуралық емес, яғни бұл тілдің операторларында деректер базасына жасалатын әрекеттер көрсетіледі, қалайтын әрекеттерді орындаудың шарты анықталады, ол анықтаулар процедура емес.

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

Деректер базасының утилиттерінің қызметіне – деректер базасын жүктеу, босату (выгрузка), деректер базасы туралы статистика жинау, ДҚ – ның бүтіндігін тексеру сияқты процедуралар жатады. Утилиттердің программасы ДҚБЖ – нің ядросында немесе оның интерфейсін қолдану арқылы жасалады.

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

ДҚБЖ негізгі функциялары

• деректерді сипаттау мен манипуляциялаудың тілдік құралдарын қамтамасыз ету;

• деректердің логикалық моделін қолдауды қамтамасыз ету;

• деректердің логикалық және физикалық құрылымдарының өзара әрекеттестігін қамтамасыз ету;

• деректердің қорғанысы мен бүтіндігін қамтамасыз ету;

• деректер базасын актуальды куйде ұстауды қамтамасыз ету;

• сыртқы жадтағы деректерді тікелей басқару;

• жедел (оперативті) жадтың буферлерін басқару;

• транзакцияларды басқару және журнализация;

 

ДҚБЖ түрлері:

1. тілге байланысты:

• көбінесе аралас типті, яғни SQL тілі кеңейтілген бір немесе бірнеше әмбебаб программалау тілдері бар;

• ашық типті - әмбебаб программалау тілдерін қолданады;

• тұйық типті - қолданушының жеке программалау тілі болады;

2. архитектурасындағы деңгейлердің санына байланысты:

• бір деңгейлі - тек физикалық модель қолданылады;

• екі деңгейлі - физикалық және концептуальдық модельдер қолданылады;

• үш деңгейлі - физикалық, концептуальдық және сыртқы модельдері бар;

3. қызметтеріне байланысты:

• ақпараттық - сақтау және ақпаратқа қатынауға рұқсат береді;

• операциялық - ақпаратты күрделі өңдеуге мүмкіндік береді;

4.қолдану саласына байланысты:

• әмбебаб;

• арнаулы;

5. деректер типіне байланысты:

• деректер типтерінің нақты жиынтығы бар;

• кеңеймелі ДҚБЖ - жаңадан деректердің типтері мен оларға жасалатын операцияларды анықтауға болады (объектіге бағытталған ДҚБЖ);

6. желі арқылы деректер базасымен әрекеттесуді ұйымдастыру тіліне байланысты:

• орталықтандырылған архитектуралы ДҚБЖ;

• файл-сервер архитектуралы;

• клиент - сервер архитектуралы;

• үш деңгейлі архитектуралы;

7.ақпараттық жүйе мен деректер базасыныңмасштабына байланысты:

• дара;

• топтық;

• корпоративтік және т.с.с. болып бөлінеді.

 

ДҚБЖ, көбінесе олар қолдайтын деректердің модельдерінің типі бойынша жіктелінеді. Соған орай ДҚБЖ-сін желілік, иерархиялық, және реляциялық деп бөледі.

ДҚБЖ-нің типтік ұйымдастырылуы.

Қазіргі заманғы реляциялық ДҚБЖ-нің ішкі құрамын мына түрде анықтауға болады:

1) ДҚБЖ-нің ядросы (көбінесе Data Base Engine деп атайды);

2) деректер базасы тілінің компиляторы (көбінесе SQL);

3) орындалу уақытын қолдаудың ішкі жүйесі;

4) утилиттер жиынтығы.

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

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

Деректер базасының утилиттерінің қызметіне деректер базасын жүктеу, босату, деректер базасы туралы статистика жинау, деректер базасының бүтіндігін кең ауқымды түрде тексеру сияқты процедуралар жатады.

Қолданушы сұратуының жүру процесі

Деректер базасының контекстінде қолданушы терминінің екі негізгі мағынасы бар:

• Бұл жұмыс орындау үшін деректер базасына кірген адам;

• Бұл қолданба схемасының аймағы, мұнда осы қолданба пайдаанатын объектілер.

3. Грамматикалардың сыныпталуы: регулярлық, контексті-бос, контексті-тәуелді, жалпы түрдегі, атрибутты, программалық грамматикалар

Грамматикалардың классификациялануы: регулярлық, контексті-бос, контексті-тәуелді, жалпы түрдегі, атрибутты, программалық грамматикалар.

Грамматикада анықталған 3,2 разрядында a®b-ға шығу ережесінде екеуінің біреуі a тізбегінде терминальды емес болуы керек. Праграммалау тілінің сипаттамасы және оларды оқып білу көбінесе грамматика тілінде қызықты болады және шығару ережесі дәлелдеуді талап етеді

Формальды грамматиканың анықталу облысында [3, 6, 9, 34, 35,48] Хамаскидің классификациясы қабылдайды, грамматиканы ереже түріне байланысты 4 класқа бөледі:грамматиканың түрі және грамматиканың жалпы түрі G=(N, SP, S) бұл грамматика У шығу ережесінің түрінде a®b, ол a V*NV*,ab V* .

Грамматиканың жалпы түрі мәннің қызықтысын қабылдайды, олар тым бос, бұларды программалау тіліндегі синтаксисті жазуда қолдануға болады. Табиғи тілге арналған синтаксисте қолданылады. 0 грамматикалық түрдегі мысал G=( {A, S}, {0,1}, P, S) программасына негіз болады және P={S®0A1, 0A® 00F1,A ®e}.

Бірінші грамматика түрі немесе конспект- тәуелді грамматика бұл G=(N, SP, S) граммтикасы шығу ережесі түрінің g1А g2®g1bg2 одан g1, g2 V,A N,ab V+. Конспект оң және сол жақ g1және g2 аталуы бойынша сәйкестендіріледі және тізбектеледі. Олар шығу ережесінің тапсырмасы бойынша шарт орындалады: конспект g1,g2 тізбектері әр уақытта терминальды емес грамматикада a және b тізбегімен ауыстырылады.

Конспект тәуелді грамматика тілде конспект тәуелді тіл деп те аталады. Грамматикада конспект тәуелді грамматика мен тіл кластарын сәйкестендіреді, оны [9] -бен дәлелдеуге де болады. Ол грамматикада қысқартылмайтын деп те аталады, шығару ережесінің a®b орындау кезінде мына шартты қанағаттандырады½a£½b½.

Демек бұл алгоритмде немесе шекті сандарды анықтау кезінде терминалды тілде не жатады немесе жатпайды. Қысқартылмаған грамматика мына мысалда көрсетілген: G=( {B,C,S} ), {a,b,c},P,S) P={S aS,B,C, S abc; CB BC, bB bb, bC bc, cC cc).

Екінші грамматикалық түрі немесе конспект бос грамматика – бұл G=(N, S,P,S) грамматика шығару ережесінің мынадай түрін береді. А®В , немесе АÎN,abÎV*.

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

Қатынас (®) - метолингвистикалық байланыста былай белгіленеді: (::=) шығу ережесінің терминалды және терминалды емес тізбектерінің бөлігі – метолингвистикалық формулада екіге бөлінеді: математикалық қоңырау тізбегі және тілдің басты символдарының оң жақ бөлігі.

Үшінші грамматикалық түрі – автоматты және регулярлы грамматика бұл G=(N, S,P,S) шығару ережесінің түрі А®ab немесе А®a, онда А,ВÎN, aÎSU{E}.Автоматты грамматика тілде конспект тәуелді тілі немесе автоматты және регулярлы грамматика деп аталады. Рекурсивті конспект-тәуелді грамматиканың байланысы

Еске түсірсек грамматика G=(Vn, Vt, P,S) - рекурсивті деген не, егер алгоритм бар болса, ол көбінесе анықталады. Кейбір нақты тізбекте хÎV*t нақты грамматика G-ге тең болады, егер G=(Vn, Vt, P,S)-конспекстті-тәуелді грамматикаға байланысы болса. Тексерейік, нақты грамматиканың бос сөйлемі жоқ немесе жай ғана. Ережеде S®e L(G1), eÎL(G) сонда және тек сонда ғана, егер S®eÎP, eÎL(G), және жаңа грамматика құрастыруға болады:

G=(Vn, Vt, P,S), ереже болмайды S®e, тағы солай P=P1/{ S®e}.

Грамматика G1 тағы конспект байланысы және L(G1)= L(G1)/{ e}. Әрбір шешу ұзындығы сентенциалдық формада үлкейеді. V грамматикасы сөздікте К символында біріктіреді. Жалғасы, SÞх1бe½|a|£|a|£|a| Сентентенциялдық формасы аі, а ...,а бәрі сол бір ұзындық, P әртүрлі ұзындық тізбегі, V алфавит символы, к символ, кр ендік. Біздідің қарастырған j+1 тізбегі j>k7

Теорема 2.2: Егер грамматикада G=(Vn, Vt, P,S)- конспект байланысы немесе рекурсивті болса

Дәлелдеу: қолдану бар болса шынында eÎ L(G1) егер осылай болса, онда грамматика ережесі S®e, грамматиканы аламыз, көбінесе бір тіл, немесе бос сөз. Р ережені тоқтатпайды S®e, қарастырылған тізбекте хÎV*t . Біздің тапсырмада алгоритмді табу, хÎ L(G1) мына сұрақты шешеміз: |х|=n(n>0). Тm келесі бейне мүмкін. Tm=Tm-1U{a}β→αβε

Контексті-бос грамматикалармен(КБ-грамматикалар)  тудырылған тілдер тобы стекті автоматтармен (СА) танылған тілдер тобына дәл келетінін көрсетуге болады. Бұл берілген КБ-грамматикаға сәйкес бейдерминді СА тұрғызу және керісінше СА-қа сәйкес КБ-грамматика құру керек.

Контексті тілдердің тудырушы механизмдері ретінде 1-ші типтегі грамматикалар болады және олар контексті-тәуелді (контексті) грамматикалар деп аталады. Оларға тікелей құраушылар грамматикалары және қысқармайтын грамматикалар жатады. Контексті тілдердің танығыш механизмдері ретінде сызықты шенеуленген автоматтар болады.

 

№ 4 БИЛЕТ 

 

1. Алгоритмдерді талдау принциптері. Функцияның өсуі. О-нотация

Алгоритмдерді талдаудың негізгі әдістері:

- Сөздік-формулалық (табиғи тілдерде);

- Құрылымды немесе блок-схемалар;

- Арнайы алгоритмдік тілдерді қолдану;

- Граф-схемалар көмегімен (граф – әр сызық екі нүктені қосатын, нүктелер мен сызықтар жиынтығы). Нүктелер шыңдар деп аталады, сызықтар – қабырғалар;

- Петри торының көмегімен.

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

О-нотация

Алгоритмдердің еңбеккөлімін бағалау үшін арнайы жүйе О-нотация енгізілді. Бұл нотацияf (n) функциясындағы тек мағыналы элементтерді ғана есептеуге мүмкіндік береді. Мысалы, f (n) = 2n2 + n – 5 функциясында n үлкен шамасында n2 компонентасыда айтарлықтай өседі, яғни басқа қосындаыларды есептемеуге болады. Сондықтан бұл функция О(n2 ) түріндегі бағалауға ие. О-бағалау барлық негізгі функциялар компоненттердің өсу жылдамдығынан тәуелді бөлуге мүмкіндік береді:

1. О(1) типтегі Тұрақты функция 

2. О(log 2 n) өсу жылдамдықты логарифмдік функция

3. О(n) өсу жылдамдықты сызықтық функция

4. О(n*log 2 n) өсу жылдамдықтағы сзықты-логаримдік функция

5. О(n2 ) өсу жылдамдықтағы квадратты функция

6. а>2 кезінде өсу жылдамдықты кезеңді функция

7. О(2n) өсу жылдамдықты көрсеткішті немесе экспоненциалды функция

8. О(n!) деңгейлі өсу факториалды функция

2. ДҚ көрсету деңгейлері. Деректер құрылымы. Динамикалық және статикалық құрылымдар. Деректердің логикалық және физикалық құрылымы. Деректерді сақтау құрылымдары

---

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

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

---

---

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