Релационна цялостност на данните: Нулеви стойности

6.Релационни оператори: Релационна алгебра

6.1.Въведение

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

Всеки оператор на релационната алгебра има една или две релации като входни данни и връща като резултат една нова релация. Codd дефинира 8 операции, разделени по 4 в две групи:

• 
  множество на традиционните (класическите) операции - обединение (union), сечение (intersection), разлика (difference) и Декартово произведение (Cartesian product);
  
• 
  специални релационни операции - ограничение (restrict), проекция (project), естествено съединение (join) и частно (divide).
  

Освен класическата релационна алгебра в литературата са описани различни нейни варианти. Ние ще разгледаме една такава алгебра, която не се различава много от оригиналната и същевременно може да служи за дискутиране на различни релационни идеи. 8 оператора са показани на фигура 9-1.

• 
  RESTRICT (SELECT) - връща релация, която съдържа всички записи, отговарящи на специфицираните условия;
  

• 
  PROJECT - връща релация, която съдържа всички записи със специфицирани атрибути от дадена релация;
  
• 
  UNION - създава релация, която се състои от всички записи, които се появяват във всяка една или и в двете релации;
  
• 
  INTERSECT - създава нова релация, състояща се от всички записи, които се появяват в двете релации едновременно;
  
• 
  DIFFERENCE - създава релация, състояща се от всички записи, които се появяват в първата, но не и във втората релация;
  
• 
  PRODUCT - създава нова релация от две дадени релации, която се състои от всички възможни свързани двойки от записи от двете релации;
  
• 
  JOIN - създава нова релация от двете дадени релации, която съдържа всички възможни свързани двойки от записи, (по един от всяка релация) така че всяка двойка да удовлетворява някакво условие;
  
• 
  DEVIDE - взема две релации (една двоична и една единична в примера) и създава нова релация, която съдържа всички стойности на единия атрибут от двоичната релация, които съответстват (равни в другия атрибут) на всички стойности от единичната релация.
  

• 
  проекция от обединение;
  
• 
  сливане на два избора;
  
• 
  разлика от сливане и сечение и т.н.
  

6.2.Затвореност

Така е възможно да създаваме вградени изрази. Т.е. операндите могат да бъдат представени посредством изрази.

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

Както вече казахме, една релация има две части: заглавна част и тяло. Заглавната част е добре дефинирана и позната на системата. Но за релации, които се извеждат? Напр. LECTURER join FACULTY описва сливането на факултетите и преподавателите върху FACULTY_ID - атрибута. Каква е заглавната част на резултата? Затвореността изисква той отново да е заглавна част и системата трябва да знае каква е тя. Т.е. ако системата поддържа затвореността, всеки релационен оператор трябва да бъде дефиниран в системата. Така системата трябва да има информация за такова множество от подходящи имена на атрибути, за да може да ни разреши да реферираме тези имена в последващи операции. Например, не можем да запишем израза (LECTURER join FACULTY) where EMPLOYEE_NUMBER > 30, ако не знаем, че в (LECTURER join FACULTY) има атрибут с име EMPLOYEE_NUMBER.

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

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

6.3.Синтаксис на релационната алгебра

В този раздел ще въведем конкретен синтаксис за операциите на релационната алгебра, за да създадем основата на дискусията, която следва след това.
expression ::= monadic-expression | dyadic-expression
monadic-expression ::= renaming | restriction | projection
renaming ::= term RENAME attribute AS attribute
term ::= relation | (expression)
restriction ::= term WHERE condition
projection ::= term | term [ attr-spec-commalist ]
dyadic-expression ::= projection dyadic-operation expression
dyadic-operation ::= UNION | INTERSECT | MINUS | TIMES | JOIN | DIVIDEBY
Някои бележки по граматиката:

• 
  граматиката използва следните подходящи съкращения: ако "xyz" e синтактична категория, тогава "xyz-commalist" е синтактична категория, съдържаща списък от един или повече "xyz", разделени със запетаи;
  
• 
  категориите relation и attribute са дефинирани като идентификатори (най малката категория в тази граматика);
  
• 
  категорията condition представлява логическа комбинация от сравнения ("comparisons"), съставени в съответствие с нормалните правила на Булевите изрази. Сравненията представляват елементарни сравнения между две "scalar-values" и една "scalar-value" се състои от константа или атрибутна стойност;
  
• 
  съзнателно не разрешаваме една "attr-spec" в проекция да бъде операторен израз като ATTR1 + ATTR2, за по-голяма простота. Аналогично ние не разрешаваме такива изрази да се появяват като сравняемо в сравненията. На практика, обаче, такива ограничения са нежелателни;
  
• 
  граматиката включва операции за дефиниране на релации и псевдоними. Ние включваме псевдоними, за да избегнем проблеми при именуване при оператора за Декартово произведение.
  

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

Забележка: въпреки факта, че ние разглеждаме атрибутите като подредени от ляво на дясно в една релация, ние все пак разчитаме на имената на атрибутите за целите на референциите и изискваме да няма релация, която да има два атрибута с еднакви имена. Ние предполагаме, че това ограничение автоматично се налага за именуваните (т.е. дефинираните) релации. Правилата за генериране имена на атрибутите за дериватните (derived) релации (т.е. релации, които се представят по-скоро чрез изрази, отколкото чрез имена) в съответствие с ограничението на уникалното именуване се разглежда по-нататък. Тук ние ще се задоволим с кратко разглеждане на именуваните релации.

• 
  нека R е една именувана релация и нека А е (неквалифицирано) име на един атрибут в R - т.е. един атрибут в списъка "attr name commalist", появяващ се в дефиницията на R. Атрибутът А има квалифицирано име R.A.
  
• 
  ако R е именувана релация и S е един псевдоним на R, тогава:
  
  • 
    когато дадена релация се реферира чрез името R, атрибутът А на тази релация може да се референцира чрез R.A;
    
  • 
    когато дадената релация се референцира посредством името S, атрибутът А от тази релация може да се референцира като S.A.
    

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

6.4.Множество на традиционните операции

Множеството на традиционните оператори включва:

• 
  обединение;
  
• 
  сечение;
  
• 
  разлика;
  
• 
  произведение.
  

Всяка операция има два операнда.

6.4.1.Свойството съвместимост на типове (type-compatible)

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

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

Например, обединението на FACULTY и LECTURER - множеството на записите за факултетите и преподавателите.

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

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

Съвместимост на типове - двете релации да имат идентични заглавни части, т.е.:

• 
  имат еднакви множества от имена на атрибутите;
  
• 
  кореспондиращите атрибути са дефинирани върху еднакви домени.
  

Съвместимост по типове се изисква за операторите:

• 
  обединение;
  
• 
  сечение;
  
• 
  разлика.
  

6.4.2.Обединение

Обединението на две релации А и В (A UNION B) е релация със заглавна част като на A и B и тяло множеството на всички записи, принадлежащи на А, В или и двете.

Пример: нека А е множеството от записите за факултети от ПУ и нека В е множеството от записи за факултети от СУ. Тогава A UNION B е множеството на записите за факултети от ПУ и/или СУ, като дубликатите се елиминират.

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

6.4.3.Сечение

Сечението на две релации А и В, (A INTERSECT B) е релация със заглавна част като A и B и тяло множеството на всички записи, които принадлежат към А и В.

Пример: нека А и В са както по-горе. Тогава А INTERSECT B е множеството на записите на преподавателите, които са едновременно в един и същ факултет в двата ВУЗ-а.

6.4.4.Разлика

Разликата на две релации А и В (A MINUS B) е релация със заглавна част като A и B и тяло множеството от всички записи, които принадлежат към А и не принадлежат към В.

Пример: A MINUS B е множеството от записи на преподаватели от факултети в ПУ, които не са такива в същите факултети в СУ.

6.4.5.Произведение

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

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

{ A₁ : a₁, A₂ : a₂, ... ,A_m : a_m }

и

{B₁ : b₁, B₂ : b₂, ... , B_n : b_n}

обединението е
{A₁ : a₁, A₂ : a₂, ... , A_m : a_m, B₁ : b₁, B₂ : b₂, ... , B_n : b_n}
Другият проблем е, че ние искаме резултатната релация да има точно определена заглавна част. Тя е обединението на двете заглавни части на входните релации.

Проблем – ако двете заглавни части имат някои общи имена на атрибутите. В този случай трябва да използваме оператора RENAME за преименуване на тези атрибути.

Дефинираме Декартовото произведение на две релации A и B (A TIMES B), където A и B имат общи имена на атрибутите, т.е. като релация с:

• 
  заглавна част - обединението на заглавните части на A и B ;
  
• 
  тяло - множеството на всички записи t, където t е обединението на всеки запис a от A с всеки запис b от B.
  

Кардиналност на резултата - произведението на кардиналността на A и B.

Степен на резултата - сумата от степените на A и B.

6.4.6.Асоциативност

Лесно е да се докаже, че UNION е асоциативна - т.е. ако A, B и C са произволни "проекции", тогава изразите

( A UNION B ) UNION C

и

A UNION (B UNION C)

са еквивалентни.

INTERSECT, TIMES (но не MINUS) са асоциативни.

UNION, INTERSECT, TIMES са също така комутативни, т.е.

A UNION B = B UNION A

6.5.Специални релационни операции

Това са операторите:

• 
  ограничение (избор);
  
• 
  проекция;
  
• 
  естествено сливане;
  
• 
  частно..
  

6.5.1.Ограничение (избор)

Нека  (тита) представлява някой валиден оператор за сравняване (=, !=, <, >, ...). Тита-избор на релацията R върху атрибутите X и Y
R WHERE R.X  R.Y
е релация със същата заглавна част като R и с тяло множеството на всички записи t на R, така че сравнението t.X  t.Y e вярно за всички t (атрибутите X и Y са дефинирани върху един и същ домейн и операторът  трябва да има смисъл за този домейн). На мястото на всеки един от атрибутите може да се специфицира константна стойност.
R WHERE R.X  constant
По този начин тита-избор операторът произвежда "хоризонтално" подмножество на дадена релация - т.е. това подмножество от записи на дадена релация, за което е удовлетворено специфицираното сравнение.

Забележка: тита-избор често се съкращава само като избор.

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

• 
  R WHERE c1 AND c2 е дефинирана като еквивалентна на (R WHERE c1) INTERSECT (R WHERE c2);
  
• 
  R WHERE c1 OR c2 еквивалентна на (R WHERE c1) UNION (R WHERE c2);
  
• 
  R WHERE NOT c е еквивалентна на R MINUS (R WHERE c).
  

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

6.5.2.Проекция

Проекцията на релацията R върху атрибутите X,Y,...,Z
R [X,Y,...,Z]
е релация със заглавна част {X,Y, ... , Z} и тяло множеството от всички записи {X:x, Y:y, ... , Z:z }, така че един запис t се появява в R с X-стойност x, Y-стойност y,...., Z-стойност z. По този начин проекцията създава едно "вертикално" подмножество на дадената релация - т.е. това подмножество се получава чрез избор на специфични атрибути в специфициран ред (отдясно наляво) и след това се елиминират излишните дубликати ако е необходимо. Проекцията ни доставя възможен начин за пренареждане на атрибутите в една релация.



Забележки:

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

6.5.3.Естествено сливане

Съществуват различни варианти на оператора сливане. Най-често използваният е естествено сливане.

Нека са дадени релациите A и B със заглавни части

{ X₁ , ... , X_m , Y₁ , ... , Y_n } и { Y₁ , ... , Y_n , Z₁ , ... , Z_p }

т.е. атрибутите { Y₁ , ... , Y_n } са общи за двете релации.

Допускаме, че общите атрибути са дефинирани върху общи домени.

По-нататък ще разглеждаме:

• 
  { X₁ , ... , X_m } - като X;
  

• 
  { Y₁ , ... , Y_n } - като Y;
  
• 
  { Z₁ , ... , Z_p } - като Z
  

т.е. три съставни атрибута.

Тогава естественото сливане (A JOIN B) е релация със:

• 
  заглавна част - { X, Y, Z };
  

• 
  тяло - множеството на всички записи { X:x, Y:y, Z:z }, така че един запис се появява в A с X-стойностите и с Y-стойностите, а B - с Y-стойностите и Z- стойностите.
  

JOIN - операторът е:

• 
  асоциативен - (A JOIN B) JOIN C = A JOIN (B JOIN C) или A JOIN B JOIN C;
  
• 
  комутативен - A JOIN B = B JOIN A
  

6.5.4. сливане

Нека релациите A и B нямат общи атрибути и нека  е дефиниран като преди. Тогава  сливане (-join) на релацията A върху атрибута X с релацията B върху атрибута Y е резултатът от изпълнението на израза
( A TIMES B ) WHERE X  Y
т.е. резултатната релация е с:

• 
  заглавна част - като на Декартовото произведение на A и B;
  
• 
  тяло - множеството на всички записи, принадлежащи на Декартовото произведение, за които X  Y е вярно.
  

6.5.5.Частно

Нека релациите A и B имат заглавни части { X₁ , ... , X_m , Y₁ , ... , Y_n } и { Y₁ , ... , Y_n }, т.е. атрибутите { Y₁ , ... , Y_n } са общи за двете релации. Допускаме, че кореспондиращите атрибути са дефинирани върху общи домени.

Нека разглеждаме { X₁ , ... , X_m } като X и { Y₁ , ... , Y_n } като Y - съставни атрибути.

A DIVIDEBY B е релация с:

• 
  заглавна част - { X };
  
• 
  тяло - множеството на всички записи { X:x }, така че един запис { X:x, Y:y } се появява в A за всички записи { Y:y }, появяващи се в B.
  

Операторът за деление дели една релация А от степен m+n на друга релация В от степен n и създава нова релация от степен m. (m+i)-тият атрибут на А и i тият атрибут на В (i-1,2,...,n) трябва да бъдат дефинирани върху същия домен.

6.6.За какво е необходима алгебрата?

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

Може би е ясно, че осемте операции не образуват едно минимално множество. В действителност само 5 от 8 операции са примитиви (restriction, projection, produkt, union, difference). Останалите 3 могат да бъдат дефинирани чрез първите 5. Например, естественото сливане е проекция на рестрикцията на едно произведение. На практика обаче, тези 3 операции са толкова полезни (специално сливането), че си заслужава те да се поддържат директно като примитиви.

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

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

Най-общо изразите служат като абстрактно и на високо ниво представяне целите на потребителите. От това следва, че те могат да се обработват с помощта на различни трансформационни правила (transformation rules). Например, изразът (LECTURER JOIN FACULTY) WHERE FACULTY_NAME = 'ФМИ' може да се трансформира в логически еквивалентен, но по-ефективен израз: (LECTURER JOIN (FACULTY WHERE FACULTY_NAME = 'ФМИ')).

По този начин алгебрата става удобна основа за оптимиране.

6.7.Разширение и сумиране

Много изследователи предлагат нови алгебрични оператори, като допълнение на тези на д-р Codd. Ще разгледаме два такива по-детайлно - EXTEND, SUMMARIZE.

6.7.1.EXTEND

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

Пример: да включим атрибут, който да съдържа теглото на детайлите в грамове (от килограми в грамове).

EXTEND P ADD (WEIGHT * 1000) AS GMWT
(EXTEND P ADD (WEIGHT * 1000) AS GMWT ) WHERE GMWT > 10000
В синтаксиса можем да включим нов вид monadic expression
EXTEND term ADD scalar-expression AS attribute
Резултатът е релация със:

• 
  заглавна част - заглавната част на оригиналната релация, разширена с новия атрибут;
  
• 
  тяло - всички записи t, така че t е записът от оригиналната релация, разширен със стойност на новия атрибут, която е изчислена от scalar-expression.
  

6.7.2.SUMMARIZE

Този оператор извършва вертикално изчисление.
Пример: SUMMARIZE R BY (ID) ADD SUM(QUANTITY) AS TOTQTY


SUMMARIZE term BY (attribute-commalist)

ADD aggregate-expression AS attribute

Пример: SUMMARIZE A BY (A1 , ... , An) ADD exp AS Z
A_i - отделни атрибути на A.
Резултатът е релация със:

• 
  заглавна част - {A₁ , ... , A_n , Z };
  
• 
  тяло - всички записи t, така че t е един запис на проекция на A върху A₁, ... , A_n , разширен с една стойност за новия атрибут Z. Новата Z-стойност е получена чрез изчисляване на exp за всички записи от A, които имат имат едни и същи стойности за A₁ , ... , A_n;
  

Степен на резултатната релация - степен на проекцията на оригиналната релация +1.

Кардиналност на резултатната релация - кардиналност на проекцията на оригиналната релация.

6.8.UPDATE оператори

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

Синтаксис на този оператор:

target := source;
target и source са релационни изрази (type-compatible).

source се изчислява и резултатът се присвоява на target, като заменя предишната му стойност.

Следователно, този оператор променя БД.

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

• 
  добавяне на запис - R := R UNION {5, “Детайл 4”, 200};
  
• 
  изтриване на запис - R := R MINUS {1, “Детайл 1”, 300}.
  

В практиката една релационна система може да включва явни операции за тези действия:

• 
  INSERT - INSERT source INTO target;
  

рел. изрази

source се изчислява и всички записи на резултата се добавят към target;

• 
  UPDATE - UPDATE target assigment-commalist;
  

target - релационен израз;

assigment във формата attribute := scalar-expression;

• 
  DELETE - DELETE target, target - рел. Израз;
  

6.9.Релационни сравнения

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

Нов вид условие - релационно сравнение.

expression  expression

expression - рел. изрази (type-compatible)

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

• 
  = - идентично множество;
  
• 
  =,< - подмножество на, истинско подмножество;
  
• 
  =, > - супермножество, истинско супермножество.
  

Каталог: sites -> default -> files
files -> Образец №3 справка-декларация
files -> Р е п у б л и к а б ъ л г а р и я
files -> Отчет за разкопките на праисторическото селище в района на вуз до Стара Загора. Аор през 1981 г. ХХVІІ нац конф по археология в Михайловград, 1982
files -> Медии и преход възникване и развитие на централните всекидневници в българия след 1989 година
files -> Окръжен съд – смолян помагало на съдебния заседател
files -> Семинар на тема „Техники за управление на делата" 18 19 юни 2010 г. Хисар, Хотел „Аугуста спа" Приложение
files -> Чинция Бруно Елица Ненчева Директор Изпълнителен директор иче софия бкдмп приложения: програма
files -> 1. По пътя към паметник „1300 години България

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

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