Лекции по бази данни



страница1/10
Дата16.12.2016
Размер1.96 Mb.
ТипЛекции
  1   2   3   4   5   6   7   8   9   10
Лекции по бази данни
Писани са от мен, Иван Димитров Георгиев (вече завършил) студент по информатика, електронната ми поща е ivandg@yahoo.com.

Четени през летния семестър на учебната 2003/2004 година.

Лектор тогава беше доц. Владо Димитров.

Използвал съм мои (и на мои колеги) записки от лекции. Основно, обаче, материалът е от книгата Начален курс в СУБД на Джефри Улман.



Увод в системите бази от данни
Базите от данни са в основата на всеки бизнес. Освен това, те намират редица приложения при научни изследвания.

Базите от данни се управляват от специален софтуер, който ще наричаме СУБД (система за управление на бази от данни).

СУБД представлява мощен инструментариум за създаване и ефективно управление на големи обеми от данни. Данните трябва да се поддържат и съхраняват за толкова време за колкото е необходимо. Освен това, те трябва да се предпазват от неправилен достъп, който може да наруши целостта им (integrity), както и от неправомерен достъп (security).

Поради това, в наши дни СУБД е доста сложен софтуер.

Примери за СУБД са Oracle, DB2, Microsoft SQL server. Първите две системи, за разлика от третата се използват в сериозни организации.
По-нататък под база от данни ще разбираме наборът от данни, които се поддържат в даден момент от една СУБД.
От потребителска гледна точка една СУБД трябва да притежава следните свойства:


  • устойчива памет – данните трябва да се съхраняват независимо от процесите; базите от данни трябва да позволяват ефективен достъп до много големи обеми от данни – времето на достъп до данните трябва да е независимо от техния обем;

  • програмен интерфейс – СУБД предоставя мощен език за заявки на потребителя или на приложната програма, която използва данните;

  • управление на транзакции – СУБД поддържа едновременен достъп до данните; той се осъществява чрез множество процеси, наречени транзакции; всеки потребител, който работи с данните трябва да инициира такъв процес; СУБД поддържа изолация на транзакциите – всяка транзакция е атомарна, т.е. тя или завършва изцяло или бива изцяло отхвърлена; ако по време на изпълнение на една транзакция възникне проблем тя се отменя, заедно с всички изменения, които е причинила върху базата от данни;

  • устойчивост на данните – при възникване на аварии или грешки данните трябва да могат да бъдат възстановени; естествено, това е свързано с допълнителни операции за четене и писане.

От архитектурна гледна точка една СУБД трябва да предоставя следните функции:



  • СУБД позволява на потребителя да създава нови бази от данни;

за целта потребителят задава схема на базата от дании; схемата е логическа структура на данните и тя се описва с помощта на специален език за дефиниция на данните (DDL – data definition language); този език е символен или графичен;

  • СУБД трябва да осигури възможност за търсене в данните и за модификация на данните; това се постига с помощта на език за манипулация с данните (DML – data manipulation language); езикът за заявки е подезик на езика за манипулация с данните, който се използва при търсене на данни;

  • СУБД трябва да съхранява безопасно и дългосрочно много големи обеми от данни; съхраняването трябва да осигурява ефективно търсене и изменение на данните;

  • СУБД трябва да управлява едновременен достъп до данните от много потребители - те не трябва да си влияят един на друг и да развалят целостта на данните.


Еволюция на СУБД
Първите СУБД се появяват през 60-те години като резултат от развитието на файловите системи най-вече в посока към безопасно и дългосрочно съхранение. Те намират приложение при резервацията на самолетни билети, при банковите системи, при корпоративните записи и др. При тях визуализацията на данните е така както те се съхраняват.

Естествената еволюция на файловите системи доведе до поява на следните два модела:



  • йерархичен модел – например IMS на IBM; при него данните са във вид на дърво; в действителност някои данни може да присъстват в повече от едно дърво, ако към тях се използват връзки (reference);

  • мрежови модел – този модел се появи по-късно; при него навигацията в данните е на значително по-високо ниво.

През 70-те години за пръв път се появиха СУБД, които се подчиняват на така наречения релационен модел, който измести напълно другите два модела. Този модел е разработен от Тед Код (Ted Codd).

При релационните СУБД за първи път се появява език за заявки от високо ниво.

Релационният модел почива на сериозни математически основи, което стимулира серия от изследвания в областта на базите от данни.

Този модел е изключително прост от гледна точка на потребителя – използва се само една структура от данни, наречена таблица (релация). Реализацията на таблицата е скрита за потребителя. Използват се езици за заявки от високо ниво. Примерна таблица:




accountNo

balance

type

01234

1000.00$

savings

56789

3849.40$

checking

В таблицата всяка колона си има име, което се нарича атрибут (accountNo, balance, type). Всеки ред в таблицата се нарича кортеж (имаме два кортежа). В рамките на една колона стойностите са еднотипни.


Езикът SQL (structured query language) е разработен във връзка с реализацията на релационния модел. В наши дни по стандарт всички СУБД използват SQL. Направени са изследвания, които показват, че

най-честите заявки са в рамките на една таблица. Поради тази причина, основната конструкция, която се използва в SQL е следната:



SELECT име_на_атрибут

FROM име_на_таблица

WHERE условие

Условието може да има следния вид име_на_атрибут=стойност.

В зависимост от типа вместо равенство може да се използва някой друг предикат за сравнение. Няколко условия могат да се комбинират с помощта на логическите съюзи.

Ще опишем как се изпълнява конструкцията. В таблицата, зададена във FROM клаузата се извършва търсене по всички кортежи, като се проверява условието, зададено в WHERE клаузата. SELECT клаузата определя кои атрибути на намерените кортежи да бъдат изведени. Примери: (предполагаме, че горната таблица се казва Accounts)



SELECT balance

FROM Accounts

WHERE accountNo=01234

Тук ще се изведе 1000.00$.



SELECT accountNo

FROM Accounts

WHERE type=’checking’ AND balance > 0

Тук ще се изведе 56789.


СУБД оптимизират заявките за да може те да бъдат ефективно изпълнени.
През средата на 90-те години се появиха обектно-ориентирани СУБД.

Въпреки че не успяха да се наложат, те повлияха на релационния модел и в наши дни СУБД работят с обектно-релационен модел. Този модел е разширение на обектно-ориентирания модел, но запазва пълна съвместимост с релационния модел. Обектно-ориентираният подход е водещ при проектирането на софтуер и данни в наши дни.

Има тенденция СУБД да са вградени в операционните системи и в бъдеще да изместят файловите системи.
СУБД се развиват в посока на съхранение на данните във връзка с мултимедията, която е много голям по обем (например от порядъка на терабайтове). Концепцията на работа на една СУБД е, че данните се обработват в оперативната памет, а се съхраняват върху дискове. Проблемът при големите бази данни е, че дисковете все още не са достъчно големи. Поради тази причина се промени моделът за съхранение на данните. Той беше на две нива – оперативна памет и вторична памет. Сега вече се появи и третична памет – шкафове с носители, които се управляват от роботи (например Juke Box, лентови силози). Недостатъкът е, че времето за достъп до третичната памет е много голямо – приблизително няколко секунди, за разлика от вторичната памет, при която това време е около 10-20 ms.
За да може да се оптимизира управлението на различните памети се използват индексна структура на данните или паралелизъм в няколко варианта. Паралелизмът може да означава паралелно работещи процесори, паралелно работещи дискове. Възможно е използването на така наречените разпределени системи – при изпълнението на една заявка тя се разбива на няколко части, които се обработват от различни разпределени компютърни системи.
Концепции в развитието на СУБД
Client-server е архитектура, при която един процес (клиент, client) изпраща заявка за изпълнение към друг процес (сървър, server). Когато сървърът изпълни заявката, той връща данните на клиента. Естествено, СУБД е сървърът, а клиентите са потребителите или приложните програми. При такава организация се постига полезно натоварване на мрежата.

Проблем при архитектурата client-server е претоварването на сървърите. Поради тази причина се налагат архитектури client-server с множество нива. При тях СУБД отново е сървърът, но негови клиенти са така наречените приложни сървъри. Те имат за клиенти уеб-сървъри, които вече взаимодействат с потребителите. Приложните сървъри имат за задача да реализират бизнес-логиката на СУБД. Чрез такова разслоение отговорността за изпълнение на заявките се поделя между различни компютърни системи.


Един проблем на съвременните СУБД е търсене в мултимедийни данни. Възможно е мултимедийните обекти да се индексират с ключове, по които да се осъществява търсенето. Такъв подход, обаче, е неприложим в следните ситуации – търсене на кадър от филм, търсене на фрагмент от картинка и т.н.

Обектно-релационният модел поддържа операции за работа с мултимедийни обекти. Стремежите са данните да се визуализират пред потребителя във виртуална реалност.


Има тенденция когато една база от данни се създаде, тя да може занапред да съществува самостоятелно. За целта се използват складове за данни (data warehouse), в които информацията се интегрира и унифицира. Във връзка с постиженията в изкуствения интелект са разработени така наречените OLAP технологии (OLAP technologies), които позволяват ефективен анализ на данните в складовете. С тези технологии може да се осъществява търсене по образци (data mining).

Структура на СУБД

DDL команди

Потребителят дава заявка към системата. Това става в интерактивен режим. Възможно е това взаимодействие да се осъществява чрез приложение. Самите заявки не променят базата от данни, докато при обновяване тя се променя.



Компилаторът на заявките изяснява дали синтаксисът на заявките е правилен и след това проверява тяхната семантика. В крайна сметка компилаторът на заявките изработва план на заявката. Обикновено този план е във вид на дървовидна структура. Във възлите на структурата стоят операции от релационната алгебра, а в листата се намират константи, имена на атрибути или цели таблици. Тъй като заявките са от високо ниво се изисква те да бъдат оптимизирани. Това е функция на компилатора на заявките. Всъщност, той се състои от три части:

  • синтактичен анализатор;

  • семантичен анализатор;

  • оптимизатор на заявки.

При оптимизиране на заявките възниква един фундаментален проблем – езиците за заявки са ориентирани за сравнително прости заявки. Например, SQL е разработен върху концепцията, че най-често заявките са в рамките на една таблица, по-рядко върху две таблици и много рядко върху три или повече таблици. При оптимизиране на проста заявка може да се загуби ефективност – времето за оптимизиране да надхвърля многократно времето за изпълнение на заявката.

Обикновено в интерактивен режим заявките не се оптимизират. Когато обаче една заявка се съхранява, т.е. тя ще се изпълнява много пъти, то тя се оптимизира. Освен самият сорс на заявката се съхранява и нейният оптимизиран план (естествено, оптимизацията се извършва само веднъж при първото изпълнение на заявката).


Изпълнителната машина има за задача да изпълнява заявките по плана, който е предоставен от компилатора на заявките. Изпълнителната машина изпраща заявки към файлове и заявки към индекси за да извърши своята работа. Всъщност, изпълнителната машина използва различни методи на достъп, познавайки вътрешната структура и организация на физическо ниво на таблиците. Независимо от метода на достъп, той се поддържа във вид на страници.
Външната памет реално е организирана на страници, т.е. четенето и писането се извършва постранично. Размерът на една страница може да е 4K, 16K и др. Обикновено данните се прехвърлят между оперативната памет и външната памет. При СУБД ефективността на една заявка се измерва в това колко постранични операции (прехвърляния) се извършват при нейното изпълнение.
Управлението на външната памет реално извършва четенето и писането върху външната памет.

Управлението на буферизацията се занимава с това дали търсените страници не се намират в буферите на оперативната памет. По този начин се спестяват дискови операции.


Обикновено оптимизациите на заявките се извършват независимо, т.е. съобразно само една заявка. Има СУБД при които в компилатора на заявките постъпват по няколко заявки едновременно, които се компилират в общ план и съответно върху тях се извършва обща оптимизация. Ефективността на такава стратегия силно зависи от управлението на буферизацията.

Транзакциите са процесите в СУБД. Изпълнението им трябва да бъде такова, че те да не си влияят една на друга и да изглежда все едно се изпълняват последователно една след друга.

Когато един потребител работи интерактивно със системата, всяка негова заявка се счита за една транзакция. Той, обаче, може да изпълнява няколко заявки в рамките на една транзакция с помощта на специални команди. Има и други команди за управление на транзакциите.


Модулът управление на транзакциите използва друг модул – журнал,

в който се регистрират транзакциите. По време на изпълнението на една транзакция, изпълнителната машина записва в журнала всякакви промени, които извършва върху транзакцията. Грубо казано, журналът се състои от записи. Всеки запис има нова част и стара част. Изпълнителната машина извършва промените върху новата част. Ако по време на изпълнение на транзакцията възникне проблем, т.е. тя не успее да завърши, чрез старата част на записа се възстановява старото състояние на базата от данни.


Администраторът на базата от данни отговаря за нейната структура. Освен това, той може да дава различни права на достъп (например read, write, read/write) на други потребители. Администраторът дефинира схемата на базата от данни като подава DDL-команди на

DDL-компилатора. Самите DDL-команди след компилация се изпълняват от изпълнителната машина.


Управлението на едновременния достъп е модул, който има за задача да гарантира атомарността на транзакциите. Това става с помощта на таблици на блокировката, които се намират в оперативната памет.

Когато една транзакция се обработва от модула управление на транзакциите, то е известно кои таблици ще се използват за четене/писане в рамките на транзакцията. Тогава този модул се обръща към управлението на едновременния достъп, при което се блокират съответните таблици (релации). В таблицата на блокировката се съдържа информация кои от релациите са блокирани само за четене или за четене и за обновяване. Ако се прави опит за повторно блокиране за четене, няма проблем, т.е. от една релация едновременно могат да четат много транзакции. От друга страна, само една транзакция може да блокира релация за обновяване, т.е. ако една транзакция пише в релация, то други транзакции нямат достъп до тази релация (нито за четене, нито за обновяване). Най-често блокировката се извършва на отделни релации. Възможно е блокировката да се извършва на ниво кортежи, т.е. върху една и съща релация може да работят едновременно няколко транзакции, но върху различни кортежи. Ако блокировката е на по-едро ниво, то се губи ефективност. Ако блокировката е на по-ситно ниво, то се усложнява значително управлението на едновременния достъп.


Транзакциите са процеси – възможно е няколко транзакции да попаднат в дедлок. Механизмът, който се използва за преодоляване на този проблем е откриване и възстановяване от дедлок – всички транзакции, които участват в дедлока се елиминират.
Буферите се намират в оперативната памет и с тях взаимодейства модула управление на буферизацията. Ако една страница се прочита от външната памет, то тя първо се записва в буферите.
Изпълнителната машина взаимодейства с модула за управление на едновременния достъп – например, тя изпълнява командите на този модул.
Журналът се управлява самостоятелно и работи пряко с управлението на буферизацията. Всички останали модули се изпълняват на изпълнителната машина. Журналът, обаче, слиза на по-ниско ниво, тъй като той се нуждае от гаранция, че неговите изменения са направени върху диска преди да се обработва базата от данни.
Метаданните са описание на схемата на базата от данни и те се разполагат в буфери в оперативната памет. DDL-компилаторът се нуждае от метаданните – например, ако администраторът изменя

базата от данни.

Журналните страници също се разполагат в буфери в оперативната памет. Компилаторът на заявките също има свои буфери – метаданни, които се използват при проверка на семантиката и статистики, които се натрупват от СУБД и се използват при оптимизиране на заявките.

В хода на своята работа изпълнителната машина също използва

буфери – метаданни, данни, индекси.
Често при описание на свойствата на транзакциите се използва съкращението ACID – атомарност (atomicity), цялостност (consistency), изолирано изпълнение (isolation), надеждност и устойчивост (durability).
По-отношение на СУБД се изучават следните компоненти:


  • проектиране на базите от данни – каква информация се съхранява в базата от данни;

  • структура на базата от данни – какви структури от данни, типове от данни се използват и какви са връзките между типовете данни;

  • програмиране на базата от данни – програмиране на заявки и на конвенционални програми;

  • реализация на СУБД – този въпрос няма да го разглеждаме подробно.


Модел на данните същност-връзки

(Entity-Relationship, ER)
Този модел на данните се използва главно за проектиране на бази от данни. Процесът на проектиране на една база от данни започва от това каква информация да се съхранява в нея. В общия случай това е доста труден въпрос – нужни са познания в приложната област.

Процесът на проектиране можем да разделим на две части:



  • определяне на информацията в базата от данни;

  • определяне на връзките между компонентите на информацията.

Моделът ER дава възможност с определени структури да се опишат същности, а с други структури да се опишат връзките между тези същности.


Схемата на базата от данни се описва с помощта на език или друга подходяща нотация. След като бъде описана схемата на базата от данни, изпълнителната машина трябва по подходящ начин да превърне тази схема във физическа база от данни върху диска. В съвременнните СУБД обикновено описанието се прави ER, след което това описание се транслира към SQL и тогава се подава на DDL-компилатора.

Друг подход за описание на базата от данни е обектно-ориентираният подход. При този подход се използват така наречените UML-диаграми. Те са ориентирани по-скоро към описание на софтуера, отколкото описание на самите данни както е при ER-диаграмите.

Недостатък на релационния модел при проектиране е, че структурата която се използва е само една – таблицата (релацията). Чрез тази структура трябва да се описват както същностите, така и връзките.

Затова при проектиране се предпочита ER-модела пред релационния модел.


При модела ER съществени елементи са множествата същности, множествата атрибути и множествата връзки.

Същността е нещо, което се възприема самостоятелно, т.е. което може да бъде отделено от другите същности. Същността може да е предмет, явление, но може да бъде и абстрактно понятие.

При проектирането на информацията е важно до каква степен тя е детайлизирана. Една същност се описва с конкретни стойности за нейните атрибути. Стойностите на атрибутите могат да бъдат атомарни, т.е. числа, дати, низове и др. Друг вариант е стойностите на атрибутите да са цели структури с фиксиран брой компоненти. В нашите разглеждания ще считаме, че всички стойности на атрибути са атомарни.

Между две или повече множества от същности може да има връзки. Най-простите връзки са бинарни, но може да има и по-сложни връзки между повече от две множества същности.


Схемата на базата от данни при модела ER се описва с диаграма същност-връзки (диаграма ER), която представлява граф. Множествата същности се представят с правоъгълници, атрибутите се представят с овали, връзките се представят с ромбове. Ще разгледаме един пример.

Stars и Studios са различни множества от същности, въпреки че имат едни и същи атрибути. Правило е да се използват колкото се може

по-малко атрибути. Естествено, същностите и атрибутите трябва да са така подбрани, че да отразяват адекватно реалния свят.
Диаграмата ER е описание на схемата на базата от данни. С нея не се описва конкретното съдържание на базата от данни. Конкретните данни се наричат екземпляр на базата от данни и те могат да се менят с времето, докато схемата на базата от данни е устойчива и не се променя.

Това е причината по която DML-езика се отделя от DDL-езика.

В екземпляр на базата от данни първо се определят конкретни крайни множества от същности, а след това за всяка конкретна същност се определя конкретна стойност за всеки един от нейните атрибути.

Екземплярът на връзките се представя малко по-специфично.

Нека R е връзка между множествата от същности E1, E2, …, En.

Тогава екземпляр на R е краен списък от наредени n-торки (e1, e2, …, en), където ei е конкретна същност от множеството Ei, i = 1, 2, …, n.

Между две множества от същности може да има повече от една връзка. Много често за визуализация на представянето на една връзка се използва таблица. Ще разгледаме пример.

Нека Sharon Stone и Arnold Schwarzeneger са конкретни същности

от Stars. Нека Basic Instinct и Total Recall са конкретни същности от Movies. Тогава един екземпляр на връзката stars_in може да е следния:


Movies

Stars

Basic Instinct

Sharon Stone

Total Recall

Arnold Schwarzeneger

Total Recall

Sharon Stone

Важна характеристика на една връзка е нейната мултипликативност.

Нека R е връзка между множествата същности E и F.

Ако всеки елемент на E може да бъде свързан с най-много един елемент на F, казваме че R е връзка много към един (many-one) от E към F.

В диаграмата ER за такива връзки се обозначава стрелка от R към F.

Пример от по-горе е връзката owns, което означава че един филм може да бъде притежаван най-много от едно студио.

Ако R е връзка много към един от E към F и R е връзка много към един от F към E, казваме че R е връзка един към един (оne-one)

между E и F. В диаграмата ER за такива връзки се обозначава стрелка от R към F и от R към E. Пример от по-горе е връзката runs, което означава, че едно студио може да има най-много един президент и освен това един президент може да ръководи най-много едно студио.

Ако R не е връзка много към един от E към F и R не е връзка много към един от F към E, казваме че R е връзка много към много

(many-many) между E и F. В диаграмата ER за такива връзки не се обозначават стрелки. Пример от по-горе е връзката stars_in, което означава, че една звезда може да участва в повече от един филм и в един филм могат да участват повече от една звезди.


Връзки между повече от две множества същности се срещат рядко.

Нека E0, E1, …, En са множества от същности и R е връзка. Аналогично на по-горе, казваме че R е връзка много към един от E1, …, En към E0, ако за всеки елемент e1 от E1, e2 от E2, …, en от En съществува най-много един елемент e0 от E0, така че (e0, e1, …, en) е наредена (n+1)-орка от R.

В диаграмата ER за такива връзки се обозначава стрелка от R към E0.

Ще разгледаме един пример.



Връзката в случая е договор на звезда за участие във филм през определено студио. Стрелката означава, че една звезда за определен филм може да сключва договор най-много с едно студио.


Каталог: materials
materials -> Исторически преглед на възникването и развитието на ес
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 12. 2006 г. 4 клас
materials -> Великденско математическо състезание 12. 04. 2008 г. 2 клас Времето за решаване е 120 минути
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 09. 12. 2006г
materials -> Съюз на математиците в българия-секция русе коледно математическо състезание – 12. 2006 г. 8 клас
materials -> Великденско математическо състезание 12. 04. 2008г. 3 клас
materials -> К а т е д р а " информатика"
materials -> Зад. 2 Отг.: 5- 3т Зад. 3 Отг.: (=,-);(+,=);(+,=) по 1т., общо 3т. За
materials -> Іv клас От 1 до 5 зад по 3 точки, от 6 до 10 – по 5 и от 11 до 15 – по 7


Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   10


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница