Для специальности 5В073200 «Стандартизация, сертификация и метрология»



страница1/10
Дата06.06.2016
Размер1.01 Mb.
ТипЛекция
  1   2   3   4   5   6   7   8   9   10
    Навигация по данной странице:
  • ЛЕКЦИИ


Министерство образования и науки республики Казахстан Государственный университет имени Шакарима города Семей


УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ
по дисциплине «Базы данных и экспертные системых»

для специальности

5В073200 «Стандартизация, сертификация и метрология»

Семей


2014

Предисловие

1. РАЗРАБОТАНО


Составитель _________ «______» ________ 2014 г. Жанузаков Е. Т.,

преподаватель кафедры «Автоматики и электротехники»

2. ОБСУЖДЕНО

2.1 На заседании кафедры «Автоматики и электротехники»


Протокол от «_____» __________ 2014 г., №____
Заведующий кафедрой ____________ А.Д.Золотов
2.2. На заседании учебно-методического бюро ФИКТ

Протокол от «______» __________ 2014 года, № _____.


Председатель __________________Бекбаева Р.С.

ЛЕКЦИИ


Лекция 1. Модели данных. Введение в реляционную модель данных.

При работе с СУБД разные люди и разные программы, запускаемые этими людьми, видят СУБД по-разному. Конечный пользователь работает в каком-то приложении и, скорее всего, ничего не знает о внутренней структуре. Программа, которую использует этот пользователь и, соответственно, программист, написавший эту программу, видят и используют ту часть базы данных, которую им разрешено видеть.  Администратор, позволяющий тем или иным пользователям видеть те или иные данные, видит всю схему базы данных. Группа программистов, разработавшая ядро исполнителя запросов (SQL-сервер), и предоставившая администратору возможность создавать схему базу данных, реализовала отображение базы данных на внешние устройства и в память.

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

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

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

Уровень реализации - физический уровень. На физическом уровне определяется, как хранятся данные и как осуществляется доступ к ним. Например, сервер СУБД реализует в внутри себя именно этот уровень. Как правило, физическое представление не только скрыто от посторонних глаз, но и является частной, закрытой информацией фирмы производителя СУБД.

Реализацией физического уровня, как правило, занимаются специализированные фирмы, такие как Informix Software, Software AG, CA, Oracle Corporation и т.д. Реализацией концептуального и пользовательского уровней занимаются либо программисткие отделы предприятий, либо специализированные фирмы.

К логическому уровню восприятия относится понятие “модель данных”, которое было вкратце затронуто во Введении. Если администратор описывает схему в терминах ссылок и записей и способов поиска, то это - сетевая модель, если в терминах отношений - реляционная. Понятие модели определяет именно доступные, видимые возможности. В принципе, например, для реляционной СУБД внутри может использоваться сетевое представление. Является или нет сервер реляционным, определяется тем, какие базы можно делать с помощью данного сервера. Расссмотрим основные модели более подробно.



Иерархическая модель данных

Иерархические, или древовидные, структуры данных разработаны и используются достаточно давно. Например, большинство методов индексирования базируются именно на древовидных структурах данных. Иерархическая модель данных близка по своей идее к иерархической структуре данных. Но модель описывает не конкретные методы работы и манипулирования ссылками, а способ логического представления данных, то, какими терминами оперирует проектировщик структуры базы данных, когда отражает реальные зависимости с помощью имеющихся в СУБД механизмов.

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

Попробуем представить себе базу данных для описания тематических сборников по некоторой теме. Прежде всего, выделим уровни иерархии. Первый уровень - это издательства. Каждое издательство характеризуется своим названием, юридическим адресом, номером счета в банке. Каждое издательство выпускает несколько сборников. То есть издательство является “родителем” для сборника и связано с сборником соотношением “издает” (разработчик, естественно, вправе выбрать и другой синоним для данной связи, например “публикует”, “печатает” и т.д.). Для каждого сборника появляются такие атрибуты, как размер, периодичность, цена, ответственный редактор, корректор и т.д. В каждом сборнике есть несколько статей (хотя бы, одна). То есть сборник и статья связаны соотношением “включает”. Далее, у каждой статьи есть название, авторы. Авторы представляются отдельным элементом и образуют следующий уровень иерархии. Каждый автор характеризуется фамилией, именем, отчеством, гонораром и т.д. Статьи связаны с автором соотношением “написаны”. Графическое представление этого примера приведено на Рис.2.2. Элементы нарисованы прямоугольниками, их названия даны обычным шрифтом. Связи нарисованы стрелками и их названия даны курсивом. Обращаем внимание читателей, что атрибуты для каждого элемента на этой схеме не показаны - они являются частью элемента данных.

Что касается способов описания конкретных схем, базирующихся на иерархической модели, или языков манипулирования данными, работающими с такой моделью, то они зависят от конкретной реализации. Например, в достаточно давно разработанной системе IMS фирмы IBM (эта система является классическим примером иерархической СУБД) схема для нашего примера будет описана следующим образом):

DBD  NAME  = ТЕМАТИЧЕСКИЕ_СБОРНИКИ


SEGM NAME  = ИЗДАТЕЛЬСТВО
    FIELD NAME = НАЗВАНИЕ
    FIELD NAME = АДРЕС
    FIELD NAME = СЧЕТ
SEGM NAME  = СБОРНИК, PARENT = ИЗДАТЕЛЬСТВО
    FIELD NAME = НАЗВАНИЕ
    FIELD NAME = ПЕРИОДИЧНОСТЬ
    FIELD NAME = ЦЕНА
    FIELD NAME = ОТВЕТСТВЕННЫЙ_РЕДАКТОР
SEGM NAME  = СТАТЬЯ, PARENT = СБОРНИК
    FIELD NAME = НАЗВАНИЕ
SEGM NAME  = АВТОР, PARENT = СТАТЬЯ
    FIELD NAME = ФИО
    FIELD NAME = ГОНОРАР

В данном примере мы не именовали явно связи, которые существуют между разными элементами (в терминологии IMS для нашего понятия “элемент” используется термин “сегмент”). Язык доступа к данным, который поддерживает IMS позволяет обращаться к элементам напрямую, зная название и, возможно, дополнительное условие. Например, можно распечатать названия всех сборников, ответственным редактором которых является некто по фамилии Буквоедов:



Code:

GET UNIQUE СБОРНИК WHERE ОТВЕТСТВЕННЫЙ_РЕДАКТОР = “БУКВОЕДОВ”

/* получили первый сборник */



while true do

       print СБОРНИК.НАЗВАНИЕ

       /* переходим к следующему сборнику */

       GET NEXT СБОРНИК WHERE ОТВЕТСТВЕННЫЙ_РЕДАКТОР = “БУКВОЕДОВ”



end while

 

Выбрав один из сборников в предыдущем примере, можно спуститься “вниз” по иерархии и, например, просмотреть все статьи из выбранного сборника. Для этого существует оператор “движения вниз по иерархии” GET NEXT WITHIN PARENT. Этот оператор позволяет перебрать все элементы-потомки, принадлежащие выбранному элементу. Предположим, мы хотим напечатать не только названия сборников, но и входящие в них статьи:



Code:

GET UNIQUE СБОРНИК WHERE ОТВЕТСТВЕННЫЙ_РЕДАКТОР = “БУКВОЕДОВ”

/* выбрали первый сборник */



while true do

       print “Сборник ”, СБОРНИК.НАЗВАНИЕ

       GET NEXT WITHIN PARENT СТАТЬЯ

       while true do

               print СТАТЬЯ.НАЗВАНИЕ

               GET NEXT WITHIN PARENT СТАТЬЯ

       end while

       GET NEXT СБОРНИК WHERE ОТВЕТСТВЕННЫЙ_РЕДАКТОР = “БУКВОЕДОВ”



end while

 У иерархических СУБД есть достоинства и недостатки. К достоинствам относится возможность реализовать фантастически быстрый поиск нужных значений, когда условия запроса соответствуют иерархии в схеме базе данных. Например, приведенный выше запрос отработает очень быстро. С другой стороны, если запрос не соответствует имеющейся иерархии, то и его программирование, и его исполнение, потребуют значительных усилий. Например, попытки реализовать запрос типа “в скольких сборниках статей опубликовал свои статьи господин Плагиаторов” может оказаться весьма трудной задачей (мы можем искать в направлении от статьи к автору, но не наоборот).

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

Недостатки иерархической модели проистекают от того, что данная модель слишком жесткая. Иерархическая модель очень хорошо подходит для устоявшихся предметных областей с четкими зависимости “родитель-потомок”, то есть к моделям, где есть четкая субординация между понятиями. Там же, где эти условия выполнены, проявляются достоинства иерархической модели - очень быстрая скорость поиска.

Сетевая модель данных

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

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

На данном рисунке представлены элементы только одно класса - описание людей, и на этом множестве для некоторых конкретных пар людей существуют связи, именуемые “муж”, “жена”, “отец”, “мать”, “ребенок”. Поэтому с точки зрения графического представления схемы этой базы данных (а не конкретных данных о семье Петровых), можно использовать следующий рисунок:

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

Если мы вернемся к нашему примеру про издательства тематических сборников (этот пример рассматривался в разделе про иерархические СУБД) и попытаемся расширить его, для того чтобы он более полно соответствовал реальным взаимоотношениям, то схема базы данных будет выглядеть следующим образом:

Существует большое число удачных реализаций сетевой модели данных. В каждой из реализации, как правило, используется свой собственный язык для описания схемы базы данных и доступа к данным. Рассморим в качестве примера язык CODASYL. Этот язык) был разработан специальной ассоциацией и являлся попыткой стандартизировать язык для работы с сетевой моделью данных. Данный язык является классическим примером работы с сетевыми моделями данных. Описание схемы для представления нашего примера со сборниками будект выглядеть примерно так:

RECORD NAME IS ИЗДАТЕЛЬСТВО


01 НАЗВАНИЕ TYPE IS CHARACTER 20
01 АДРЕС TYPE IS CHARACTER 30
01 СЧЕТ IS PICTURE “9999999”
RECORD IS СБОРНИК
01 НАЗВАНИЕ TYPE IS CHARACTER 20
01 FIELD NAME = ПЕРИОДИЧНОСТЬ
01 FIELD NAME = ЦЕНА
01 ОТВЕТСТВЕННЫЙ_РЕДАКТОР TYPE IS CHARACTER 20
RECORD IS СТАТЬЯ
01 НАЗВАНИЕ TYPE IS CHARACTER 20
RECORD IS АВТОР
01 ФИО TYPE IS CHARACTER 20
01 ГОНОРАР IS FIXED

SET NAME IS ВЫПУСКАЕТ


   OWNER IS ИЗДАТЕЛЬСТВО
   MEMBER IS СБОРНИК

SET NAME IS СОДЕРЖИТ


   OWNER IS СБОРНИК
   MEMBER IS СТАТЬЯ
. . . . . . . . . . . . . . .

К достоинствам сетевой модели относится очень высокая скорость поиска и возможность адекватно представлять многие задачи в самых разных предметных областях. Высокая скорость поиска основывается на классическом способе физической реализации сетевой модели - на основе списков. Более подробно о способах физической реализации сетевых СУБД можно почитать в монографиях Дж.Мартина и Дж.Ульмана. Можно обрнатиться и к технической документации доступных сетевых СУБД.

Главным недостатком сетевой модели, как, впрочем, и иерархичесокй, является ее жесткость. Поиск данных, доступ к ним, возможен только по тем связям, которые реально существуют в данной конкретной модели. В нашем примере с издательствами очень легко и быстро можно найти список всех статей, выпущенных издательством “Бухгалтерия и спорт”, но задача поиска издательств, в которых была опубликована статья “Влияние колец Сатурна на своевременную сдачу норм ГТО” будет требовать гораздо больших усилий. Причиной для подобных проблем, по мнению Е.Кодда), является “навигационный” характер сетевых СУБД. Другими словами, при поиске данных сетевая СУБД требует перемещаться только по существующим, заранее предусмотренным связям.

Реляционная модель данных

История реляционных СУБД ведет свое начало с конца 60-х, когда одновремнно несколькими авторами были выдвинуты предложения об использовании теоретико-множественных операторов для организации доступа к данным. Наиболее известными являются работы Е. Кодда. Затем была экспериментальная система управления базми данных System R и использованный в ней язык SEQUEL, который можно считать непосредственным предшественником языка SQL. В настоящее время именно язык SQL является и де-юро, и де-факто стандартом для работы с реляционными СУБД. Например, семейство серверов реляционных баз данных Informix Dynamic Server поддерживают все эти стандарты и, кроме того, обеспечивают дополнительные возможности.

Интересно отметить, что еще в 1980 году Джефри Ульман (J.D. Ullman) писал в своей монографии "Основы систем баз данных" ("Principles of Databse Systems"), что почти все существующие коммерческие системы баз данных базируются либо на сетевой, либо на иерархической модели данных, но не реляционной модели и "эта ситуация будет меняться медленно". Тем не менее, уже в 1985 году ситуация резко поменялась - реляционные СУБД и язык SQL стали очень популярными. А в начале 90-х годов реляционные СУБД и язык SQL практически вытеснили все остальное с рынка СУБД. Причиной для такого кардинального изменения ситуации стала разработка эффективных, быстрых и надежных методов хранения и доступа к реляционным данным.

Понятие отношения и таблицы

Давайте определим, что же такое реляционная СУБД и как в ней представляются данные. Для реляционной СУБД выбрано представление на основе математического понятия "отношение". Оно очень близко к знакомым всем нам понятию "таблица". По-английски отношение называется "relation", отсюда и название "реляционные СУБД (если называть такие базы "относительными", то это может исказить смысл).

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

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


Лекция 2. Реляционная алгебра.

Реляционная алгебра была представлена E. F. Codd в 1972 году. Она состоит из множества операций над отношениями:

  • ВЫБОРКА(SELECT) (σ): извлечь кортежи из отношения, которые удовлетворяют заданным условиям. Пусть R - таблица, содержащая атрибут A. σA=a(R) = {t ∈ R ∣ t(A) = a} где t обозначает кортеж R и t(A) обозначает значение атрибута A кортежа t.

  • ПРОЕКЦИЯ(PROJECT) (π): извлечь заданные атрибуты (колонки) из отношения. Пусть R отношение, содержащее атрибут X. πX(R) = {t(X) ∣ t ∈ R}, где t(X) обозначает значение атрибута X кортежа t.

  • ПРОИЗВЕДЕНИЕ(PRODUCT) (×): построить декартово произведение двух отношений. Пусть R - таблица, со степенью k1 и пусть S таблица со степенью k2. R × S - это множество всех k1 + k2 - кортежей, где первыми являются k1 элементы кортежа R и где последними являются k2 элементы кортежа S.

  • ОБЪЕДИНЕНИЕ(UNION) (∪): построить теоретико-множественное объединение двух таблиц. Даны таблицы R и S (обе должны иметь одинаковую степень),объединение R ∪ S - это множество кортежей, принадлежащих R или S или обоим.

  • ПЕРЕСЕЧЕНИЕ(INTERSECT) (∩): построить теоретико-множественное пересечение двух таблиц. Даны таблицы R и S, R ∪ S - это множество кортежей, принадлежащих R и S. Опять необходимо, чтобы R и S имели одинаковую степень.

  • ВЫЧИТАНИЕ(DIFFERENCE) (− или ∖): построить множество различий двух таблиц. Пусть R и S опять две таблицы с одинаковой степенью. R - S - это множество кортежей R,не принадлежащих S.

  • СОЕДИНЕНИЕ(JOIN) (∏): соединить две таблицы по их общим атрибутам. Пусть R будет таблицей с атрибутами A,B и C и пусть S будет таблицей с атрибутами C,D и E. Есть один атрибут, общий для обоих отношений,атрибут C. R ∏ S = πR.A,R.B,R.C,S.D,S.ER.C=S.C(R × S)). Что же здесь происходит? Во-первых, вычисляется декартово произведение R × S. Затем, выбираются те кортежи, чьи значения общего атрибута C эквивалентны (σR.C = S.C). Теперь мы имеем таблицу, которая содержит атрибут C дважды и мы исправим это, выбросив повторяющуюся колонку.

Внутреннее соединение

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


R A | B | C S C | D | E

---+---+--- ---+---+---

1 | 2 | 3 3 | a | b

4 | 5 | 6 6 | c | d

7 | 8 | 9

Во-первых, мы вычислим декартово произведение R × S и получим:

R x S A | B | R.C | S.C | D | E

---+---+-----+-----+---+---

1 | 2 | 3 | 3 | a | b

1 | 2 | 3 | 6 | c | d

4 | 5 | 6 | 3 | a | b

4 | 5 | 6 | 6 | c | d

7 | 8 | 9 | 3 | a | b

7 | 8 | 9 | 6 | c | d

После выборки σR.C=S.C(R × S)получим:

A | B | R.C | S.C | D | E

---+---+-----+-----+---+---

1 | 2 | 3 | 3 | a | b

4 | 5 | 6 | 6 | c | d

Удалить повторяющуюся колонку S.C можно с помощью проекции следующей операцией: πR.A,R.B,R.C,S.D,S.ER.C=S.C(R × S))и получим:

A | B | C | D | E

---+---+---+---+---

1 | 2 | 3 | a | b

4 | 5 | 6 | c | d



  • ДЕЛЕНИЕ(DIVIDE) (÷): Пусть R будет таблицей с атрибутами A, B, C, и D и пусть S будет таблицей с атрибутами C и D. Мы можем определить деление как: R ÷ S = {t ∣ ∀ ts ∈ S ∃ tr ∈ R так, что tr(A,B)=t∧tr(C,D)=ts} где tr(x,y)означает кортеж таблицы R, который состоит только из элементов x и y. Заметим, что кортеж t состоит только из элементов A и B отношения R.

Зададим следующие таблицы

R A | B | C | D S C | D

---+---+---+--- ---+---

a | b | c | d c | d

a | b | e | f e | f

b | c | e | f

e | d | c | d

e | d | e | f

a | b | d | e

R ÷ S получается

A | B

---+---


a | b

e | d


Более подробное описание и определение реляционной алгебры смотри у [Ullman, 1988 год] или [Дейта, 1994 год].

Пример 2-3. Запрос с использованием реляционной алгебры

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

πSUPPLIER.SNAMEPART.PNAME='Screw'(SUPPLIER ∏ SELLS ∏ PART))

Мы назовём такую операцию запросом. Если мы применим, приведённый выше запрос к таблицам нашего примера (База данных поставщиков и деталей), то получим следующий результат:

SNAME

-------


Smith

Adams




Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   10


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

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