• Реляционные базы данных. Теоретические основы. Решение задач.
  • 1. Основные математические понятия
  • 1.2 Алгебра множеств
  • 1.3 Отношения
  • 1.4 Операции над отношениями.
  • 1.5 Агрегативные функции.
  • 1.6 Дополнительные операции.



  • страница1/3
    Дата09.07.2017
    Размер0.55 Mb.
    ТипРешение

    Реляционная алгебра


      1   2   3

    Оглавление


    Реляционные базы данных.
    Теоретические основы. Решение задач. 2

    1. Основные математические понятия 4

    1.1 Множества 4

    1.2 Алгебра множеств 5

    1.3 Отношения 6

    1.4 Операции над отношениями. 10

    1.5 Агрегативные функции. 20

    1.6 Дополнительные операции. 23

    2. Описание модели 24

    2.1 Концептуальная модель 25

    2.2 Реляционная модель 28

    3 Решение задач в реляционной алгебре 29

    3.1 Простые задачи 30

    3.2 Задачи на сравнение множеств объектов 37

    3.3 Задачи на применение агрегативных функций 42

    4 Особенности записи запросов на SQL 42


    Реляционные базы данных.
    Теоретические основы. Решение задач.


    Данное учебное пособие предназначено для формирования у студентов навыков решения задач при работе с базами данных. В настоящее время наиболее распространенными базами данных являются реляционные базы данных, основанные на реляционных моделях. Реляционные базы данных получили широкое распространение благодаря двум факторам:

    • В основе работы с реляционными моделями лежит математическая теория: теория множеств, реляционная алгебра и реляционное исчисление;

    • Современная вычислительная техника способна хранить большие объемы информации и эффективно выполнять необходимые действия с соответствующим образом структурированными данными.

    В настоящее время достаточно много литературы, посвященной проектированию баз данных [1-4], в которой рассматриваются этапы превращения результатов обследования функционирования некоторого предприятия в реляционную модель, удовлетворяющую критериям полноты, целостности, достоверности хранимых данных, а также методы достижения этих целей: функциональные зависимости и нормализация отношений. Эти разделы в данном пособии не рассматриваются.

    Однако имеется недостаток литературы, в которой делается попытка научить студента решать задачи, то есть по некоторому тексту, написанному на естественном языке записать запрос к базе данных на языке и в терминах, воспринимаемых системой управления базами данных. Основным препятствием для студента на этом этапе является интерпретация текста задачи. Покажем это на примере.

    Казалось бы простая задача: "Получить список студентов, изучающих русский язык". Однако давайте проанализируем сказанное. Что значит, студент изучает русский язык. Это можно понимать так. "В течение всего времени обучения, какое-то время было потрачено на изучение русского языка" или "В течение данного семестра студент изучает русский язык". В первом случае каждый студент хоть какое-то время тратит на изучение русского языка, и поэтому мы можем считать, что любой студент (что тоже самое все студенты) изучает русский язык. Во втором случае только часть студентов в данном семестре изучает русский язык.

    Поэтому при проведении занятий следует уделять достаточно внимания на то, что студент понял задачу именно так, как рассчитывает преподаватель. Еще лучше записывать условие задачи подробнее, добиваясь однозначной ее интерпретации студентами, хотя, если признаться, это не всегда получается.

    Первая часть посвящена основным математическим понятиям, лежащим в основе реляционных баз данных. Каждая операция сопровождается примерами, при описании которых автор опирается на интуитивное понимание студентами используемых отношений, полное описание которых приведено во второй части. Третья часть рассчитана на развитие у студентов мышления множествами объектов. Несмотря на то, что курс теории множеств ими, как правило, уже прослушан, но рассматриваемые там абстрактные примеры a, b, c не сразу распространяются ими на конкретные объекты, такие как студент, группа, дисциплина и т.п. Еще один существенный момент заключается в следующем. В теории множеств совсем не уделяется внимания на размерность элементов множеств, считая их по умолчанию одинаковой размерности. Отсутствие навыков критического отношения к размерности элементов отношений так же отрицательно сказывается на решении задач в области баз данных. Четвертый раздел посвящен записи задач, рассмотренных в третьем разделе, на наиболее распространенном в настоящее время языке запросов к базам данных – SQL. Сохраняя необходимость множественного мышления при анализе задачи, SQL предоставляет некоторое отличие по отношению к реляционной алгебре в записи алгоритма на получение ответа на запрос.

    Для приобретения навыков решения задач по написанию запросов к базам данных необходимо освоить основные математические понятия, лежащие в основе реляционных баз данных.


    1. Основные математические понятия

    1.1 Множества


    Базовым понятием при работе с базами данных является понятие множества.

    Множество – набор, совокупность, собрание каких-либо объектов, называемых его элементами, обладающих общим для всех них характеристическим свойством.

    В этом определении следует остановиться на двух моментах.

    Первое, на что мы хотим обратить внимание, то, что мы абстрагируемся от рассмотрения свойств элементов, из которых множество состоит. Каждый объект сам по себе может иметь разнообразные характеристики или свойства, но как элемент того или иного множества все объекты должны обладать обозначенными свойствами. В качестве примеров можно рассмотреть множество всех студентов или множество всех студентов, изучающих русский язык и т.п. Объектами этих множеств являются разнообразные люди (лица, персоны), просто в данном случае из многих характеристик, которыми обладают лица, интересуют лишь несколько характеристик (свойств), которые имеют соответствующие значения. Для обоих упомянутых множеств объектами являются личности, обладающие разнообразными свойствами, такими как цвет глаз, рост и вес, количество родственников, работает она (личность) или учится (а может быть одновременно и работает и учится); если учится, то на каком курсе, какие изучает дисциплины и еще много разнообразной информации, а если работает, то в какой должности, в каком подразделении и т.п. Разнообразных свойств каждый объект имеет достаточно много, но в зависимости от постановки задачи при ее решении мы ограничиваемся теми, которые прямо или косвенно в ней упомянуты. Поэтому в первом случае – множество всех студентов – мы забываем, не обращаем внимания на все характеристики, кроме одной: учится человек в институте или нет, а во втором – две характеристики, два свойства: учится ли он и при этом среди всех изучаемых им дисциплин должен быть русский язык.

    С точки зрения теории множеств мы говорим, что некоторый объект а принадлежит множеству А (характеристики множества уже определены), если этот объект обладает указанными характеристиками и эти характеристики имеют соответствующие значения. Обозначается этот факт аА. При написании различных программ можно встретить эквивалентную запись: а in А. Если же некоторый объект b не обладает нужным свойством или это свойство не имеет соответствующего значения, то говорят, что b не принадлежит множеству А, что обозначается как bА (другие формы записи: not bА, not b in А, b not in А).

    Может случиться, что множество не содержит ни одного элемента. В этом случае говорят, множество пусто и обозначают такое множество знаком . Иногда говорят в этом случае, что множество не существует (not exists), хотя интерпретировать это надо в том смысле, что множество не содержит ни одного элемента. Наоборот, множество существует, если в нем есть хотя бы один элемент.

    Отметим также тот факт, что по определению множество не может содержать двух одинаковых элементов (мультимножества мы не рассматриваем).

    1.2 Алгебра множеств


    Вторым моментом, на котором следует остановиться – какие операции (действия) можно выполнять над множествами.

    Алгебра – раздел математики, изучающий алгебраические операции.

    Алгебра множеств – раздел теории множеств, занимающийся исследованием операций над множествами.

    Рассмотрим в алгебре множеств те операции, которые часто используются в практике решения задач. Нас интересуют четыре бинарные операции: сравнение, объединение, пересечение и разность [].

    Напомним еще раз. Любая операция над множествами А и В допустима, если эти множества имеют одинаковую природу, то есть обладают общими характеристиками (свойствами).



    Сравнение. Говорят, что множество В является подмножеством множества А, если любой элемент множества В является элементом множества А. Обозначается это ВА. Иногда, чтобы подчеркнуть, что все элементы множества А могут быть элементами множества В, используют специальное обозначение ВА. Мы этого делать не будем, хотя всегда будем допускать возможность совпадения всех элементов. Два множества А и В эквивалентны А=В, тогда и только тогда, когда выполнены оба условия ВА и АВ.

    Объединение. Множество С является объединением множеств А и В (С= АВ), если любой элемент множества С является либо элементом множества А, либо элементом множества В, причем АС и ВС.

    Пересечение. Множество С является пересечением множеств А и В (С= АВ), если множество С содержит все элементы, которые являются одновременно элементами и множества А и множества В, Справедливо, что СА и СВ.

    Для объединения и пересечения справедливы свойства коммутативности АВ=ВА и АВ=ВА и ассоциативности А(ВС)=(АВ)С и А(ВС)=(АВ)С.



    Разность. Множество С является разностью двух множеств А и В (С= А-В), если множество С содержит все элементы из множества А, которых нет в множестве В. Разность двух множеств не коммутативна: А-В≠В-А. Стоит обратить внимание, что если АВ, то А-В=

    Рассмотрим некоторые примеры. Пусть даны два множества, элементы которых указаны в фигурных скобках, причем порядок расположения элементов множества безразличен. A={a, b, c, e, f, h} и


    B={d, e, a, x}. Тогда

    АВ={a, b, c, e, f, h, d, x}

    АВ= {a, e}

    А-В={b, c, f, h}

    В-А={d, x}

    1.3 Отношения


    До сих пор мы рассматривали множества, характеристики которых заданы в самом общем виде. Если же на объекты наложить более строгие условия, то можно ввести дополнительные операции. Основным объектом реляционных баз данных является отношение.

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

    Рассмотрим подробно это определение. Как представлены свойства объекта? Для каждого свойства выбирается некоторое множество значений, называемое доменом, элементы которого (и только они) используются для записи характеристики конкретного объекта. Другими словами, смысл домена в том, чтобы определить роль соответствующей характеристики при описании свойств объекта. Наиболее распространенные домены: числа, строки, булевские значения (истина и ложь), множества значений, заданные перечислением (например, названия дней недели или месяцев), допустимые оценки знаний студентов (пятибалльная, европейская – А, В, С, D, E, FX, F, стобальная и т.п.), названия дисциплин и т.д. Прямое произведение доменов представляет множество всех возможных комбинаций элементов, выбранных из каждого домена. Например, если отношение содержит три свойства, то каждый из элементов отношения определяется тремя значениями, по одному из каждого домена. В любой момент времени в отношении представлена только часть (подмножество) всех возможных комбинаций свойств объекта, причем, как правило, незначительная часть.

    Для чего добавлены слова "объект, рассматриваемый в определенном ракурсе". Слово "объект" используется в самых различных смыслах. Например, студент это объект, множество – объект, отношение объект и т.д. Часто возникает путаница, что именно в данный момент понимается под объектом. При создании модели мы естественно берем не все характеристики реального объекта, а только часть их, рассматривая реальный объект с какой-либо определенной точки зрения, в определенном ракурсе. Как правило, в базе данных информация о реальном объекте хранится в различных ракурсах, и, как правило, разбросана по разным отношениям. Обычно формулировка задачи выполняется в терминах реальных объектов и умение студента состоит в том, чтобы при ее решении выбрать соответствующие поставленной задаче отношения, именно те, в которых хранятся данные об объектах, обозначенных в поставленной задаче.

    Таким образом, отношение можно рассматривать как множество элементов (строк, кортежей), каждый из которых содержит предусмотренные этим отношением значения характеристик некоторого реального объекта.

    Наиболее трудная часть решения задачи студентом состоит как раз в правильной интерпретации текста задачи, выделении тех отношений в базе данных, в которых хранятся характеристики объектов, упомянутых в задаче.

    Отношение можно рассматривать как двумерную таблицу, каждая строка которой соответствует значениям выделенных характеристик объекта, а столбцы – характеристики (свойства, атрибуты) этих объектов. Степенью отношения называется количество атрибутов, а мощностью – количество кортежей.

    Кроме естественных характеристик объектов, таких как вес, рост, оценка знаний следует обратить внимание на особые характеристики, называемые ключами отношения.



    Первичный ключ – характеристика объекта, назначение которой состоит в том, чтобы различать объекты, собранные в одном отношении.

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

    Между разными объектами могут существовать связи. Например, фраза "староста группы" должна интерпретироваться следующим образом. Имеется два различных типа объектов: студенты и группы. Один из студентов, как правило, учащийся в группе, играет в ней особую роль – роль старосты группы. Эта роль и является связью между двумя типами объектов. Кстати, в предыдущем предложении высказана и другая связь между теми же типами объектов – студент учится в группе. Более подробно связи рассматриваются в разделе "проектирование баз данных". Здесь мы только подчеркиваем, что связи в реляционных базах данных реализуются через специальные свойства объектов – внешние ключи.



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

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

    Здесь приходится еще раз подчеркнуть, что в реляционной модели отношениями реализуются как множества объектов, так и факты существования связей между объектами1. В связи с этим, еще раз следует отметить о роли как самих отношений во всей модели, так и о роли любого из атрибутов в каждом отношении. Одной, но достаточно важной составляющей, успешного решения задач в базах данных является четкое представление о той роли, которую атрибут играет в отношении и во всей модели в целом. Именно поэтому при проектировании модели существенное внимание должно быть уделено наименованию атрибутов, чтобы само название подсказывало роль, которую атрибут играет в модели. Не менее важно умение студента воспринимать размерность, которая скрыта в каждом домене. С чисто математической точки зрения домены состоят из одинаковых значений. Например, и возраст студента и номер группы могут быть представлены целыми числами. Однако у студента не должно даже возникнуть мысли складывать или сравнивать значения этих доменов, потому только, что это бессмысленно именно в силу различия размерности; два домена представляют различную природу данных.


    1.4 Операции над отношениями.


    Несколько раз мы подчеркивали, что отношения можно рассматривать как множество кортежей (строк). Следовательно, все ранее определенные операции для множеств применимы для отношений при условии, что отношения имеют одинаковые характеристики, т.е. схемы отношений одинаковы2.

    Каждое отношение обладает схемой, в которой описано имя отношения и имена его свойств (атрибутов). Учитывая специфику отношений как объектов, над ними можно определить ряд специфических операций.



    Реляционная алгебра – совокупность операций, выполняемых над отношениями, в результате применения которых получаем новое отношение с известной схемой.

    При рассмотрении операций следует обратить внимание на две основные характеристики отношения: схема отношения, в которой количество атрибутов называется степенью, и количество кортежей, называемое мощностью. Если схема результата определена однозначно, то мощность результата может быть только оценена, показана в сравнении с мощностью исходных отношений.

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



    Селекция. Мы уже не раз интерпретировали таблицу как множество кортежей (строк), причем каждый кортеж – информация о свойствах некоторого объекта. Можно получить новое отношение, в котором будут только те кортежи из исходного отношения, которые удовлетворяют некоторому условию или, что тоже самое, предикат3 кортежа, вычисленный на значениях его свойств принимает истинное значение.

    R1  <условие> (R),
    где R – исходное отношение, <условие> – предикат, высказывание об одном или нескольких атрибутах отношения R, R1 – результирующее отношение.

    Например, пусть отношение R содержит следующие характеристики о студенте: код, фамилия, Nстуденческого билета, дата рождения, пол, выплачиваемая стипендия, т.е. схема отношения R имеет вид



    R = R(Кст, Фио, Nст_билета, Д_р, Пол, Стипендия)

    Правомерны следующие условия:



    • Пол = "женский"

    • Д_р = "01.10.1980"

    • Пол = "мужской"  Стипендия > 1000 руб.

    • Д_р ≥ "01.01.1980"  Д_р ≤ "31.12.1980"  Пол = "женский"

    Подставляя любое из этих условий, мы получим отношение – множество студентов, для каждого из которых справедливо (истинно) записанное условие.

    Особо следует обговорить возможность использования функций при записи условия. В некоторых СУБД это допускается, в других нет. В данном пособии мы будем считать допустимой, например, такую запись условия: Месяц(Д_р) ≥ 11, что означает выделение всех, родившихся в ноябре или декабре.

    Для селекции справедливо

    <условие1> (<условие2> (R)) = <условие1> <условие2> (R),


    т.е. последовательное применение двух селекций эквивалентно применению одной селекции с условием равным конъюнкции двух условий.

    Очевидно, что схема результата R1 совпадает со схемой R, а мощность R1, как правило, становится меньше мощности R, хотя бывают случаи, что она так же не изменяется. Например, если в качестве условия взять Возраст ≤ 50 лет, то для любого студента это условие будет истинным.



    Проекция. Получим новое отношение, оставив из исходного только некоторые свойства.

    R1  <список атрибутов> (R),
    где R – исходное отношение, <список атрибутов> –перечисление имен некоторых свойств (атрибутов) отношения R, записанных через запятую, R1 – результирующее отношение.

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

    Фам (R),

    Фам, Пол (R),

    Nстбилета (R),

    Nстбилета , Пол, Стипендия (R),

    Запись <список атрибутов1> (<список атрибутов2> (R)) допустима, если в <список атрибутов1> присутствуют только те атрибуты, которые есть в <список атрибутов2> (<список атрибутов1><список атрибутов2>). В этом случае

    <список атрибутов1> (<список атрибутов2> (R)) = <список атрибутов1> (R)

    Именно поэтому в практике решения задач последовательное применение проекций не используется.

    Принципиально, есть ли среди списка атрибутов ключевой атрибут отношения или нет. Если ключевой атрибут присутствует, то количество кортежей в результирующем отношении будет таким же, как и в исходном; в противном случае количество кортежей в R1, как правило, уменьшается по сравнению с R. Например, если записать



    R1  Пол (R),
    то в отношении R1 будет не более двух кортежей.

    Иногда оказывается выгодным переименование атрибута (см. ниже естественное соединение). Как правило, это относится к атрибутам, играющим роль внешних ключей. Например, если код студента (сокращенно, Кст) – первичный ключ в отношении студент, то для реализации связи "староста группы" естественно выбрать в качестве названия внешнего ключа код старосты (Кстг). Домены этих двух атрибутов должны совпадать. При решении задачи сначала было важно подчеркнуть, что речь идет о старосте группы (используем имя Кстг). Но мы знаем, что староста группы это то же студент и в некоторый момент времени нам выгодно забыть о его роли старосты и перейти к наименованию Кст, как у обычного студента. Операция проекции может сопровождаться переименованием атрибутов



    R1(<список новых имен>)  <список атрибутов> (R),
    где список новых имен содержит столько же имен, что и список атрибутов, а порядок новых имен соответствует порядку имен в списке атрибутов.

    Более сложными представляются бинарные операции. Наиболее востребованной бинарной операцией является естественное соединение, но чтобы осознать действие этой операции подойдем к ней постепенно, рассмотрев предварительно три другие операции.



    Декартово произведение (). Пусть имеются два отношения R1 и R2 со схемами R1(А1,…,Аn) и R2(В1,…,Вm) и соответственно мощностями N и M. Декартовым произведениемэтих отношений называется отношение R3(А1,…,Аn1,…,Вm), которое содержит все возможные комбинации кортежей из R1 и R2. Мощность отношения R3 – M*N. Первичным ключом R3 можно взять совокупность первичных ключей отношений R1 и R2.

    Может случиться, что в R1 и R2 есть совпадающие по имени атрибуты: R1(А12,…,Аn) и R2(А12,…,Вm). Чтобы их различать в результате R3 в схему R3 включим эти имена с указанием имен отношений, отделив их точкой R3(R112,…,Аn,R212,…,Вm).



    Пусть мы имеем два отношения: СТУДЕНТ(Кст, Фам, Стип, Nгр) и ГРУППА(Nгр, Спец, Кстг). Здесь Кст – код студентов, в качестве которого можно рассматривать номер студенческого билета, Фио – его фамилия, СТУДЕНТ.Nгр – номер группы, в которой студент учится, Спец – название специальности, которой обучаются все студенты группы, Кстг – код студента, являющегося старостой группы.

    СТУДЕНТ

    Кст

    Фио

    Nгр







    ГРУППА

    Nгр

    Спец

    Кстг




    105

    Петров

    3










    2

    Физика

    216




    318

    Иванов

    2










    1

    Химия

    Nil




    216

    Сидоров

    2










    3

    Матем

    105




    418

    Алексеев

    3



















    Тогда СТ_ГР1  СТУДЕНТ  ГРУППА примет вид.

    СТ_ГР1

    Кст

    Фио

    СТУДЕНТ.Nгр

    ГРУППА.Nгр

    Спец

    Кстг




    105

    Петров

    3

    2

    Физика

    216




    318

    Иванов

    2

    2

    Физика

    216




    216

    Сидоров

    2

    2

    Физика

    216




    418

    Алексеев

    3

    2

    Физика

    216




    105

    Петров

    3

    1

    Химия

    Nil




    318

    Иванов

    2

    1

    Химия

    Nil




    216

    Сидоров

    2

    1

    Химия

    Nil




    418

    Алексеев

    3

    1

    Химия

    Nil




    105

    Петров

    3

    3

    Матем

    105




    318

    Иванов

    2

    3

    Матем

    105




    216

    Сидоров

    2

    3

    Матем

    105




    418

    Алексеев

    3

    3

    Матем

    105

    -соединение (><). Отношение R3(А1,…,Аn1,…,Вm)

    R3(А1,…,Аn1,…,Вm) R1(А1,…,Аn) ><<условие> R2(В1,…,Вm)

    называется -соединением относительно R1(А1,…,Аn) и R2(В1,…,Вm), если из всех кортежей декартова произведения R1(А1,…,Аn) и R2(В1,…,Вm) остаются только те, которые удовлетворяют заданному условию. По получаемому результату -соединение эквивалентно применению двух операций



    R3(А1,…,Аn1,…,Вm) <условие> (R1(А1,…,Аn) R2(В1,…,Вm)),
    из чего делается вывод о схеме и мощности результата.

    Существует ограничение на правило записи условия. Пусть А1,…,Аn1,…,Вm атрибуты отношений. Тогда правильными условиями будут:



    • F = Аi op Bj, где i[1,n], j[1,m], op – одна из операций сравнения (<, , =, , , >). Естественно предположение, что домены Аi и Bj сравнимы.

    • Если F1 и F2 – условия, то F1F2, F1F2 также условия.

    В нашем примере

    СТ_ГР2  СТУДЕНТ >< СТУДЕНТ.Nгр ГРУППА.Nгр ГРУППА


    получится из декартова произведения вычеркиванием соответствующих кортежей, для которых не выполнено условие.

    СТ_ГР2

    Кст

    Фио

    СТУДЕНТ.Nгр

    ГРУППА.Nгр

    Спец

    Кстг




    105

    Петров

    3

    2

    Физика

    216




    318

    Иванов

    2

    2

    Физика

    216




    216

    Сидоров

    2

    2

    Физика

    216




    418

    Алексеев

    3

    2

    Физика

    216




    105

    Петров

    3

    1

    Химия

    Nil




    318

    Иванов

    2

    1

    Химия

    Nil




    216

    Сидоров

    2

    1

    Химия

    Nil




    418

    Алексеев

    3

    1

    Химия

    Nil




    105

    Петров

    3

    3

    Матем

    105




    318

    Иванов

    2

    3

    Матем

    105




    216

    Сидоров

    2

    3

    Матем

    105




    418

    Алексеев

    3

    3

    Матем

    105

    и примет вид.

    СТ_ГР2

    Кст

    Фио

    СТУДЕНТ.Nгр

    ГРУППА.Nгр

    Спец

    Кстг




    318

    Иванов

    2

    2

    Физика

    216




    216

    Сидоров

    2

    2

    Физика

    216




    105

    Петров

    3

    3

    Матем

    105




    318

    Иванов

    2

    3

    Матем

    105




    216

    Сидоров

    2

    3

    Матем

    105




    418

    Алексеев

    3

    3

    Матем

    105

    Equi-соединение отличается от -соединения только правилом записи условия (обозначение тоже, что и для -соединения). При записи условия Equi-соединения можно пользоваться только конъюнкцией и только одной операцией сравнения – сравнением на равенство.

    В нашем примере

    СТ_ГР3  СТУДЕНТ >< СТУДЕНТ.Nгр = ГРУППА.Nгр ГРУППА
    примет вид.


    СТ_ГР3

    Кст

    Фио

    СТУДЕНТ.Nгр

    ГРУППА.Nгр

    Спец

    Кстар




    318

    Иванов

    2

    2

    Физика

    216




    216

    Сидоров

    2

    2

    Физика

    216




    105

    Петров

    3

    3

    Матем

    105




    418

    Алексеев

    3

    3

    Матем

    105

    Естественное соединение (*). Так как в Equi-соединении при записи условия допускается только конъюнкция сравнений атрибутов, то в результирующем отношении мы получим одну (или несколько) пар атрибутов, значения которых в каждом из кортежей совпадают. Естественно, один атрибут из пары совпадающих атрибутов не несет дополнительной смысловой нагрузки и может быть удален из результата. Более того, предполагается, что названия сравниваемых атрибутов совпадают, что позволяет определить естественное соединение следующим образом. Пусть даны два отношения R1(C1,…,Ck,A1,…,An) и R2(C1,…,Ck,B1,…,Bm). Тогда естественное соединение

    R3(C1,…,Ck,A1,…,An,B1,…,Bm)

    R1(C1,…,Ck,A1,…,An) * R2(C1,…,Ck,B1,…,Bm)

    эквивалентно следующей записи

    R3  ,

    Где b – условие попарного совпадения значений атрибутов C1,…,Ck в отношениях R1 и R2.

    В нашем примере

    СТ_ГР  СТУДЕНТ ><СТУДЕНТ.Nгр ГРУППА.Nгр ГРУППА


    примет вид


    СТ_ГР

    Кст

    Фио

    Nгр

    Спец

    Кстг




    318

    Иванов

    2

    Физика

    216




    216

    Сидоров

    2

    Физика

    216




    105

    Петров

    3

    Матем

    105




    418

    Алексеев

    3

    Матем

    105

    Если бы схема отношения ГРУППА была задана в виде ГРУППА(Nгр, Спец, Кст), то естественное произведение было бы выполнено по совпадению значений двух атрибутов "Кст" и "Nгр" и результат принял бы вид

    СТ_ГР4

    Кст

    Фио

    Nгр

    Спец




    216

    Сидоров

    2

    Физика




    105

    Петров

    3

    Матем

    что соответствует задаче: получить номера групп с указанием специальности и кода и фамилии старосты.

    1.5 Агрегативные функции.


    Рассмотренные выше операции реляционной алгебры имели одну характерную особенность: атрибуты результата, их ролевые характеристики и, соответственно, их домены были получены из исходных отношений.

    Однако при решении задач достаточно часто возникает необходимость получить информацию, касающуюся значений нескольких кортежей исходного отношения. Таким образом, в результирующем отношении появляются атрибуты, которые либо имеют домен, отсутствующий в исходном отношении, либо домен тот же, но атрибут имеет другую ролевую характеристику. По этой причине агрегативные функции, не являясь в прямом смысле операциями реляционной алгебры, используются наравне с ними при решении задач.

    Общий вид агрегативной функции

    R1(<список атрибутов>,<список имен>)

    <список атрибутов> F<список функций> (R)

    где <список атрибутов> – имена атрибутов из R, по которым происходит агрегация кортежей отношения R; <список функций> – названия функций, используемых при агрегации; <список имен> – имена, которыми называются атрибуты, соответствующие списку функций.

    Агрегативные функции работают по следующему принципу. Рассмотрим отношение R2  <список атрибутов> (R). Так как одинаковых кортежей в отношении быть не может, то мы получим новое отношение, мощность которого равна количеству различных комбинаций значений по списку атрибутов отношения R. Именно такова будет мощность отношения R1. Можно сказать, что два отношения <список атрибутов> (R) и <список атрибутов> (R1) совпадают. Далее допустим, что все кортежи отношения R упорядочены по комбинации значений атрибутов из списка, то есть сначала расположены (сгруппированы, агрегированы – отсюда и название) все кортежи, имеющие одинаковые значения атрибутов из списка, потом все кортежи, имеющие другую комбинацию значений атрибутов из списка, потом третью и т.д. Тогда для каждой комбинации одинаковых значений атрибутов из списка могут быть вычислены значения следующих функций


    • count(A) – количество кортежей, имеющих значение атрибута А из его домена4;

    • max(A), min(A) – выбирается максимальное (минимальное) значение атрибута А;

    • sum(A) – вычисляется сумма значений атрибута А;

    • avg(A) – вычисляется среднее значение атрибута А (sum(A) / count(A)).

    Естественно, что sum(A) и avg(A) определены только для атрибутов, домен которых содержит числовые значения.

    В качестве примера рассмотрим несколько измененное отношение СТУДЕНТ



    СТУДЕНТ

    Кст

    Фио

    Nгр

    Стипендия




    105

    Петров

    3

    600.00




    318

    Иванов

    2

    800.00




    216

    Сидоров

    2

    1000.00




    163

    Захаров

    3

    600.00




    258

    Баева

    2

    800.00




    436

    Кудрина

    2

    400.00




    418

    Алексеев

    3

    300.00

    Поставим задачу: показать для каждой группы (их всего две: вторая и третья) количество студентов, максимальную и среднюю стипендию. Решение следует записать следующим образом.

    R1(Nгр, Численность, Макс_стип, Средняя_стип)

    Nгр F count, max(стипендия),avg(стипендия)(R)

    Результат примет вид



    R1

    Nгр

    Численность

    Макс_стип

    Средняя_стип




    2

    4

    1000.00

    750.00




    3

    3

    600.00

    500.00

    1.6 Дополнительные операции.


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

    Внешнее объединение (==). Может случиться, что схемы двух отношений совпадают частично, т.е. часть атрибутов совпадает, а часть различается. Например, имеем СТУДЕНТ(Код, Фио, Стипендия, Nгр) и ПЕДАГОГ(Код, Фио, Зарплата, Nкаф). В данном примере мы специально выбрали одинаковое написание первичного ключа "Код". Если можно предположить совпадение доменов атрибутов "Стипендия" и "Зарплата", то рассчитывать на совпадение доменов для "Nгр" и "Nкаф" не приходится, а, значит, объединить эти два отношения нельзя. При желании можно выполнить внешнее объединение, которое предполагает выравнивание схем отношений добавлением в каждое из них недостающих атрибутов из другого и заполнением значений этих атрибутов в кортежах значением Nil, после чего объединение выполняется обычным образом. Следует отметить, что при таком объединении встает много побочных проблем. Что считать первичным ключом, не нарушается ли правило функциональной зависимости и т.п. Именно поэтому, внешнее объединение если и применяется, то крайне осторожно.

    Внешнее соединение (=><=). Если внешнее объединение анализирует схемы отношений, то внешнее соединение анализирует, насколько жестко следует подходить к оставлению кортежей в результате. Если мы обратимся, к примеру, рассмотренному в конце раздела 1.4

    СТУДЕНТ

    Кст

    Фио

    Nгр







    ГРУППА

    Nгр

    Спец

    Кст




    105

    Петров

    3










    2

    Физика

    216




    318

    Иванов

    2










    1

    Химия

    Nil




    216

    Сидоров

    2










    3

    Матем

    105




    418

    Алексеев

    3



















    то обнаружим, что в результате естественного соединения5 пропала информация о первой группе, так как староста в ней пока не назначен. Воспользовавшись внешним соединением (в данном случае правым (><=)), мы оставим в результате информацию о первой группе, несмотря на то, что этому кортежу в отношении ГРУППА не соответствует ни один кортеж из отношения СТУДЕНТ. Значения атрибутов отношения СТУДЕНТ для этого кортежа заполняются значением Nil.

    СТ_ГР5

    Кст

    Фио

    Nгр

    Спец




    216

    Сидоров

    2

    Физика




    Nil

    Nil

    1

    Химия




    105

    Петров

    3

    Матем

    Из объяснения примера понятно, что для левого внешнего соединения (=><) за основу берутся все кортежи левого отношения, а внешнее соединение предполагает, что не происходит потери кортежей, как левого, так и правого отношений.
      1   2   3

    Коьрта
    Контакты

        Главная страница


    Реляционная алгебра