Глава 5. Нормализация на релациите

Глава 6. Видове операции с данните

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

Потребителските операции са действия, които показват какво трябва да се получи след обработката. Те са укрупнени и ориентирани към посочване на цялото множество от обекти и свойства, с които се работи. От семантична гледна точка операциите с данните на външно равнище биват три групи: търсене, изменения, библиотечни операции. Разбира се тези операции имат разнообразни варианти в зависимост от модела на данните и функциите в предметната област. Осъществяването на операциите става над конкретните обекти, за които съществува общ модел. Примери за характерни операции с данните на външно равнище за предметна област „речни ресурси” – фиг. 4.3. са дадени в таблица 6.1.

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

Общото наименование на операцията изменения включва операциите за създаване, добавяне, отстраняване (отпадане) и корекции. Допустими са и групови изменения на едно и също свойство. Всяка информационна съвкупност търпи изменения - отпадат екземпляри, добавят се нови екземпляри, коригират се някои стойности на свойства, добавят се или отпадат цели свойства. Отстраняванията и корекциите са свързани с търсене на определени екземпляри и съответно условие за търсене. В случаите, когато на условието за търсене отговарят повече екземпляри, имаме групови отстранявания и групови корекции. Създаването на нови релации може да се разглежда като частен случай на добавянето. За това най-общо казано измененията са три вида: добавяния, отстранявания и корекции.

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

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

Обединение (Union)

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

А В Р

а	в	с		a	в	с		а	в	с
а1	в2	с3		а1	в2	с3		а1	в2	с3
а2	в1	с1		а4	в3	с1		а2	в1	с1
а3	в1	с1						а3	в1	с1
								а4	в3	с1

Разлика (Difference)

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

А В Р

а	в	с		a	в	с		А	в	С
а1	в2	с3		а1	в2	с3		а2	в1	с1
а2	в1	с1		а4	в3	с1		а3	в1	с1
а3	в1	с1

Проекция (Projection)

Унарната специална релационна операция проекция отделя свойства т.е. колони от релацията и я прави по-малка. При отстраняването на свойства може да се получи повторение на екземпляри, които се отстраняват. В следващия пример изходната релация е А. От нея се отделят свойствата а и с и се получава релацията Р1. След това се отстраняват повтарящите се редове и се получава като краен резултат проекцията Р2.

А Р1 Р2

А	в	с		а	с		а	С
а1	в2	с3		а1	с3		а1	С3
а1	в3	с3		а1	с3		а2	С1
а2	в1	с1		а2	с1		а3	С1
а3	в1	с1		а3	с1

Селекция (Selection)

Операцията селекция отделя обекти (редове) от релацията, които отговарят на зададено условие. Тя е унарна операция и създава по-малка от началната релация. Нека началната релация е горепосочената релация А. Искаме от нея да се селектират обекти със стойности на свойството а, равни на а1. След селектирането се получава релацията Р2.

Операцията съединение е бинарна. Тя съединява две релации по общо свойство. При това общото свойство може да изпълнява дадено условие. Резултатът е по-сложна релация. Съединението е най-сложната и времеемка релационна операция. Затова тя трябва да се изпълнява след всички възможни опростявания с другите релационни операции. За целта преди съединението се изпълняват селекциите и проекциите, ако са необходими. Нека началните релации са А и В. Общото свойство да е а, а условието за съединение да е равенство на стойностите на свойството а от релациите А и В. Такова съединение се нарича естествено съединение. Очевидно двете релации трябва да са подредени по един и същ начин по отношение на общото свойство. Резулт атът от съединението на двете релации е новата релация Р3.

А В

А	в	с		а	е
а1	в2	с3		а1	е1
а1	в3	с3		а2	е2
а2	в1	с1		а3	е1

Р3

a	в	с	е
а1	в2	с3	е1
а1	в3	с3	е1
а2	в1	с1	е2
а3	в1	с1	е1

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

Деление (Division)

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

А В Р

А	в	с		a		а	в	с
а1	в2	с3		а2		а2	в1	с1
а2	в1	с1		а3		а3	в1	с1
а3	в1	с1

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

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

П

ример

Търсим запис за изделие с главен ключ ProduktNo 501001. Търсенето протича в следната последователност:

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

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

Най-използваният метод за бързо намитане на даден запис в настоящия момент е индексирането. При него освен основният файл се създава и използва допълнителен, индексен файл. Индексният файл съдържа сортирани главните ключове, придружени от адресите, на които се намират записите им в основния файл. Обикновено индексният файл е организиран за бързо търсене по главен ключ чрез метода на двоичното или блочното търсене. След като е открит адресът на търсения запис в индексния файл се отива по него в съответния запис от основния файл. Ускоряванетo тук е за сметка на по-бързото двоично търсене в индексния файл в сравнение с двоично търсене в основния файл. Записите в индексния файл са къси и той целият може да се прегледа в бързата оперативна памет. Записите в основния файл са дълги, той не се събира в оперативната памет и двоичното търсене в него е по-дълго.