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

Основная операция над множествами. Мощность множества.

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

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

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

Заметим, что понятие универсального множества четко не определено. Универсальное множество всегда можно включить в другое множество W, которое тоже будет универсальным.

Множество является пустым, если оно не содержит элементов.

Множество, не являющееся пустым, называется непустым.

Равными называются два множества А и В, состоящие из одинаковых элементов (А=В).

Кортежи. Декартово произведение.

В математике часто приходится иметь дело с упорядоченными множествами, с кортежами.

Пример.

∆АВС задается на плоскости кортежем из 6 чисел: <x₁,y₁;x₂,y₂;x₃,y₃>, где А(x₁,y₁), В(x₂,y₂), С(x₃,y₃) – координаты вершин.

Кортежем длины nиз элементов множества А называется упорядоченная конечная последовательность.

α= <a₁,a₂,…,a_n>, равная элементам этого множества.здесь элемент a_k – kкоордината или k компонент кортежа α.

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

Т.е. кортежи α =<x₁,…,x_m>

β = <y₁,…,y_n>

равны m = n

x_k = y_k

Примечание.

Кортеж, не содержащий ни одного элемента, называется пустым.

Пусть заданы множества А₁, А₂, …, А_n. Декартовым (прямым) произведениемэтих множеств, называется множество А₁*А₂*…*А_n, состоящее из всех кортежей, вида <a₁,a₂,…,a_n> длины k, в которых a_kϵA_k, 1≤k≤n.

Поскольку для задания кортежей важен порядок, поэтому порядок множителей важен и в декартовом произведении.

Отношения фундаментальных основ баз данных. Бинарные отношения и их свойства.

Соответствие между равными множествами называется отношением на данноммн-ве А.

Пусть А и В конечные множества, вспоминаем, что декартово произведение множества А и В состоит из всех упорядоченных пар а и b, где А принадлежит а ϵ А.

Бинарным отношением между элементами множества А и В называется подмножествоRс А*В.

Пример.

а и в находятся в отношении R

а≤в

Отношение эквивалентности.

Бинарное отношение Rназывается отношением эквивалентности, если оно одновременно обладает тремя свойствами: рефлективностью, симметричностью и транзитивностью.

Обозначим а Qbили a ~b

« а эквивалентно в в отношении R»

Не пересекающиеподмножества на которых разбивается множество М называется классами эквивалентности.

Отношение порядка.

Отношение Rназывается отношением порядка на множестве М, если оно обладает свойствами антисимметричности и транзитивности.

Отношение Rназывается множеством А²называется отношением порядка, если оно обладает рефлективностью, антисимметричностью и транзитивностью.

Антисимметричное транзитивное отношение называется отношением порядка.

Отношение порядка может быть рефлексивным и тогда оно называется отношением нестрогого порядка.

Отношение порядка может быть анти рефлексивным и тогда оно называется отношением строгого порядка.

Отношение порядка может быть полным и тогда оно называется отношением полного или линейного порядка.

Отношение порядка может не обладать свойством полноты и тогда оно называется отношением частичного порядка.

Как правило отношение строгого порядка обозначается <, а отношение частичного порядка ≤.

В общем случае отношение порядка обозначается Множества и операции над множествами - student2.ru

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

Заметим, что для любых х,у =>x≤yт.е. любые два числа сравнимы между собой. Такие отношения называется полного порядка.

Предикат данного отношения есть x≤y

Пример.

Рассмотрим на множестве А сотрудников какого-либо учреждения. Отношения создадим следующим образом:

«сотрудник х предшествует сотруднику у» тогда и только тогда, когда выполняется одно из условий:

1. х = у

2. х – начальник у (н\о непосредственные)

Назовем такое отношение «быть начальников». Легко проверить, что данное отношение является отношением порядка.

В отличии от предыдущих примеров существуют такие пары сотрудников х и у для которых не выполняется х < у, ни х≤у (например, если х и у являются сослуживцами) это отношение частичного порядка.

Функциональные отношения.

Отношение Rнад А₁*А₂ называется функцией, если оно обладает следующими свойствами:

1. Если (х,у) ϵ Rи (х,у) ϵ R, то у = z(однозначность функций)

2. Остальные свойства аналогичны свойствам отношения порядка.

n-арные отношения (отношения степени n)

В математики n-арные рассматривают относительность редко, в отличии от БД, гденаиболее возможные являются равномерные, заданной на декартовом произведении более, чем 2х множеств.

Пример

В каком-либо университете учатся студенты Иванов, Петров и Сидоров, лекции им читает Иваненко, Петренко, Сидоренко. Известно: Иваненко читает лекции по ЛА и БД, соответственно 40 и 80 часов в семестр. Петренко читает лекции по МА 50 часов. Сидоренко читает лекции по МА и ЛА 40 и 50 часов. Студент Иванов посещает лекции по ЛА у Сидоренко и по БД у Иваненко, студент Петров ЛА-Иваненко, МА – Петренко, студент Сидоров МА – Петренко, БД – Иваненко.

Чтобы формально описать данную ситуацию( если предположим необходимо разобрать ИС, фиксир. ход учебного процесса), введем три множества.

1. Множество преподавателей А{Иваненко, Петренко, Сидоренко}

2. Множество предметов В{ЛА, МА, БД}

3. Множество студентов С{Иванов, Петров, Сидоров}

Имеющиеся факты можно разделить на 2 группы:

1. факты 1-3

2. факты 4-6

Чтобы отобразить факты 1-2 введем отношение R, на декартовом произведении

R₁с А*В*Q, где Q – множество рациональных чисел.

А именно упорядоченная тройка ([x,y,z) ϵR₁óпреподаватель х читает предмет у в количество nчасов.

Назовет R₁– «читает лекции по R₁удобно представить в виде таблицы.

А (преподаватель)	В (предмет)	Q
Иваненко	ЛА
Иваненко	БД
Сидоренко	МА
Сидоренко	ЛА
Петренко	МА

Чтобы отобразить факты 4-6, введем R₂

R₂с С*В*А

(z,y,x) ϵR₂

C (студент)	В (предмет)	А (преподаватель)

Рассмотрим R₂более подробно, оно задано на декартовом произведении

Ω = С*В*А

3*3*3 = 27 картежей

«Студенты, лекции, преподаватели»

Множество Ω - совокупность всех возможных вариантов посещений студентами лекций.

Отношение R₂отображает текущее состояние учебного процесса.

Очевидно, что R₂является изменяющимися со временем отношениями.

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

Транзитивные замыкания отношений.

Пусть отношение Rзадано на декартовом произведении в степени некоторого множества А.

Транзитивным замыканием Rназывается новое отношение Ṝ, состоящее из картежей (х,у) для которых выполняется:

1. либо картеж (х,у) ϵ R

2. либо найдется конечная последовательность z₁,z₂,…,z_nϵA, такая что (х, z₁)(z₁,z₂),…,(z_n,y) ϵК

Пусть множество А – множество деталей конструкций

А = {Болт, Гайка; двигатель, Автомобиль; Колесо, Ось}

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

Взаимосвязь деталей описывает отношение R («непосредственно используется в…»)

Конструкция	Где используется
Болт	Двигатель
Болт	Колесо
Гайка	Колесо
Колесо	Автомобиль
Ось	Колесо

Транзитивные отношения Ṝ представляется в виде таблицы:

Конструкции	Где используются
Болт	Двигатель
Болт	Колесо
Гайка	Двигатель
Гайка	Колесо
Колесо	Автомобиль
Ось	Колесо
Болт	Автомобиль
Гайка	Автомобиль
Ось	Автомобиль

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

Краткие выводы об основных понятиях и терминах.

1. Отношение – это подмножество декартового произведения множеств. Отношения состоят из однотипных картежей.

2. Отношения являются математическим аналогом понятия таблица.

3. Отношение обладает степенью и мощностью.

Степень отношения – это количество элементов в каждом кортеже отношения (аналог – количество столбцов в таблице)

Мощность отношения – мощность множества кортежей отношения( аналог – количество строк в таблице)

Базовые понятия реляционной модели данных (РМД)

Типы данных и домены. Общая характеристика РМД

Основы РМД были заложены Коддом в 1970. Это работы послужила стимулом для большого числа статей, в которых РМД получила свое дальнейшее развитие.

Наиболее распространённая трактовка РМД принадлежит Дейту. Согласно Дуйту, РМД состоит из 3х частей:

1. Структурная часть

2. Целостная часть

3. Манипуляционная часть

1. Описывает, какие объекты рассматриваются в РМД. Постулируется, что единственной структурой данных, используемой в РМД является Нормализованные n-арные отношения.

2. Описывает ограничения специального вида, которые должны выполняться в любых БД. Эта целостность сущности, целостность внешних ключей.

3. Описывает 2 эквивалентных способа манипулирования реляционными данными – реляционную алгебру, реляционное исчисление.

Типы данных

Любые данные, используемые в программирования имеют свои типы.

Примечание: РМД требует, чтобы типы используемых данных были простыми

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

Как правило типы данных делятся на 3 группы:

1. Простые

2. Структурированные

3. Ссылочные

01.03.12

Тема: SQL

ОПЕРАТОР SELECT

Select – ключевое слово которое сообщает СУБД, что эта команда – запрос. Все запросы начинаются этим словом с последующим пробелом. За ним может слеловать способ выборки – с удалением дубликатов или без удаления (ALL – все поля, все записи по всем столбцам с указанием определенных столбцов). Затем следует список перечисленных через запятую столбцов, либо знак ‘*’.

Синтаксис оператора Select

SELECT [ALL|DISTINCT] (список полей| или *)

FROM (список таблиц)

[WHERE (условие выборки или соединение) ]

[GROUP BY (список полей для вывода результатов)]

[HAVING (условие выборки для группы)]

[ORDER BY (список полей, по которым отсортировать записи)]

ALL – означает, что в результирующий набор строк включаются все строки удовлетворяющие условию запроса

DISTINCT – означает, что в результирующем набор строк попадают все строки, не имеющие дубликатов

Символ * означает, что в результирующий набор попадут все строки из всех столбцов

FROM – в разделе FROM задается список исходных отношений (таблиц).

В разделе WHERE задается условие отбора.

В разделе GROUP BY – задается список полей группировки.

HAVING – задается условие, предъявляемой каждой группе.

В разделе ORDER BY указывается способ сортировки.

В разделе WHERE могут быть использованы следующие предикаты:

1.предикаты сравнения (<,>,<=,<>)

2.предикат between A and B

3.предикат вхождения во множество IN

4. Предикаты сравнения с образцом LIKE и NOT LIKE

5.предикат сравнения с не определенным значением IS NULL

Для МОБД будет состоять из трех таблиц: R1, R2, R3

Пр.1: Select *

From r1,r2;

Примечание! Этот запрос соответствует декартовому произведению.

Пр.2: (проекция дек. Произв.)

Select r1.a, r2.b

From r1,r2;

Этот запрос соответствует проекции декартово произведения двух таблиц на два столбца (а – с таблицы r1, и b с таблицы r2. При этом дубликаты всех строк сохранены.

Пр.3:(вывести список всех групп без повторений) где должны пройти экзамены

Select distinct группа

From r3

Пр.4: Вывести списко студентов которые сдали экзамен по БД

Select ФИО

From r1

Where дисциплина = “БД” and оценка = 5;

Пр.5:вывести список всех студентов которым надо сдавать экзамен с указанием названием дисциплин, по которым должны проводится экзамены

Select ФИО, дисциплина

From r2, r3

Where r2 группа = r3 группа;

Здесь левая часть раздела where задает условия соединения отношения r2 , r3, при отсутствии условия соединения. Результат будет равен декартовому произведению (расширенному). В этом случае каждому студенту были бы приписаны дисциплины из отношения r3, а не те, по которым нужно сдавать экзамены.

Пр. Вывести список лентяев, имеющихся несколько двоек (максимум 2)

Select distinct r1. ФИО

From r1 a, r1 b

Where a.фио=b.фио and

a.дисциплина <> b.дисциплина

a.оценка<=2 and b. Оценка<=2;

Здесь мы используем псевдоним (a,b) для наименования отношения r1, так как для записи условия поиска необходимо работать с двумя экземплярами а и b указанного отношения r1.

Типы данных в БД

В языке sql поддерживаются следующие типы данных

-CHARACTER (n) или CHAR(n) – символьные строки фиксированной длины в n символов

-NUMERIC [(n,m)] – точные числа. Здесь n общее количество в числе, n количество цифр справа в десятичной точке

-DECIMAL [(n,m)]

-DEC[(n,m)]

-INTEGER или INT

-SMALLINT – целые числа меньшего диапазона, вещественный тип данных в одинарной точности.

-FLOA [(n)] – числа в большом формате, хранимы в плавающем формате, n – число байт, резервируемое для храниения одного числа.

-REAL – вещественный тип который соответствует числам в плавающем формате меньшей точности чем FLOAT.

-DOUBE PRECISION – большая точность чем REAL

-VARCHAR (n) – строки переменной длины n.

-NCHAR(N) – строки локализованных чисел, фиксируемой длины (n)

-NCHAR VARYING – строки локализованных чисел

-DATE – календарная дата

-TIMESTAMP(точность)- дата и время

-INTERVAL – временной интервал

Табл. Агрегат.ф

Функция	Результат
Count
Sum
Avg
Min	Минимальное значение
Max	Максимальное значение

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

Select r1.дисциплина, count(*)

From r1

Group by r.дисциплина;

Результат

Дисциплина	Count(*)
БД
а/я

Пр. найти количество студентов успешно сдавших экзамены

Select count(*)

From r1

Where оценка>2;

Пр. Вычислить количество разных оценок полученных по каждой дисциплине

Select r1.дисциплина, count(distinct r.оценка)

From r1

Where r1.оценка<>0

group by r1.дисциплина;

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

Select r2.группа, r1.дисциплина, count(*) avg(оценка)

From r1,r2

Where r1.фио = r2.фио and

R1.оценка>2 and r1.оценка<>0

Group by r1.группа, r1.дисциплина;

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

Select r2.группы

From r1,r2

Where r1.фио = r2.фио and

R1.лценка=2

Group by r2.группа, r1.дисциплина

Having count(*)>1;

22.03.2012

Вопросы по контрольной:

1.Операции соединения

2.Операции объединения.

3.Создание и удаление таблицы

4.Модификация таблиц

5.Транзакции. Определение и оператор транзакций

6.Краткая характеристика первых 3 нормальных форм

7.Нормализация БД

Декартово произведение множеств

Декартово произведение двух таблиц

Синтаксис: select список_столбцов from T1,T2,…,Tn – этот запрос возвращает набор строк(записей) полученный в результате декартово произведения наборов записей из указанных таблиц.

Примечание! Таблицы могут быть как таблицами БД, так и виртуальными таблицами, возвращаемыми запросами.

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

Пример: select список_столбцов from MyTab T1, My Tab T2;

В Майкрософт для получения декартово произведения возможно использование выражения (select список_столбцов from T1, T2,…,Tn;)

Объединение новой записи (union)

Нередко требуется объединить записи двух или более таблиц с похожими структурами в одну таблицу, иначе говоря к набору записей возвращаемому одним запросом требуется добавить записи возвращаемыми другим запросом.
Синтаксис: запрос1 union запрос2;

При этом в результирующих таблицах остаются только отличающиеся записи. Чтобы сохранить записи, после оператора union следует добавить ключевое слово all.

Пример: даны таблицы клиенты и контакты. Пусть они имеют однотипные столбцы Имя и Адрес. Чтобы заполнить данные о клиентах и таблицу Контакты, необходимо выполнить следующий запрос:

Select Имя, Адрес from клиенты

Union

Select Имя, Адрес, from контакты;

Возможно, что в объединяемых таблицах Клиент и Контакты имеются записи с одинаковыми парами значениями в столбцах Имя и Адрес. Однако в результирующей таблице запроса повторений не будет, как если использовать оператор union distinct.

Оператор union можно применять только к таблицам, удовлетворяющим требованиям

1. Количество столбцов объединяемых таблиц должны быть равны

2. Данные в соответствующих столбцах объединяемых таблиц должны иметь совместимые типы. Например, символьный (строковый) типы char и varchar совместимы, а числовой строковый типы – нет

Пересечение наборов записей (intersect)

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

Синтаксис: запрос1 intersect запрос2;

В результирующей таблице остаются только отличающиеся записи.

Примечание! В операторах union и intersect можно использовать corresponding. В этих случаях исходные наборы данных в таблицах могут быть несовместимы, но соответствующие столбцы должны иметь одинаковый тип и длину.

Пример: система 1 и система 2. Требуется получить список компонентов Входящие одновременно в эти обе таблицы.

Select *from Система1

Intersect

Select *from система2;

Вычитание наборов записей (except)

Синтаксис: запрос1 except запрос2;

С помощью этого оператора из первой таблицы удаляются записи входящих во вторую таблицу. Здесь также можно использовать

Пример: таблицы Клиенты и Контакты

Необходимо узнать все ли клиенты содержаться в списке контактов. Указанные таблицы имеют однотипные столбцы имя и адрес

Select* from клиенты

Except*from контакты;

ОПЕРАЦИИ СОЕДИНЕНИЯ

(Join)

Естественные соединения

(natural join)

Пусть в БД имеются следующие 2 таблицы:

Продажи (ID_товара, количество, ID_клиента);

Клиенты (ID_клиента, Имя, Телефон)

Декартово произведение этих таблиц получается с помощью следующего запроса:

select *from продажи, Клиенты;

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

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

From Продажи, клиенты

Where Продажи.ID_клиента=Контакты.ID_клиенты;

Эквивалентный запрос с использованием оператора natural join

Select Продажи.*, Клиенты.Имя, Клиенты.Телефон

From Продажи Natural join клиенты;

Примечание! В Access оператор natural join не поддерживается, вместо него используется используется оператор inner join (внутреннее соединение), on (при), за которым следует условие отбора.

УСЛОВНОЕ СОЕДИНЕНИЕ

(join…on)

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

Пусть в БД имеются 2 таблицы

Продажи (ID_товара, Кол-во, ID_клиента);

Клиенты (ID_клиента, Имя, Телефон)
Тогда эти таблицы можно соединить используя следующие запросы: select *from Продажи JOIN Клиенты

On (продажи.ID_клиента)=Клиенты.ID_клиента)

And (продажи.колличество>50);

СОЕДИНЕНИЕ ПО ИМЕНАМ СТОЛБЦОВ

(join…using)

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

Эквивалентный запрос можно выполнить иначе: select* from Болты, Гайки

Where (болты.Тип=Гайки.Тип) and (Болты.Кол-во=гайки.Кол-во);

Примечание! В access оператора join…using нет, вместо него используется оператор inner join…on. Тогда запрос в access записывается так : select* from болты inner join гайки

On (болты.Тип=Гайки. Тип) and (Болты.Кол-во=Гайки.Кол=во);

Внешние соединения

Все соединения таблиц рассмотрены до сих пор являлись внутренними. Во всех примерах можно было вместо ключевого слова join использовать ключевые слова inner join . Из таблицы, получаемой при внутреннем соединении, отбрасываются все записи, для которых нет соответствующих записей одновременно в обеих соединяемых таблицах.

При внешнем соединении такие несоответствующие записи сохраняются, в этом и заключается отличие внешнего соединения от внутреннего.

Левое внешнее соединение

(left outer join)

При левом внешних соединений не соответствующей записи, имеющийся в левой таблице, сохраняется в результирующей таблице, а имеющийся в правой – удаляется.

Пример: пусть в БД имеются свои таблицы

Предложения(ID_товара,Цена,Описание);

Склад (ID_товара, Кол-во);

Примечание! Ключевое слово outer отсутствует, вместо него используются слова left join.

ПРАВОЕ ВНЕШНЕЕ СОЕДИНЕНИЕ

Right outer join –тоже что и левое, только наоборот

ПОЛНОЕ ВНЕШНЕЕ СОЕДИНЕНИЕ

Full join. Полное соединение выполняет одновременно левое и правое внешнее соединение.

В общем случае в этой БД могут быть:

- представительство без отделов;

- отделы, не входящие не в одно представительство

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

Select*

From представительство full join отделы

On (представительство.ID_пр=Отделы.ID_пр)

Full join Сотрудники

On (отделы.ID_отд=Сотрудники.ID_отд)

Транзакция

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

Транзакция состоит из любых операторов SQL, которые могут изменить БД.

Commit – завершение выполнение транзакции. Выполнение всех операторов транзакции проходит последовательно в едином блоке.

Rollback – откат. Происходит отмена действия всех операторов транзакции, и БД возвращается в исходное состояние, в котором БД находилась до начала транзакции.

Savepoint – контрольная точка. Контрольные промежуточные точки, сохраняющие состояние БД в них.

[i]

в 201 аудитории

5.04

12.04

26.04

Кренке Базы данных

БД

r1, r2, r3 – три таблицы

ФИО	Дисциплина	Оценка
Петров	БД
Сидоров	БД
Миронов	БД
Степанова	БД
Крылова	БД
Сидоров	Теория информации
Степанова	Теория информации
Крылова	Теория информации
Миронов	Теория информации
Владимиров	БД
Трофимов	Сети
Иванова	Сети
Уткина	Сети
Владимиров	Английский
Трофимов	Английский
Иванова	Английский
Петров	Английский

ФИО	Группа
Петров
Сидоров
Миронов
Крылова
Степанова
Владимиров
Трофимов
Иванова
Уткина