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

Представяне на небинарни връзки в ODL

Изтегляне 1.96 Mb.

страница	9/10
Дата	16.12.2016
Размер	1.96 Mb.
	#11293
Тип	Лекции

1 2 3 4 5 6 7 8 9 10

Представяне на небинарни връзки в ODL
В ODL се поддържат само бинарни връзки. За да представим небинарна връзка в ODL трябва да разбием тази връзка на бинарни връзки, аналогично на конструкцията, която разгледахме по-горе в ER модела.

Нека имаме небинарна връзка R между класовете C₁, C₂, …, C_n.

За да представим R образуваме нов клас C и връзки много към един от

C към C_i, i = 1, 2, …, n. Всеки обект t от класа C е конкретна връзка между обектите от C₁, C₂, …, C_n, с които е свързан t.

Като пример ще представим връзката Contracts между филмите, звездите и студията. За целта създаваме клас Contract със следната декларация:

class Contract {

attribute integer salary;

relationship Movie theMovie inverse Movie::contractsFor;

relationship Star theStar inverse Star::contractsFor;

relationship Studio theStudio inverse Studio::contractsFor

} ;

Използваме един атрибут salary - това е атрибутът на връзката.

Съответно, в класовете Movie, Star, Studio трябва да добавим следните декларации.

В Movie:

relationship Set contractsFor inverse Contract::theMovie;.

В Star:

relationship Set contractsFor inverse Contract::theStar;.

В Studio:

relationship Set contractsFor inverse Contract::theStudio;.
Наследяване и подкласове в ODL
Подобно на модела ER, където могат да се строят isa-йерархии, в ODL се допуска един клас C да наследи друг клас D. За целта, в декларацията

на C след неговото име се записва ключовата дума extends, последвана от името на класа D.

Ще разгледаме примера с Cartoons и MurderMysteries.

Подкласът Cartoon трябва да наследи класа Movie и към него да се добави допълнителна връзка voices с класа Star, указваща звездите, които озвучават анимациония филм.

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

class Cartoon extends Movie {

relationship Set voices inverse Star::voiceOf;

} ;

class MurderMystery extends Movie {

attribute string weapon;

} ;
Естествено, в класа Star трябва да добавим следната декларация:

relationship Set voiceOf inverse Cartoon::voices;.

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

Например, може да има филми, които са едновременно анимационни и в които има убийства. В модела ER такива филми могат да се включат едновременно в Cartoons и MurderMysteries. При обектно-ориентирания подход, обаче, основен принцип е всеки обект да принадлежи на точно определен клас. Поради тази причина се нуждаем от нов клас, който представя указаните филми. Класът CartoonMurderMystery трябва да наследи двата класа Cartoon и MurderMystery. По този начин получаваме следната йерархия на наследяване:

При множественото наследяване в ODL, ключовата дума extends е последвана от имената на наследените класове, разделени с :.

В горния пример, декларацията на новия клас е следната:

class CartoonMurderMystery extends MurderMystery : Cartoon;.

В случая новият клас няма собствени свойства, а само наследени.
Технически, вторият и останалите наследени класове трябва да са интерфейси, т.е. класове, с които не се асоциират обекти.

По-нататък ще разгледаме по-подробно множеството от обекти, което се асоциира с един клас.

Когато един клас C наследява няколко класа, възниква опасност от дублиране на имената на свойства. Два или повече от суперкласовете

на C може да имат свойства с еднакви имена.

В горния пример нямаше такъв проблем, но да разгледаме друг пример.

Да предположим, че Movie има подкласове Romance и CourtRoom.

Нека Romance има атрибут ending от изброен тип { happy, sad} и

CourtRoom има атрибут със същото име ending от изброен тип

{ guilty, notGuilty }. Ако създадем нов подклас RomanceCourtRoom, който наследява двата класа Romance, CourtRoom, то атрибутът ending се дублира в двата суперкласа и неговият статут в новия клас е неясен.

Решението на подобен конфликт не е част от стандарта на ODL.

Някои от подходите за решаване на проблема са следните:

Забранява се множественото наследяване - естествено, това е прекалено ограничаващ подход.
Изрично се указва, коя от декларациите на дублираните свойства да се използва.
Преименува се някое от дублираните свойства - например, в класа CourtRoom можем да преименуваме ending на verdict.

Разширения на класове
Множеството от обектите на даден клас се нарича

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

Това се постига, като се зададат различни имена за класа и за неговото разширение. Името на разширението на един клас се задава в скоби след името на класа, предшествано от ключовата дума extent.

Общоприетата конвенция е имената на класа и на неговото разширение

да са едни и същи, но името на класа да е в единствено число,

а името на разширението да е в множествено число.

Например, за класа Movie може да се зададе име на разширението по следния начин:

class Movie (extent Movies) {

attribute string title;

…

} ;
Заявките към една база от данни, описана в ODL се извършват посредством имената на разширенията на класовете, а не посредством техните собствени имена.

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

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

Ключове в ODL
За разлика от моделите ER и релационния модел, в ODL ключовете не са задължителни. Причината е, че обектите се идентифицират уникално посредством своите OID. Напълно е възможно в ODL два обекта от един и същи клас да притежават еднакви свойства - системата ще ги различава по техните OID.
Въпреки това, в ODL могат да се дефинират ключове. Един или повече от атрибутите на даден клас могат да се декларират като ключ на класа с помощта на ключовата дума key или keys, последвана от заграден в скоби списък от имената на тези атрибути, разделени със запетаи.

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

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

За класа Movie можем да зададем ключ по следния начин:

class Movie (extent Movies key (title, year))

{ attribute string title;

…

} ;

Може да се използва коя да е от двете ключови думи key, keys при деклариране на ключ.

За класа Star можем да зададем ключ по следния начин:

class Star (extent Stars key name)

{ attribute string name;

…

} ;
Възможно е да се зададе повече от един ключ за даден клас.

За целта, отделните ключове след key (keys) разделяме със запетаи.

Ще разгледаме пример, в който е подходящо използването на два ключа.

class Employee (extent Employees key empID, ssNo)

{ …

} ;

Тук empID е атрибут, чрез който се идентифицират работниците, атрибутът ssNo е техният номер на социална осигуровка.

Изрично отбелязваме, че тази декларация е различна от следната:

class Employee (extent Employees key (empID, ssNo))

{ …

} ;

При нея атрибутите empID, ssNo едновременно образуват ключ, т.е. възможно е, например, два обекта да имат еднакъв empID или ssNo.

При горната декларация два обекта не могат да имат еднакви empID или еднакви ssNo.

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

Също е възможно в ключ на клас да се използва връзка.

Чрез използването на връзка един към много в ключ могат да се представят слабите множества същности. Като пример ще дефинираме клас Crew, който съответства на множеството същности Crews, което разгледахме по-горе при ER модела.

class Crew (extent Crews key (number, unitOf))

{ attribute integer number;

relationship Studio unitOf inverse Star::crewsOf;

} ;

Естествено, в класа Star добавяме следната декларация:

relationship Set crewsOf inverse Crew::unitOf;.

Ограничението, което поставя ключа е никои два екипа-обекти от клас Crew да нямат еднакви номера и да са свързани с еднакви студия.

Това е същото ограничение, което произтичаше от факта, че

Crews е слабо множество същности.

Преобразуване на ODL-проект към схема на релационна база данни
ODL е разработен като език за спецификация за обектно-ориентирани СУБД. Днешните СУБД са обектно-релационни, но ODL не губи значението си. Ще покажем как един ODL-проект може да се конвертира към схема на релационна база от данни. Този процес е подобен на преобразуването на ER-диаграма, но възникват следните проблеми:

Множествата същности задължително имат ключове за разлика от ODL-класовете.
Атрибутите в модела ER задължително са от атомарни типове, докато в ODL няма такова ограничение.
В ODL могат да се задават методи, но няма как те директно да се преобразуват към част от релационната схема. Засега ще считаме, че в ODL-класовете, които преобразуваме няма методи.

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

class Movie (extent Movies) {

attribute string title;

attribute integer year;

attribute integer length;

attribute enum Film { color, blackAndWhite } type;

} ;

Този клас се преобразува към следната релация:

Movies (title, year, length, type).

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

Всеки обект от разширението на класа се представя с един кортеж в екземпляра на съответната релация.
Преобразуване на атрибути от неатомарни типове
Дори свойствата на един клас да са само атрибути, може да възникнат проблеми при преобразуването на класа към релация по гореописания начин. Причината е, че в ODL атрибутите могат да са от неатомарни типове.
Най-простият случай е когато един атрибут има тип структура с полета от атомарни типове. Тогава за всяко поле на структурата в релацията добавяме по един атрибут. Единственият проблем, който може да възникне е дублиране на имена на атрибути. В такъв случай трябва да се извърши подходящо преименуване.
Ще разгледаме пример с класа Star.

class Star (extent Stars) {

attribute string name;

attribute struct Addr { string street, string city } address;

} ;

Този клас се преобразува към следната релация:

Stars (name, street, city).
Сега ще разгледаме как се преобразуват наборните конструктори

Set, Bag, List, Array, Dictionary. Първо ще разгледаме по-подробно преобразуването на наборния конструктор Set.

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

Ще разгледаме пример с разширен вариант на класа Star.

class Star (extent Stars) {

attribute string name;

attribute Set address;

attribute Date birthdate;

} ;

Този клас се преобразува към следната релация:

Stars (name, street, city, birthdate).

За всеки отделен адрес на една звезда има отделен кортеж в екземпляра на релацията Stars. Поради тази причина name, street, city образуват ключ на тази релация. От друга страна, name е ключ на класа Star и тогава name  birthdate е нетривиална функционална зависимост с лява част, която не е суперключ. Това означава нарушаване на BCNF.

В общия случай при преобразуване на един атрибут от тип множество, заедно с няколко атрибути от атомарен тип, които не са част от ключ довеждат до нарушаване на BCNF. Два или повече атрибута от тип множество при преобразуване довеждат до нарушаване на 4NF.
Преобразуването на атрибут от тип Bag се извършва както при атрибут от тип Set. В чистия релационен модел, обаче, не се допуска дублиране на кортежи в релациите. Поради тази причина, трябва да добавим отделен атрибут count в релацията, който показва колко пъти съответният елемент се среща в мултимножеството. Например, ако в класа по-горе типът на атрибута address е

Bag,

то класът се преобразува към следната релация:

Stars (name, street, city, birthdate, count).

За всеки обект и всяка различна стойност от мултимножеството address на този обект има по един кортеж в релацията Stars. В този кортеж стойността на count е броят на срещанията на съответната стойност в мултимножеството address, съответно на обекта.
Преобразуване на атрибут от тип List се извършва подобно на атрибут от тип Set. За да представим наредбата между стойностите в списъка на този атрибут можем да добавим допълнителен атрибут position в релацията, който показва позицията на съответната стойност в списъка.

Например, ако в класа по-горе типът на атрибута address е

List,

то класът се преобразува към следната релация:

Stars (name, street, city, birthdate, position).

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

Преобразуване на атрибут от тип Array може да се извърши по следния начин: всеки елемент на масива се представя чрез отделен атрибут в релацията. Например, ако в класа по-горе типът на атрибута address е

Array,

то класът се преобразува към следната релация:

Stars (name, street1, city1, street2, city2, street3, city3, birthdate).

За всеки обект има по един кортеж в релацията Stars. В този кортеж стойностите на streetK, cityK, K = 1, 2, 3 са съответните стойности от масива address, съответен на обекта.
Преобразуване на атрибут от тип Dictionary може да се извърши по следния начин: за всяка стойност от речника на атрибута да има отделен кортеж в релацията. В схемата на релацията атрибутът се представя чрез два атрибута - един атрибут за ключа на речника и един атрибут за стойността, съответна на ключа. Например, ако в класа по-горе типът на атрибута address е

Dictionary,

то класът се преобразува към следната релация:

Stars (name, street, city, attr, birthdate).

За всеки обект и всяка стойност от речника address, съответен на този обект в релацията Stars има по един кортеж. В този кортеж стойностите на атрибутите street, city, attr се извличат от съответната стойност от речника address на обекта.
Преобразуване на ODL връзки
Както в модела ER за всяка връзка между два ODL-класа се образува по една релация, която свързва ключовете на двата класа. Естествено, двойките инверсни връзки се представят чрез една релация.
Като пример ще разгледаме следният вариант на

класовете Movie и Studio.

class Movie (extent Movies key (title, year)) {

attribute string title;

attribute integer year;

attribute integer length;

attribute enum Film { color, blackAndWhite} type;

relationship Studio ownedBy inverse Studio::owns;

} ;

class Studio (extent Studios key name) {

attribute string name;

attribute string address;

relationship Set owns inverse Movie::ownedBy;

} ;
За представяне на връзката между Movie и Studio се създава нова релация StudioOf със следната схема: StudioOf (title, year, studioName).

В случая преобразуваната връзка е много към един от Movie към Studio.

Поради тази причина релацията StudioOf може да се комбинира с релацията Movies, която съответства на класа Movie - този клас стои в множествената част на връзката. По този начин получаваме следната релация: Movies (title, year, length, type, studioName).

Както вече отбелязахме когато разглеждахме релационния модел, подобно комбиниране не е удачно да се извършва с класа в единичната част на връзка много към един или въобще за връзки много към много - това води до нарушаване на BCNF.
Липса на ключове в ODL
Тъй като ключовете не са задължителни в ODL можем да попаднем в ситуация, при която атрибутите на един клас не могат да се използват за идентифициране на обектите от този клас. Такава ситуация води до проблеми, особено ако класът участва в една или повече връзки с други класове. Решението на този проблем е добавяне на допълнителен атрибут, който да служи за ключ. Този атрибут се преобразува към отделен атрибут в релацията, съответна на класа и чрез него обектите на класа се представят в релациите, съответни на връзки, в които участва този клас. Например, да предположим, че атрибутът name не може да е ключ на класа Star. Тогава добавяме допълнителен атрибут cert#, който се свързва с всяка звезда и чрез който всяка звезда се идентифицира уникално. При това положение класът Star се преобразува към следната релация: Stars (cert#, name, street, city). Връзката много към много между класовете Star и Movie тогава се представя чрез следната релация:

StarsIn (title, year, cert#).

Обектно-релационен модел на данните
В началото на 90-те години се появиха обектно-ориентирани СУБД.

Те не успяха да се наложат и отпаднаха към средата на 90-те.

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

обектно-релационният модел. Този модел е в основата на един от

най-съвременните стандарти на SQL - SQL99.
От релации към обектни релации
В обектно-релационния модел релацията отново е фундаментална концепция. За разлика от релационния модел, в обектно-релационния модел са добавени следните пет нови характеристики:

Въвеждат се структурирани типове за атрибутите - системата за типизация в обектно-релационните СУБД е подобна на тази в ODL. Атрибутите могат да са както от атомарни типове, така и от по-сложни типове, образувани чрез наборни конструктори и конструктори за структури. Интересен ефект от това е, че типът множество (мултимножество) от структури може да се разглежда като релация. По този начин един компонент на един кортеж може да бъде цяла релация.
Въвеждат се методи, които се обвързват с релациите и могат да се прилагат към кортежите на релациите.
Въвеждат се идентификатори на кортежи - в обектно-релационните системи кортежите играят ролята на обекти. В определени ситуации е полезно кортежите да се идентифицират уникално, подобно на обектите в ODL. По принцип идентификаторите на кортежи са невидими за потребителя, но понякога той може да има достъп до тях.
Въвеждат се reference към кортежи, които се използват по различни начини в обектно-релационните системи.

Вгнездени релации
Релации, които са разширени с първата характеристика от по-горе често се наричат вгнездени релации. В модел, допускащ вгнездени релации атрибутите могат да имат неатомарен тип. Релационната схема също се разглежда като възможен тип за атрибутите. Като резултат получаваме следната индуктивна дефиниция за тип на атрибут и схема на релация.

База: всеки атрибут може да има атомарен тип.

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

Като пример ще разгледаме вгнездена релация, подобна на релацията за звездите на филми от по-горе. Тя има следната схема:

Stars (name, address (street, city), birthdate, movies (title, year, length)).

Чрез атрибута movies, който има тип релационна схема се задават филмите, в които участва звездата. Чрез атрибута address, който има тип релационна схема се задават адресите на звездата.

Един примерен екземпляр на Stars изглежда по следния начин:

name

address

birthdate

movies

Carrie Fisher

street

city

9/9/99

title

year

length

Maple

Hollywood

Star Wars

1977

124

Locust

Malibu

Empire

1980

127

Return

1983

133

Mark Hamill

street

city

8/8/88

title

year

length

Oak

Brentwood

Star Wars

1977

124

Empire

1980

127

Return

1983

133

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

В този пример наблюдаваме излишество - информацията за филмите, които попадат в повече от една релация, която е стойност на атрибута movie се дублира. Този проблем се решава с въвеждане на reference към кортежи. Всеки атрибут може да има тип reference към кортеж с дадена схема или reference към множество от кортежи с дадена схема.

Ако атрибутът A има тип reference към кортеж със схема R, то в схемата, в която участва A отбелязваме това по следния начин: A (*R).

В ODL аналог на това понятие е връзка от тип R.

Ако атрибутът A има тип reference към множество от кортежи

със схема R, то в схемата, в която участва A отбелязваме това по

следния начин: A ({ *R}).

В ODL аналог на това понятие е връзка от тип Set.
За да елиминираме излишеството в примера трябва да използваме две релации със следните схеми:

Movies (title, year, length)

Stars (name, address (street, city), birthdate, movies ({ *Movies})).

Преобразуваният екземпляр изглежда по следния начин:

По този начин елиминирахме излишеството в горната релация - за всеки филм има единствен кортеж, въпреки че към този кортеж може да има много reference.

Сравнение на обектно-ориентирания с обектно-релационния модел
Обектно-ориентираният модел, представен с ODL и

обектно-релационният модел, който разглеждаме много си приличат.

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

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

В обектно-релационния модел, обаче, връзките могат да се представят и чрез указатели към кортежи, както видяхме по-горе.
Разширения на класове и екземпляри на релации
В ODL всички обекти от даден клас съществуват в разширението на класа. В обектно-релационния модел може да има няколко релации с идентични схеми, но с различни екземпляри. В ODL това може да се постигне чрез наследяване на интерфейс, както видяхме по-горе.
Методи
По-горе не дискутирахме използването на методи като част от обектно-релационния модел. На практика в стандарта SQL99, както и при другите обектно-релационни системи позволяват аналогични на ODL възможности за дефиниране и използване на методи.
Система за типизация
Системите за типизация в ODL и в обектно-релационния модел са подобни. И двете системи поддържат атомарни типове и конструктори за създаване на нови типове. Конструкторите се различават в реализациите, но навсякъде се поддържат множества и мултимножества. Освен това, типът множество (мултимножество) от структури играе централна роля и в двата модела. В ODL това е типът на всеки клас, а в обектно-релационния модел това е типът на всяка релация.
Reference и идентификатори на обекти
В чистия обектно-ориентиран модел идентификаторите на обекти (OID) са скрити от потребителя и той няма достъп до тях.

В обектно-релационния модел reference към кортежи се задават като част от типа на атрибут и при определени условия те подлежат на манипулация. Тази възможност позволява значителна гъвкавост, но е сериозен източник на грешки.

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

по-богати конструкции - атрибути от неатомарен тип, връзки, методи.

С разширенията които добавихме в обектно-релационния модел, преобразуването на ODL-проект към обектно-релационна схема се улеснява значително. Неатомарните типове в ODL директно могат да се образуват към съответните им еквивалентни обектно-релационни типове. В някои случаи, обаче, конкретната обектно-релационна система може да не поддържа определен неатомарен тип и тогава се налага да се използва подходящо моделиране, подобно на това при преобразуване на ODL-проект към чисто релационна схема.

Връзките в обектно-релационния модел могат да се представят чрез релации, основавайки се на ключове, но за тяхното представяне могат да се използват и reference към кортежи.

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

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

Моделът на полуструктурираните данни притежава по-голяма гъвкавост от досега разгледаните модели.

В модела ER има два фундаментални типове данни - множества същности и връзки. В релационния модел има само един тип данни - релацията. Моделът ER е по-богат на концепции от релационния модел и позволява по-ефикасно моделиране на реалния свят. От друга страна, фактът че има само една структура от данни в релационния модел позволява по-ефективна реализация на заявките.

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

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

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

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

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

Като пример ще разгледаме полуструктурирана база от данни за филмите и звездите.

Коренът (root) е входна точка в базата от данни. Основните обекти (същностите), които в случая са звездите и филмите се представят чрез преките наследници на корена. Листата имат етикети, които описват данните. Три от вътрешните възли имат етикети - cf, sw, mh.

Те представят съответно звездата Carrie Fisher, филмът Star Wars и звездата Mark Hamill. Етикетите на вътрешните възли не са част от модела, но придават по-голяма яснота в примера.
Етикетите на дъгите имат две роли. Да предположим, че една дъга, която излиза от възел N и влиза във възел M има етикет L.

Ако възелът N представя обект (структура), а възелът M представя атрибут на обекта (поле на структурата), то етикетът L е името на този атрибут (поле).
Ако възлите N и M представят обекти, то етикетът L е името на връзката от N към M.

В примера по-горе да разгледаме вътрешният възел cf, който представя звездата Carrie Fisher. От него излиза дъга с етикет name, която представя атрибутът name на тази звезда. Също така, от cf излиза дъга с етикет starsIn към възела sw, който представя филмът Star Wars. Тази дъга представя връзката starsIn между звездата и филма, в който тя участва.

Интеграция на информацията чрез полуструктурирани данни
За разлика от другите модели, данните в полуструктурирания модел се самоописват, т.е. схемата на данните е прикачена към самите данни.

Във всеки възел (освен корена) влизат дъги, чиито етикети описват ролята на възела по отношение на свързаните с него възли, посредством тези дъги. Във всички други модели данните имат фиксирана схема, която е отделена от тях. При тях ролята на данните се подразбира от тази схема.

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

продукта Lotus Notes. При този продукт не е необходимо предварително да се задава схема на данните.

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

Базите данни в днешно време се използват масово. Често възниква необходимост две или повече бази от данни да бъдат достъпни като една. Например, при сливане на компании базите от данни за техния персонал трябва да се слеят. Ако тези бази от данни имат еднакви схеми, то обединяването ще е лесно. Такава ситуация, обаче, много рядко е налице. В общия случай независимо разработените бази от данни имат различни схеми, дори могат да използват различни модели на данните - една база от данни да е релационна, друга обектно-ориентирана.

Нещата са още по-сложни. В течение на времето една база от данни се използва от все повече и повече приложения и в един момент става практически невъзможно тя да бъде модифицирана. Този проблем e известен като проблем на наследените бази от данни.

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

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

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

а интерфейсът преобразува тези заявки към заявки за съответните бази от данни, съобразени с техните схеми.

XML и неговият модел на данни
XML (extensible mark-up language) е нотация за маркиране на документи чрез етикети, подобна на HTML или SGML. Документът не е нищо друго, освен символен файл. За разлика от HTML, където маркировката се използва най-вече за визуализация на данните в документа, маркировката в XML се използва за описване на смисъла на информацията в документа.

Ще разгледаме как се използва XML за представяне на графа на базата от полуструктурирани данни в линейна форма. По-конкретно, ролята на етикетите на дъгите ще се изпълнява от маркерите в XML-документа.

След това ще въведем DTD (document type definition) - това е гъвкава схема на данните, която може да се прилага върху XML-документи.
Маркери в XML
Маркерите в XML са образувани от текст, ограден в триъгълни скоби по следния начин: <текст>. Маркерите винаги се използват по двойки - на всеки отварящ маркер <текст> съответства затварящ маркер ,

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

Например, не е възможна подобна маркировка:

… … ….
XML-документите се използват в два режима:

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

Добре структурани XML-документи
Минималното изискване за един добре структуриран XML-документ е наличие на декларация в началото на документа, която показва че той е XML и наличие на коренен маркер, който обгражда цялата останала част от документа. Общата структура на добре структурираните

XML-документи е следната:

…

Първият ред индикира, че документът е XML. В него е записана версията на XML, която е използвана. Параметърът STANDALONE със стойност “yes” означава, че документът е добре структуриран, т.е. с него не е свързано DTD. Целият първи ред трябва да е ограден в специален маркер , който е различен от обикновените маркери.

Името на коренния маркер в случая е BODY, но може да се използва кое да е друго име.

Ще опишем добре структуриран XML-документ, който представя грубо полуструктурираните данни за филмите и звездите.

Carrie Fisher

123 Maple Str.

Hollywood

5 Locust Ln.

Malibu

Mark Hamill

456 Oak Rd.Brentwood

Star Wars1977

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

Например, за звездата Mark Hamill това изглежда по следния начин:

Mark Hamill

456 Oak Rd.Brentwood

Star Wars1977

Empire Strikes Back

1980

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

Валидни XML-документи
За да може XML-документите да се обработват автоматично, нормално е те да се подчиняват на някаква схема. С други думи, трябва да е указано какви маркери могат да се използват и по какви правила тези маркери могат да се вгнездяват. Описанието на схемата на

XML-документ е последователност от граматични правила, която се нарича DTD (document type definition).

Естествено, наличието на такива описания води до по-лесна обмяна на информация между компании или общности, които използват

XML-документи.

Най-общо едно DTD изглежда по следния начин:

DOCTYPE име_на_коренен_маркер [

ELEMENT име_на_елемент (компоненти)>

…

ELEMENT име_на_елемент (компоненти)>

] >
Зададеното име на коренния маркер трябва да се използва във всеки XML-документ, който се подчинява на това DTD.

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

Тези компоненти са имена на маркери, които може трябва да присъстват в порцията от XML-документа, съответна на елемента.

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

Ако след името на елемент се използва списък от компоненти (#PCDATA), това означава, че в порцията на XML-документа, съответна на този елемент няма маркери, т.е. има само текст.

Да отбележим, че имената на маркерите в XML (както в HTML) са

case-insensitive, т.е. не се прави разлика между малки и главни букви.
Ще разгледаме едно примерно DTD за звездите.

] >
В общия случай компонентите на един елемент с име E са имена на други елементи. Те трябва да присъстват между маркерите и в

XML-документа и то в указания ред. С всеки компонент може да се използва един от следните оператори, който се записва след името на компонента:

оператор * - той указва, че съответният компонент трябва да присъства нула или повече пъти в XML-документа;
оператор + - той указва, че съответният компонент трябва да присъства един или повече пъти в XML-документа;
оператор ? - той указва, че съответният компонент трябва да не присъства или да присъства един път в XML-документа.

В списъка от компоненти на един елемент може да се използва

символът |, който се появява между компоненти или списъци от компоненти, оградени в скоби. Неговата семантика е на

изключващо или - в XML-документа трябва да присъства или компонента (списъка от компоненти) отляво на | или компонента

(списъка от компоненти) отдясно на |, но не и двете едновременно.

Например, списък от компоненти (#PCDATA | (STREET, CITY)) за елемента ADDRESS означава, че в XML-документа порцията, съответна на този елемент е или текст без маркери или текст с два маркера със съответни имена.
Ще разгледаме един примерен XML-документ, който отговаря на описаното по-горе DTD.

Carrie Fisher

123 Maple Str.

Hollywood

Star Wars

1977

Empire Strikes Back

1980

Return of the Jedi

1983

Mark Hamill

456 Oak Rd.

Brentwood

Star Wars

1977

Empire Strikes Back

1980

Return of the Jedi

1983

Ако един XML-документ е валиден, т.е. свързан с DTD, това се указва по един от следните два начина:

Включваме пълното описанието на DTD в началото на

XML-документа.

Указваме име на файл, който съдържа съответното DTD. В този случай, приложението което обработва XML-документа трябва да има достъп до файловата система, в която се съхранява DTD.

И в двата случая параметърът STANDALONE в първия ред на

XML-документа има стойност “no”.

В първия случай пълното описание на DTD се осъществява непосредствено след първия ред на валидния XML-документ.

Във втория случай вторият ред на валидния XML-документ трябва да има следния вид:

DOCTYPE име_на_коренен_маркер SYSTEM “име_на_файл”>

Тук пълното описание на DTD е съдържание на съответния файл.

Този вариант е по-удобен, тъй като едно описание на DTD може да се използва с много XML-документи.
Например, описаният валиден XML-документ по-горе трябва да започва със следните два реда:

Тук star.dtd е файлът, който съдържа описанието на DTD за звездите.

Атрибути в XML
XML-документите и полуструктурираните данни са доста силно свързани. Всеки XML-документ може да се представи чрез граф на полуструктурирани данни. За целта, за всяка двойка маркери

и създаваме по един възел. Ако една двойка маркери

и е директно вгнездена в двойката маркери и

(т.е. няма двойка маркери, която огражда , и

е оградена от , ), то от възела, съответен на и прекарваме дъга с етикет S към възела, съответен на и .

Обратното не е вярно - получените графи от XML-документи са дървета, тъй като всеки връх има единствен предшественик.

Поради тази причина чрез досега описаните възможности на XML връзките не могат да се представят чрез двойки противоположни дъги.

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

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

За нашите цели разглеждаме два възможни

типове атрибути - ID и IDREF (IDREFS).

Ако един атрибут на елемент с име E има тип ID, това означава, че той ще приема уникални стойности за всяка порция от XML-документа, оградена с маркери и . В термините на полуструктурираните данни това означава, че този атрибут осигурява уникална идентификация на съответния възел.

Ако един атрибут на елемент с име E има тип IDREF (IDREFS), това означава, че той ще приема стойност (списък от стойности) на атрибути ID, асоциирани с други елементи в XML-документа. В термините на полуструктурираните данни това може да се интепретира по следния начин: от съответния възел излизат дъги към възлите, чиито ID присъстват в стойността на атрибута от тип IDREF (IDREFS) на този възел, при това името на дъгата съвпада с името на атрибута от тип IDREF (IDREFS).
Следващият пример илюстрира синтаксисът за деклариране на атрибути от тип ID и IDREF (IDREFS) за елементи в DTD, както и използването на атрибутите в XML-документ за представяне на връзките в полуструктурираните данни.

starID ID

starsIn IDREFS>

movieID ID

starOF IDREFS>

] >
Следният XML-документ отговаря на описаното DTD.

Carrie Fisher

123 Maple Str.

Hollywood

5 Locust Ln.

Malibu

Mark Hamill

456 Oak Rd.

Brentwood

Star Wars

1977

Empire Strikes Back

1980

Return of the Jedi

1983

Логически езици за заявки
Някои езици за заявки се основават на логиката повече отколкото на релационната алгебра. Те са значително по-трудни за усвояване от програмистите. Ще разгледаме логически език за заявки, наречен Datalog (database logic). Той се основава на релационния модел на данни и е близък до Prolog. Нерекурсивната версия на езика има мощта на класическата релационна алгебра. В рекурсивната версия на Datalog могат да се опишат заявки, които не могат да се опишат в SQL.
Логика за релациите
В Datalog заявките се състоят от правила, подобни на правилата в Prolog.

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

Предикати и атоми
Основна роля в Datalog играят предикатите и атомите. Релациите в Datalog се представят чрез предикати. Всеки предикат получава фиксиран брой аргументи. Атом наричаме предикат, последван от аргументите си. Атомите се описват по начина по който се описват извиквания към функции в конвенционалните езици за програмиране.

Например P (x₁, x₂, …, x_n) е атом, който се състои от предиката P с аргументи x₁, x₂, …, x_n.

Всъщност, предикатът може да се разглежда като функция, която връща булеви стойности. Ако R е име на релация с n атрибута в някакъв фиксиран ред, то ще използваме R като име на предикат, който съответства на тази релация. Атомът R (a₁, a₂, …, a_n) има стойност true, ако (a₁, a₂, …, a_n) e кортеж на релацията R и стойност false, ако

(a₁, a₂, …, a_n) не е кортеж на релацията R.

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

В Datalog могат се използват и аритметични атоми. Те представляват сравнение на два аритметични израза: например x < y, x+1  y + 4*z.

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

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

Поради тази причина аритметичните атоми се отделят от релационните.
Правила в Datalog
Oперации, подобни на операциите от релационната алгебра могат да се опишат в Datalog с помощта на правила.

Едно правило се състои от три части:

Релационен атом, който се нарича
Каталог: 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.96 Mb.

Сподели с приятели:

1 2 3 4 5 6 7 8 9 10