Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Сколько их и какие они разные! Есть совсем маленькие - они умещаются на ладони и весят не больше полкилограмма. И есть великаны, вес которых достигает...полностью>>
'Документ'
1) Гигиена: учебник для студ. учреждений высш. мед. проф. образования/ под ред. Ю.П. Пивоварова. - М.: Издательский центр «Академия», 2013. Том.1 /[Ю....полностью>>
'Документ'
Детектив – это художественное произведение, в основе которого лежит интеллектуальный поединок героя (условно - сыщика) с неким враждебным (преступным)...полностью>>
'Документ'
Как часто вы ловили себя на мысли о том, как вам не симпатичен человек, делающий что-то непривычное или не приличное, с вашей точки зрения. Довольно т...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Оглавление

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

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

1.1 Множества 4

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

1.3 Отношения 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В настоящее время достаточно много литературы, посвященной проектированию баз данных [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. С. Л. Рубинштейн основы общей психологии

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

    Документ
    ... агрегативного ... сравнению объектов ... на изготовлении малых электродвигателей с широким диапазоном применений. С каждым конечным применением, помимо базовой функции ... задач уже содержит элементы решения, устраивающего клиента. Отметим, что для множества ...
  3. Приоритетный национальный проект «образование» Т. А. Пьявченко, В. И. Фиhаев автоматизированные информационно-управляющие системы таганpог 2007

    Документ
    ... [34-36]. В ... множества выполняемых функций на множество взаимосвязанных элементов АИУС. Задача ... на сравнении технических параметров устройств; - оценка на основе комбинации команд; - оценка на ... на основе агрегативных ... объектами с применением развитой ...
  4. С. Торайгырова Региональный центр политических исследований политическая реальность в разнообразных ее проявлениях павлодар 2008 ббк 66(5Каз)

    Документ
    ... 41 пайызын ... задач. С точки зрения политических функций, идеология стремится сплотить, интегрировать общество либо на ... 1985. – 78 с. (36, 46). Пейн Т. Избранные ... множество задач ... агрегативных образований ... на объект, ... «сравнение двух ... – к применению насилия. ...
  5. 1. Экономическая мысль в Древней Греции и Древнем Китае

    Документ
    ... по сравнению ... агрегативных ... на личное потребление, и приближается к положению капиталиста, общественная функция ... станет объектом внешнеторговых ... . 36. ... ". 41. ... задача для дифференциального исчисления. Зато он был активным сторонником применения ... множество ...

Другие похожие документы..