Лекция 5. Базисни средства за манипулиране с релационни данни

5.1.3. Особености на теоретико-множествените операции на релационната алгебра

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

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

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

Ще отбележим, че включването в състава на операциите на релационната алгебра на трите операции за обединение, сечение и вземане на разлика е очевидно излишно, тъй като е известно, че всяка от тези операции се изразява чрез другите. Въпреки това, Код е решил да включи всичките три операции, изхождайки от интуитивните потребности на потенциалния потребител на система от релационни БД, който е далече от математиката.

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

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

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

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

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

Ще отбележим още, че всичките четири операции са асоциативни. Т. е., ако обозначим с OP коя да е от четирите операции, то (A OP B) OP C = A (B OP C), и следователно, без въвеждане на двусмислица може да се напише A OP B OP C (A, B и C са отношения, обладаващи свойствата, необходими за коректното изпълнение на съответната операция). Всички операции, освен вземането на разлика, са комутативни, т.е. A OP B = B OP A.

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

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

Нека UNION обозначава операцията за обединение, INTERSECT – операцията за пресичане, а MINUS – операцията за вземане на разлика. За обозначаване на операция ограничение ще използваме конструкцията A WHERE comp, където A е ограничиваното отношение, а comp - просто условие за сравнение. Нека comp1 и comp2 са две прости условия за ограничение. Тогава по определение:

• 
  A WHERE comp1 AND comp2 обозначава същото, което и (A WHERE comp1) INTERSECT (A WHERE comp2)
  
• 
  A WHERE comp1 OR comp2 обозначава същото, което и (A WHERE comp1) UNION (A WHERE comp2)
  
• 
  A WHERE NOT comp1 обозначава същото, което и A MINUS (A WHERE comp1)
  

На интуитивно ниво операцията ограничение е по-добре да се представя като някаква "хоризонтална" изрезка от отношението-операнд.

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

Резултатът от проекцията на отношението A по списък атрибути a₁, a₂, ..., a_n е отношение, със заглавие, определено от множеството атрибути a₁, a₂, ..., a_n, и с тяло, състоящо се от кортежи от вида <a₁:v₁, a₂:v₂, ..., a_n:v_n> такива, че в отношението A има кортеж, атрибутът a₁ на който има стойност v₁, атрибутът a₂ има стойност v₂, ..., атрибутът a_n има значение v_n. Така, при изпълнение на операция проекция се формира "вертикална" изрезка на отношението-операнд с естествено унищожение на потенциално възникващи кортежи-дубликати.

Операция съединение на отношения

Общата операция за съединение (наричана също съединение по условие) изисква наличие на два операнда - съединяваните отношения и трети операнд - просто условие. Нека да се съединяват отношенията A и B. Както при операция ограничение, условието за съединение comp има вида или (a comp-op b), или (a comp-op const), където a и b са имена на атрибути на отношенията A и B, const е литерално зададена константа, а comp-op - допустима в дадения контекст операция за сравнение.

Тогава по определение резултатът от операция за сравнение е отношение, получено чрез изпълнение на операция за ограничение по условие comp на прякото произведение на отношенията A и B.

Ако внимателно обмислим това определение, то става ясно, че в общия случай прилагането на условие за съединение съществено ще намали мощността на резултата от промеждутъчното пряко произведение на отношенията-операнди само в случая, когато условието за съединение има вида (a comp-op b), където a и b са имена на атрибути от различни отношения-операнди. Затова на практика обикновено се смятат за реални операции съединение именно тези операции, които се основават на условие за съединение от показания вид.

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

Има важен частен случай на съединение - еквисъединение и просто, но важно разширение на операция еквисъединение - естествено съединение. Операция за съединение се нарича операция еквисъединение, ако условието за съединение има вида (a = b), където a и b са атрибути на различни операнди на съединението. Този случай е важен, защото (a) той често се среща на практика, и (b) за него съществуват ефективни алгоритми за реализация.

Операцията естествено съединение се прилага към двойката отношения A и B, имащи (възможно е и съставен) общ атрибут (т.е. атрибут с едно и също имене и определен в един и същи домейн). Нека ab обозначава обединението на заглавията на отношенията A и B. Тогава естественото съединение на A и B – това е проектирания върху ab резултат от еквисъединението на A и B по A/c и BBC. Ако си спомним определението за външен ключ на отношения от края на предишната глава, то става ясно, че основният смисъл на операцията естествено съединение е възможността за възстановяване на сложна същност, декомпозирана поради изискванията на първа нормална форма. Операцията естествено съединение не се включва пряко в набора операции на релационната алгебра, но тя имеа много важно практическо значение.

Операция деление на отношения

Тази операция е най-малко очевидна от всички операции на релационната алгебра и затова се нуждае от по-подробно обяснение. Нека са дадени две отношения - A със заглавие {a₁, a₂, ..., a_n, b₁, b₂, ..., b_m} и B със заглавие {b₁, b₂, ..., b_m}. Ще смятаме, че атрибутът b_i на отношението A и атрибутът b_i на отношението B не само имат едно и също име, но са и определени върху един и същи домейн. Ще наречем множеството атрибути {a_j} съставен атрибут a, а множеството атрибути {b_j} - съставен атрибут b. Сега вече можем да говорим за релационно деление на бинарното отношение A(a,b) на унарното отношение B(b).

Резултатът от делението на A на B е унарното отношение C(a), състоящо се от кортежите v такива, че в отношението A има кортежи <v, w> такива, че множеството значения {w} включва множеството стойности на атрибута b в отношението B.

Да предположим, че в базата от данни на сътрудниците се поддържат две отношения: СЪТРУДНИЦИ (ИМЕ, ОТД_НОМЕР) и ИМЕНА (ИМЕ), при това унарното отношение ИМЕНА съдържа всички фамилии, които имат сътрудниците на организацията. Тогава след изпълнение на операция релационно деление на отношение СЪТРУДНИЦИ на отношението ИМЕНА ще се получи унарно отношение, съдържащо номерата на отделите, сътрудниците на които имат всички възможни в тази организация имена.

5.2. Релационно изчисление

Да предположим, че работим с база от данни, притежаваща схемата СЪТРУДНИЦИ (СЪТР_НОМ, СЪТР_ИМЕ, СЪТР_ЗАПЛ, ОТД_НОМ) и ОТДЕЛИ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), и искаме да научим имената и номерата на сътрудниците, които са началници на отдели с брой сътрудници по-голям от 50.

Ако за формулировката на такава заявка се използва релационната алгебра, то ще получим алгебричен израз, който ще се прочете, например, така:

• 
  изпълни съединение на отношенията СЪТРУДНИЦИ и ОТДЕЛИ по условието СЪТР_НОМ = ОТД_НАЧ;
  
• 
  ограничи полученото отношение по условието ОТД_КОЛ > 50;
  
• 
  проектирай резултата от предишната операция върху атрибутите СЪТР_ИМЕ, СЪТР_НОМ.
  

Сформулирахме точно последователността от стъпките по изпълнението на заявката, всяка от които съответствува на една релационна операция. Ако сформулираме същата заявка чрез прилагането на релационното изчисление, то ще получим формула, която може да се прочете, например, по следния начин: Покажи СЪТР_ИМЕ и СЪТР_НОМ за сътрудниците, за които съществува отдел с такова значение на ОТД_НАЧ и стойността на ОТД_КОЛ е по-голяма от 50.

Във втората формулировка само показахме характеристиките на резултиращото отношение, но нищо не казахме за начина на формирането му. В случая системата трябва сама да реши, какви операции и в какъв ред трябва да се изпълнят над отношенията СЪТРУДНИЦИ и ОТДЕЛИ. Обикновено се казва, че алгебричната формулировка е процедурна, т.е. задаваща правилата за изпълнение на заявката, а логическата е описателна (или декларативна), тъй като тя само описва свойствата желания резултат. Както беше вече посочено, тези два механизма са еквивалентни и съществуват не много сложни правила за преобразуване на един формализъм в друг.

5.2.1. Кортежни променливи и правилно построени формули

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

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

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

За определяне на кортежна променлива се използва операторът RANGE. Например, за да се определи променливата СЪТРУДНИК, дефиционната област на която е отношението СЪТРУДНИЦИ, трябва да се използва конструкцията

RANGE СЪТРУДНИК IS СЪТРУДНИЦИ

От това определение следва, че във всеки момент от време променливата СЪТРУДНИК представлява някакъв кортеж на отношението СЪТРУДНИЦИ. При използването на кортежните променливи във формулите може да се указва към стойността на атрибута на прoменливата (това е аналогично, както например, при програмиране на език С може да препращаме към значение на поле на структурна променлива). Например, за да сочим към значението на атрибута СЪТР_ИМЕ на променливата СЪТРУДНИК, трябва да се използва конструкцията СЪТРУДНИК.СЪТР_ИМЕ.

Правилно построените формули (WFF - Well-Formed Formula) служат за изразяване на условия, налагани върху кортежни променливи. В основата на WFF са простите сравнения (comparison), представляващи операции за сравнение на скаларни значения (значенията на атрибутите на променливи или литерално зададени константи). Например, конструкцията "СЪТРУДНИК.СЪТР_НОМ = 140" е просто сравнение. По определение, простото сравнение е WFF, а WFF, обградена с кръгли скоби, е просто сравнение.

По-сложните варианти на WFF се строят с помощта на логическите връзки NOT, AND, OR и IF ... THEN. Така, ако form е WFF, а comp - просто сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form са WFF.

Накрая, допуска се построяването на WFF с помощта на квантори. Ако form е WFF, в която участвува променливата var, то конструкцията EXISTS var (form) и FORALL var (form) са WFF.

Променливите, входящи в WFF, могат да бъдат свободни или свързани. Всички променливи, влизащи в WFF, при построяването на която не са използвани квантори, са свободни. Фактически, това означава, че ако за някакъв набор значения на свободни кортежни променливи при изчисляване на WFF е получена стойност true, то тези значения на кортежните прoменливи може да участват в резултиращото отношение. Ако имeто на променливата е използвано веднага след квантора при построяването на WFF от вида EXISTS var (form) или FORALL var (form), то в тази WFF и във всички WFF, построени с нейното участие, var е свързана променлива. Това означава, че такава променлива не се вижда извън границите на минималната WFF, свързала тази променлива. При изчисляването на значението на такава WFF се използва не една стойност на свързаната променлива, а цялата нейна дефиниционна област.

Нека СЪТР1 и СЪТР2 са две кортежни променливи, определени върху отношението СЪТРУДНИЦИ. Тогава, WFF EXISTS СЪТР2 (СЪТР1.СЪТР_ЗАПЛ > СЪТР2.СЪТР_ЗАПЛ) за текущия кортеж на променливата СЪТР1 приема значението true тогава и само тогава, ако в цялото отношение СЪТРУДНИЦИ се намери кортеж (свързан с променливата СЪТР2) такъв, че значението на неговия атрибут СЪТР_ЗАПЛ удовлетворява вътрешното условие за сравнение. WFF FORALL СЪТР2 (СЪТР1.СЪТР_ЗАПЛ > СЪТР2.СЪТР_ЗАПЛ) за текущия кортеж на пременливата СЪТР1 приема стойност true тогава и само тогава, ако за всички кортежи на отношението СЪТРУДНИЦИ (свързани с променливата СЪТР2) значенията на атрибута СЪТР_ЗАПЛ удовлетворяват условието за сравнение.

В същност, по-правилно е да се говори не за свободни и свързани променливи, а за свободни и свързани вхождения на променливи. Лесно се вижда, че ако променливата var представлява свързана в WFF form, то във всички WFF, включващи дадената, може да се използва името на променливата var, която може да бъде свободна или свързана, но при всички случаи няма никакво отношение към включването на променливата var в WFF form. Например:

EXISTS СЪТР2 (СЪТР1.СЪТР_ОТД_НОМ = СЪТР2.СЪТР_ОТД_НОМ) AND
FORALL СЪТР2 (СЪТР1.СЪТР_ЗАПЛ > СЪТР2.СЪТР_ЗАПЛ)

Тук има две свързани вхождения на променливата СЪТР2 със съвсем различен смисъл.

5.2.2. Целеви списъци и изрази за релационно изчисление

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

Целеви списък се строи от целеви елементи, всеки от които може да има следния вид:

• 
  var.attr, където var е име на свободна променлива на съответната WFF, а attr е името на атрибут на отношението, върху което е определена променливата var;
  
• 
  var, което е еквивалентно на наличието на подсписъка var.attr1, var.attr2, ..., var.attrn, където attr1, attr2, ..., attrn включва имената на всички атрибути на определящото отношение;
  
• 
  new_name = var.attr; new_name - новото име на съответния атрибут на резултиращото отношение.
  

Последният вариант е необходим, когато в WFF се използват няколко свободни променливи с еднаква дефиниционна област.

Израз на релационното изчисление на кортежи се нарича конструкцията от вида target_list WHERE wff. Стойността на израза представлява отношение, тялото на което се определя от WFF, а наборът атрибути и техните имена – от целевия списък.

5.2.3. Релационно изчисление на домейни

В изчислението на домейни дефиниционната област на променливите представлява не отношения, а домейни. Применително към базата от данни СЪТРУДНИЦИ-ОТДЕЛИ може да се говори, например, за домейновите променливи ИМЕ (значения са допустимите имена) или НОСЪТР (значения са допустимите номера на сътрудници).

Основната формална разлика на изчислението на домейни от изчислението на кортежи е наличието на допълнителен набор предикати, позволяващи да се изразяват така наречените условия за членство. Ако R е n-арно отношение с атрибути a₁, a₂, ..., a_n, то условието за членство има вида

R (ai1:vi1, ai2:vi2, ..., aim:vim) (m <= n),

където v_ij е или литерално задавана константа, или име на кортежна променлива. Условието за членство приема стойност true тогава и само тогава, когато в отношението R съществува кортеж, съдържащ указаните значения на указаните атрибути. Ако v_ij е константа, то върху атрибута a_ij се задава твърдо условие, независещо от текущите стойности на домейновите променливите; ако v_ij е име на домейнова променлива, то условието за членство може да приема различни значения при различните значения на тази променлива.

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

Пример. Ще формулираме чрез изчисление на домейни заявката "Изведи номерата и имената на сътрудниците, които не получават минималната работна заплата" (за простота ще считаме, че сме определили домейновите променливи, имената на които съвпадат с имената на атрибутите на отношението СЪТРУДНИЦИ, а когато са необходими няколко домейнови променливи, определени върху един домейн, ще добавяме в края на името цифри):

СЪТР_НОМ, СЪТР_ИМЕ WHERE EXISTS СЪТР_ЗАПЛ1
(СЪТРУДНИЦИ (СЪТР_ЗАПЛ1) AND
СЪТРУДНИЦИ (СЪТР_НОМ, СЪТР_ИМЕ, СЪТР_ЗАПЛ) AND
СЪТР_ЗАПЛ > СЪТР_ЗАПЛ1)

Релационното изчисление на домейни е основа на повечето езици за заявки, базирани на използването на формуляри. В частност, върху това изчисление се основавал известния език Query-by-Example, който е първия (и най-интересен) език в семейството езици, основани на таблични формуляри.

Каталог: tadmin -> upload -> storage
storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи
storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите
storage -> Лекция 5 система за вторична радиолокация
storage -> Толерантност и етничност в медийния дискурс
storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract
storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи
storage -> Лекции по Въведение в статистиката
storage -> Търсене на живот във вселената увод
storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език

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

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