Реляционные базы данных
Большинство современных промышленных баз данных являются реляционными -
данные в них представляют конечные отношения (relations), которые хранятся в таблицах. Схема отношения R(A1,A2, ..., An) включает имя отношения R и список
его атрибутов A1,A2, ..., An. Вообще говоря, атрибуты в схеме отношения считаются
неупорядоченными, т.е. являются не списком, а множеством. Но мы будем считать, что их
порядок в схеме является "стандартным".
Для каждого атрибута Ai определено множество dom(Ai)
его допустимых значений. Схема базы данных состоит из перечня схем отношений, входящих
в эту базу. В приложениях отношения чаще называют таблицами, их атрибуты - столбцами,
строки таблиц - кортежами или записями, а их элементы - полями.
В каждый момент времени состояние базы данных (ее экземпляр) - это набор (конечных) таблиц
имеющих соответствующие
схемы.
Пример 8.1.
Пусть, например, база данных со сведениями о сотрудниках некоторой организации
имеет схему: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад),
Комнаты(НомерСотрудника, Этаж, НомерКомнаты). Рассмотрим некоторый экземпляр
этой базы данных.
Сотрудники
| Номер
| ФИО
| Отдел
| Должность
| Оклад
|
|---|
| 1 |
Иванов А.А. |
торговый |
менеджер |
7000 |
| 2 |
Сидоров Н.П. |
плановый |
экономист |
5000 |
| 3 |
Сидорова М.И. |
торговый |
зав.складом |
6000 |
| 4 |
Ольгина Н.А. |
плановый |
экономист |
5500 |
| 5 |
Горев С.В. |
плановый |
зав.отделом |
10000 |
Комнаты
| НомерСотрудника
| Этаж
| НомерКомнаты
|
|---|
| 3 |
2 |
17 |
| 1 |
2 |
17 |
| 7 |
2 |
18 |
| 5 |
3 |
7 |
| 2 |
3 |
27 |
С точки зрения логики предикатов, этот экземпляр не что иное, как некоторая конечная система сигнатуры $$\Sigma _{2}=\{ Сотрудники^{(5)}, Комнаты^{(3)}\}$$ с основным множеством, включающим строки и числа из таблиц. Первая из приведенных таблиц задает интерпретацию предиката Сотрудники(5), а вторая - интерпретацию предиката Комнаты(3).
Каждому отношению базы данных со схемой R(A1, ..., An) мы сопоставим n -местный предикат с тем же именем и n одноместных предикатов Ai(x) (i=1, ..., n), выражающих принадлежность объекта x области dom(Ai) допустимых значений атрибута Ai. Следовательно, кортеж (a1, ... , an) принадлежит отношению R тогда и только тогда,
когда истинна формула $$A_{1}(a_{1}) \wedge \dots \wedge A_{n}(a_{n}) \wedge R(a_{1}, \dots , a_{n})$$.
Множество таких предикатов для всех отношений базы данных и стандартных отношений,
определенных на областях ее атрибутов (обычно это отношения равенства и порядка: =, <, <=, >, >= ), образуют сингатуру базы данных.
Например, для приведенного выше отношения Сотрудники(5) предикаты-свойства соответствующих областей значений могут быть заданы следующим образом:
$$Номер(x) \Leftrightarrow x$$ - целое число,
$$ФИО(x) \Leftrightarrow x$$ - строка символов длины <= 30,
$$Отдел(x) \} \Leftrightarrow x \in \{ торговый, плановый, производственный\}$$,
$$Должность(x) \Leftrightarrow x$$ - строка символов длины <= 80,
$$Оклад(x) \Leftrightarrow x$$ - целое число в интервале от 1000 до 100 000.
Каждый кортеж отношения Сотрудники удовлетворяет формуле $$Сотрудники(n, f, o, d, z) \wedge Номер(n) \wedge ФИО(f) \wedge Отдел(o) \wedge Должность(d) \wedge Оклад(z)$$.
Ниже мы будем просто писать R(a1, ... , an), подразумевая, что значения ai
входят в соответствующие области dom(Ai). Каждая формула $$\Phi (x_{1}, \dots , x_{k})$$
со свободными переменными x1, ... , xk
в сигнатуре базы данных определяет множество состояний, т.е. наборов значений
ее свободных переменных, на которых она истинна. Такое множество наборов можно рассматривать
как множество кортежей, которые входят в новое отношение $$P_{\Phi } ^{(k)}$$, определяемое формулой $$\Phi.$$
Например, формула
$$\Phi( k, f) = \exists n \exists d \exists z \exists e ( Сотрудники(n, f, o, d, z) \wedge
Комнаты(n, e, k) \wedge \\ \wedge (o ='плановый')$$
задает отношение $$P_{\Phi }^{(2)}$$, определяющее список комнат сотрудников планового отдела:
| ФИО
| НомерКомнаты
|
|---|
| Сидоров Н.П. |
27 |
| Горев С.В. |
7 |
Отметим, что для конечных систем поиск значений свободных переменных формул логики предикатов, при которых они выполняются, и проверка истинности замкнутых формул производятся эффективно.
Реляционная алгебра
Для манипуляции отношениями Коддом в 1970 г. был предложен набор реляционных операторов,
позволяющих по одним отношениям получать другие. Каждый такой оператор является функцией
(вообще говоря, частичной), аргументами и значениями которой являются отношения.
Из базовых реляционных операторов можно с помощью суперпозиции образовывать сложные термы.
Совокупность получаемых таким образом операций над отношениями называется реляционной алгеброй.
В этом разделе мы рассмотрим семь основных реляционных операторов, введенных Коддом в качестве базиса реляционной алгебры, и покажем, как они выражаются в терминах логики предикатов.
Теоретико-множественные операции
Первую группу реляционных операторов представляют теоретико-множественные операции:
Объединение
Пересечение
Вычитание
Декартово произведение
В лекции 1 мы рассматривали все эти операции для множеств.
Особенности их использования в реляционной алгебре состоят в том, что
объединение, пересечение и вычитание применяются к отношениям, имеющим
одно и то же множество одинаково упорядоченных атрибутов.
Пусть имеются два таких отношения R(A1, ..., An) и S(A1, ..., An). Тогда результат их объединенния - это отношение $$P_{1}= R \cup S$$, содержащее все кортежи отношения R и
все кортежи отношения S (кортежи, содержащиеся и в R, и в S, входят в P
в одном экземпляре). Это отношение представляется формулой $$P_{1}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \vee S(x_{1}, \dots , x_{n})$$.
Результат пересечения - это отношение P2 = R \cap S, которое содержит кортежи, входящие и в R и
в S. Оно представляется формулой $$P_{2}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \wedge S(x_{1}, \dots , x_{n})$$.
Результат разности P3= R - S включает кортежи из R, не входящие в S. Это отношение представляется формулой $$P_{3}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \wedge \neg S(x_{1}, \dots , x_{n})$$.
Декартово произведение P4= R x S отношений R(A1, ..., An) и S(B1, ..., Bm) содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S. Список атрибутов P4 включает все атрибуты отношений R и S: (A1, ..., An, B1, ..., Bm).
Если у R и S имеются общие атрибуты, то они переименовываются. Обычно перед
именем атрибута общего атрибута Ai=Bj
помещается через точку имя его отношения, R.Ai и S.Bj.
Результат декартового произведения задается формулой $$P_{4}(x_{1}, \dots , x_{n}, y_{1}, \dots , y_{m}) = R(x_{1}, \dots , x_{n}) \wedge S(y_{1}, \dots , y_{m})$$
(мы предполагаем, что все переменные xi и yj разные).
Специальные реляционные операторы
К специальным реляционным операторам относятся:
Выбор
Проекция
Соединение
Деление
Оператор выбора, примененный к отношению R(A1, ..., An),
возвращает новое отношение P с тем же набором атрибутов, кортежи которого
составляют подмножество кортежей отношения R, удовлетворяющих некоторому
условию C. Это записывается как $$P = \sigma _{C}(R)$$. Условие C представляет из себя булевскую
формулу, которая построена из элементарных условий, включающих имена атрибутов R
и константы. Примерами элементарных условий являются равенства вида Ai = Aj, Ai=a
и неравенства вида Ai <= Aj, Ai <= a, Ai >= a.
Тогда отношение P задается формулой $$P(x_{1}, \dots , x_{n}) = R(x_{1}, \dots , x_{n}) \wedge C'$$, где формула C' получена
из условия C заменой имен атрибутов Ai на имена соответствующих переменных xi.
Например, оператору выбора $$\sigma _{оклад> 6000}(Сотрудники)$$, выбирающему сотрудников с окладом
свыше 6000,
соответствует формула $$\Phi (n, f, o, d, z) = Сотрудники(n, f, o, d, z) \wedge (z > 6000)$$,
задающая отношение $$P_{\Phi }$$:
| Номер
| ФИО
| Отдел
| Должность
| Оклад
|
|---|
| 1 |
Иванов А.А. |
торговый |
менеджер |
7000 |
| 5 |
Горев С.В. |
плановый |
зав.отделом |
10000 |
Оператор проекции, примененный к отношению R(A1, ..., An), возвращает
все кортежи этого отношения, из которых удалены значения атрибутов, не перечисленных
в списке параметров этой операции. Отношение P, являющееся проекцией R на подмножество атрибутов $$X = \{A_{i_1}, \ldots, A_{i_k} \}$$, записывается как $$P = \pi _{X}(R)$$.
Пусть $$\{A_1, \ldots, A_n \} \setminus X= \{A_{j_1},\ldots , A_{j_{n-k}}\}$$ - это атрибуты отношения, не попавшие в X. Тогда проекция
задается формулой $$P(x_{i_1}, \ldots, x_{i_k}) =
\exists x_{j_1} \ldots \exists x_{j_{n-k}}R(x_1, \ldots, x_n)$$.
Например, оператору проекции $$\pi _{ФИО, оклад}(Сотрудники)$$,
составляющему список окладов сотрудников,
соответствует формула $$\psi ( f, z) = \exists n \exists o \exists d Сотрудники(n, f, o, d, z)$$, задающая
двуместное отношение $$P_{\psi }$$:
| ФИО
| Оклад
|
|---|
| Иванов А.А. |
7000 |
| Сидоров Н.П. |
5000 |
| Сидорова М.И. |
6000 |
| Ольгина Н.А. |
5500 |
| Горев С.В. |
10000 |
Оператор соединения применяется к двум отношениям и позволяет
соединять попарно их кортежи, удовлетворяющие определенным условиям.
В реляционной алгебре он представлен в нескольких формах.
Пусть R и S - это отношения со схемами R(A1, ..., An, B1, ..., Bm) и S(B1, ..., Bm, C1, ..., Ck) с общими атрибутами B1, ..., Bm.
Тогда естественное соединение $$P= R \Join S$$ отношений R и S
содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S. При этом соединяются
лишь пары кортежей $$r \in R$$ и $$s \in S$$, имеющих одинаковые значения всех общих атрибутов B1, ..., Bm. Так как значения общих атрибутов совпадают они входят
в схему P по одному разу, т.е. P имеет схему P(A1, ..., An, B1, ..., Bm, C1, ..., Ck).
Нетрудно понять, что естественному соединению соответствует формула $$P(x_{1}, \dots , y_{1}, \dots , y_{m}, z_{1}, \dots , z_{k})= R(x_{1}, \dots , y_{1}, \dots , y_{m}) \wedge S(y_{1}, \dots , y_{m}, z_{1}, \dots , z_{k})$$.
Пусть в дополнение к отношениям Сотрудники и Комнаты в базу данных входит отношение Оборудование:
Оборудование
| Этаж
| НомерКомнаты
| Название
|
|---|
| 2 |
17 |
компьютер |
| 2 |
17 |
принтер |
| 3 |
7 |
ксерокс |
| 3 |
25 |
принтер |
Тогда отношение $$Доступ=Комнаты \Join Оборудование$$
определяет доступность
тех или иных аппаратов сотрудникам в их комнатах. Оно имеет схему Доступ (НомерСотрудника, Этаж, НомерКомнаты, Название) и представлено в следующей таблице:
Доступ
| НомерСотрудника
| Этаж
| НомерКомнаты
| Название
|
|---|
| 3 |
2 |
17 |
компьютер |
| 3 |
2 |
17 |
принтер |
| 1 |
2 |
17 |
компьютер |
| 1 |
2 |
17 |
принтер |
| 5 |
3 |
7 |
ксерокс |
Здесь соединение производится по двум общим атрибута м Этаж и НомерКомнаты. При этом в соединение не попали сведения о сотрудниках с номерами 2 и 7, в комнатах которых нет оборудования, и о принтере в комнате 25, так как в
ней нет сотрудников. Соответствующая формула имеет вид: $$Доступ(n, e, k, o) = Комнаты(n, e, k) \wedge Оборудование(e, k, o)$$.
Другой вариант оператора соединения - тета-соединение $$P_1= R \Join_C S$$ отношений R и S
содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S, удовлетворяющими
условию C. Синтаксис этого условия такой же, как и у оператора выбора. Так как
в C могут входить не только равенства атрибутов, то атрибуты R и S с одинаковыми именами
входят в схему P1 дважды (обычно, как и в случае декартова произведения,
перед ними помещается через точку имя отношения ).
Оператор тета-соединения выражается через операторы выбора и декартового произведения: $$P_1= R \Join_C S = \sigma_C(R \times S)$$. Ему соответствует формула $$P_{1}(x_{1},\dots , x_{n}, y_{1}, \dots , y_{m}, y_{1}', \dots , y_{m}', z_{1},\dots , z_{k})=R(x_{1},\dots , x_{n}, y_{1}, \dots , y_{m}) \wedge S(y_{1}', \dots , y_{m}', z_{1},\dots , z_{k}) \wedge C'$$,
в которой C' - это формула C, где вместо имен атрибутов подставлены имена соответствующих
переменных.
Операторы реляционной алгебры можно соединять в сложные выражения, позволяющие выражать
необходимые пользователям запросы. Например, чтобы получить список фамилий сотрудников с
доступным каждому из них оборудованием, можно использовать выражение
$$F=\pi_{ФИО, Название}(Сотрудники~ \Join_{Номер =НомерСотрудника}~Доступ)=\\ = \pi_{ФИО, Название}
(Сотрудники\Join_{Номер =НомерСотрудника}\\( Комнаты \Join Оборудование)).$$
Результат его вычисления представлен в следующей таблице:
| ФИО
| Название
|
|---|
| Иванов А.А. |
компьютер |
| Иванов А.А. |
принтер |
| Сидорова М.И |
компьютер |
| Сидорова М.И |
принтер |
| Горев С.В. |
ксерокс |
Ее строки соответствуют парам значений переменных f,c, на которых истинна формула $$F(f,c) = \exists n \exists o \exists d \exists z \exists e \exists k (Сотрудники(n,f,o,d,z)\wedge Комнаты(n, e, k) \wedge Оборудование( e, k, c)$$.
Запросы
Пользователи извлекают информацию из баз данных с помощью запросов. Реляционная алгебра позволяет формулировать запросы в виде соответствующих выражений.
Однако их синтаксис не очень удобен для непрофессиональных пользователей. Поэтому
современные системы управления базами данных используют языки с более
простым и понятным синтаксисом.
Одним из самых популярных таких языков
является язык SQL (Structured Query Language - Структурный Язык Запросов). Сейчас
он служит стандартным языком запросов
для всех промышленных баз данных. Мы опишем здесь лишь простую форму основного
оператора этого языка SELECT (ВЫБРАТЬ). Она имеет вид:
SELECT <список полей (атрибутов)>
FROM <список таблиц>
WHERE <условия выбора>,
где <список полей ( атрибутов )> - список тех полей (или атрибутов ) таблиц, значения которых
будут входить в результаты запроса, <список таблиц> - список таблиц, из которых берутся
значения полей (если некоторые из них имеют поля с одинаковыми именами, то их именуют
как <имя таблицы>.<имя поля>), <условия выбора> - условия, которым должны удовлетворять
выбираемые значения полей, они представляют из себя бескванторную формулу, построенную из
атомных формул, в которых логические знаки $$\neg , \wedge , \vee$$ заменены на их английские
аналоги NOT, AND, OR, соответственно. В качестве переменных используются имена полей,
в качестве предикатов для числовых полей используются отношения порядка: >, $$\ge,$$ <, <=. В термах для числовых полей можно применять арифметические функции +, -, *, /. В термах для полей других типов обычно бывает можно использовать некоторый набор
стандартных функций соответствующих типов.
Пусть, например, мы хотим получить для базы данных из примера 8.5 список фамилий всех сотрудников,
работающих на 2-ом этаже. Соответствующий запрос выглядит так:
SELECT ФИО
FROM Сотрудники, Комнаты
WHERE Номер = НомерСотрудника AND Этаж = 2.
Нетрудно построить формулу логики предикатов, реализующую этот запрос:
$$\varphi_1=\exists Номер \existsОтдел \exists Должность \exists Оклад \exists НомерСотрудника \exists Этаж \\
\exists НомерКомнаты [ (Сотрудники(Номер, ФИО, Отдел, Должность, Оклад)\wedge \\
\wedge Комнаты(НомерСотрудника, Этаж, НомерКомнаты) ) \\ \wedge
(( Номер = НомерСотрудника ) \wedge (Этаж = 2))].$$
В качестве переменных в этой формуле используются имена полей ( атрибутов ) таблиц.
Свободными переменными являются выбираемые поля (в списке после SELECT ). Все остальные
переменные связаны кванторами существования в кванторной приставке. Матрица формулы состоит
из конъюнкции двух формул: первая представляет собой конъюнкцию предикатов-таблиц,
а вторая - это формула из условий выбора. Построенная таким образом формула
определяет множество состояний, на которых она истинна, а каждое из этих
состяний задает набор значений свободных переменных формулы, т.е. тех полей,
о которых задан запрос. Этот набор и является ответом на запрос (результатом запроса).
В нашем случае, $$\varphi _{1}$$ истинна на состояниях со значениями ФИО Иванов А.А
и Сидорова М.И., которые и являются ответом на исходный запрос.
Рассмотрим еще один пример. Пусть необходимо получить список сотрудников планового
отдела и комнат, в которых они трудятся. Запрос на SQL выглядит так:
SELECT ФИО, НомерКомнаты
FROM Сотрудники, Комнаты
WHERE Номер = НомерСотрудника AND Отдел = "плановый".
По описанным выше правилам построим формулу логики предикатов, реализующую этот запрос.
При этом заменим имена связанных переменных более короткими.
$$\varphi_2=\exists x_1\ \exists x_2\ \exists x_3\ \exists x_4 \ \exists x_5\ \exists x_6[(Сотрудники\\(x_1, ФИО, x_2, x_3, x_4)\ \wedge
Комнаты(x_5, x_6, НомерКомнаты) )\wedge\\
((x_1 = x_5)\ \wedge\ (x_2 =\ "плановый"))].$$
Эта формула истинна на состояниях со следующими парами свободных переменных (ФИО, НомерКомнаты) (мы представили их в виде новой таблицы):
| ФИО
| НомерКомнаты
|
|---|
| Сидоров Н.П. |
27 |
| Горев С.В. |
7 |
Таким образом, описанные выше SQL-запросы являются ни чем иным,
как "синтаксическим сахаром",
за которым скрываются формулы логики предикатов весьма специального вида (такие
формулы называются $$\exists$$ -формулами). Имеются и более сложные формы SQL-запросов,
которым соответствуют формулы логики предикатов более общего вида. Но в любом случае
SQL-запросы не выходят за рамки логики предикатов.
Ограничения целостности
Состояние базы данных постоянно меняется. В нее добавляются новые записи,
изменяются и удаляются старые. При этом нужно, чтобы во всех модификациях
состояние оставалось корректным
(например, для каждого сотрудника имелась лишь одна запись в таблице Сотрудники). Ограничение целостности - это условие, задаваемое для схемы базы данных,
которое ограничивает множество возможных состояний базы данных.
Вот типичные виды ограничений целостности:
ограничение на ключи: в таблице не должно быть двух строк с одинаковым значением некоторого поля (оно назывется ключом). В общем виде ограничение на ключи утверждает, что в таблице не должно быть двух строк с одинаковыми значениями нескольких заданных полей (такой набор полей также называется ключом таблицы);
ограничение на ссылки : значение некоторого поля в одной таблице должно быть среди значений некоторого поля в другой таблице. Это ограничение не позволит удалить из второй таблицы запись, на которую имеется ссылка из первой таблицы;
ограничение на значение : значение некоторого поля в таблице должно удовлетворять заданному условию (принадлежать определенному интервалу, быть больше (меньше) заданного числа, быть строкой длины не больше (не меньше) заданной, быть строкой, удовлетворяющей некоторому образцу и т.п.).
Современные системы управления базами данных позволяют задавать такие
ограничения при конструировании базы данных, а затем автоматически поддерживают
их выполнение, не давая пользователям производить модификации, которые могут
эти ограничения нарушить.
С точки зрения логики предикатов, ограничение целостности - это замкнутая
формула, которая должна быть истинна на допустимых состояниях базы данных.
Рассмотрим, как можно задать ограничения целостности указанных видов для
нашей базы данных (Сотрудники, Комнаты).
В таблице Сотрудники ключом является поле Номер:
$$\Phi_1=\forall Номер\ \forall x\ \forall y\ \forall z\ \forall v\ \forall x_1\ \forall y_1\ \forall z_1\ \forall v_1 [(Сотрудники\\( Номер, x, y, z, v) \wedge \ Сотрудники( Номер, x_1, y_1, z_1, v_1)) \rightarrow \\( (x=x_1)\ \wedge\ (y = y_1)\ \wedge\
(z = z_1)\ \wedge\ (v = v_1))].$$
Каждый сотрудник, для которого определена комната в таблице Комнаты, должен присутствовать в таблице Сотрудники:
$$\Phi_2= \forall НомерСотрудника\ \forall x\ \forall y [ Комнаты\\(НомерСотрудника, x, y) \rightarrow \\
\exists z\ \exists u\ \exists v\ \exists w ( Сотрудники( Номер, z, u, v, w)\ \wedge \ ( Номер= \\
НомерСотрудника))].$$
Оклад каждого сотрудника должен лежать в интервале (1000, 25000):
$$\Phi_3=\forall x\ \forall y\ \forall z\ \forall v\ \forall Оклад\ (Сотрудники( x, y, z, v, Оклад)\ \rightarrow\\ \indent ( (1000 < Оклад)\ \wedge\ ( Оклад < 25000))).$$
Задачи
Задача 8.1. Для определенной выше базы данных с отношениями (Сотрудники, Комнаты, Название) построить выражение реляционной алгебры,
задающее список фамилий сотрудников, в комнатах которых нет никакого оборудования.
Найти формулу логики предикатов, определяющую то же отношение.
Задача 8.2. Пусть имеются отношения R и S со схемами R(A1, ..., An, B1, ..., Bm) и S(B1, ..., Bm), соответственно. Частным $$R \div S$$ от деления отношения R на отношение S называется отношение с атрибутами A1, ..., An , каждый кортеж которого t в соединении с любым кортежом s отношения S входит в R.
Постройте выражение реляционной алгебры, эквивалентное $$R \div S$$,
и формулу логики предикатов, выражающую это отношение.
Задача 8.3. Напишите SQL-запросы и соответствующие формулы для получения
информации из базы данных (Сотрудники, Комнаты) из примера 8.5
и получите ответы на эти запросы.
Найти всех сотрудников с окладом больше 5500.
Найти все отделы, в которых есть сотрудники с окладом > 8000.
Составить список должностей и получаемых по ним окладов.
Составить список сотрудников торгового отдела, получающих зарплату от 6000 до 6500 и работающих не на 3-ем этаже.
Составить список комнат, в которых есть сотрудники с окладом меньше 5500 или больше 7500.
Задача 8.4. Определите, какие из приведенных ограничений целостности $$\Phi _{1}, \Phi _{2}, \Phi _{3}$$ выполняются для приведенного выше состояния базы данных (Сотрудники, Комнаты).
Задача 8.5. Напишите формулы, выражающие следующие ограничения целостности для базы (Сотрудники, Комнаты), и определите, какие из них выполняются для приведенного выше ее состояния.
В таблице Комнаты набор полей (НомерСотрудника, Комната) является ключом.
Для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
Номера всех комнат на 2-ом этаже больше 10, но меньше 20, а номера всех комнат на 3-ем этаже больше 20.
Реляционные базы данных
Большинство современных промышленных баз данных являются реляционными -
данные в них представляют конечные отношения (relations), которые хранятся в таблицах. Схема отношения R(A1,A2, ..., An) включает имя отношения R и список
его атрибутов A1,A2, ..., An. Вообще говоря, атрибуты в схеме отношения считаются
неупорядоченными, т.е. являются не списком, а множеством. Но мы будем считать, что их
порядок в схеме является "стандартным".
Для каждого атрибута Ai определено множество dom(Ai)
его допустимых значений. Схема базы данных состоит из перечня схем отношений, входящих
в эту базу. В приложениях отношения чаще называют таблицами, их атрибуты - столбцами,
строки таблиц - кортежами или записями, а их элементы - полями.
В каждый момент времени состояние базы данных (ее экземпляр) - это набор (конечных) таблиц
имеющих соответствующие
схемы.
Пример 8.1.
Пусть, например, база данных со сведениями о сотрудниках некоторой организации
имеет схему: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад),
Комнаты(НомерСотрудника, Этаж, НомерКомнаты). Рассмотрим некоторый экземпляр
этой базы данных.
Сотрудники
| Номер
| ФИО
| Отдел
| Должность
| Оклад
|
|---|
| 1 |
Иванов А.А. |
торговый |
менеджер |
7000 |
| 2 |
Сидоров Н.П. |
плановый |
экономист |
5000 |
| 3 |
Сидорова М.И. |
торговый |
зав.складом |
6000 |
| 4 |
Ольгина Н.А. |
плановый |
экономист |
5500 |
| 5 |
Горев С.В. |
плановый |
зав.отделом |
10000 |
Комнаты
| НомерСотрудника
| Этаж
| НомерКомнаты
|
|---|
| 3 |
2 |
17 |
| 1 |
2 |
17 |
| 7 |
2 |
18 |
| 5 |
3 |
7 |
| 2 |
3 |
27 |
С точки зрения логики предикатов, этот экземпляр не что иное, как некоторая конечная система сигнатуры $$\Sigma _{2}=\{ Сотрудники^{(5)}, Комнаты^{(3)}\}$$ с основным множеством, включающим строки и числа из таблиц. Первая из приведенных таблиц задает интерпретацию предиката Сотрудники(5), а вторая - интерпретацию предиката Комнаты(3).
Каждому отношению базы данных со схемой R(A1, ..., An) мы сопоставим n -местный предикат с тем же именем и n одноместных предикатов Ai(x) (i=1, ..., n), выражающих принадлежность объекта x области dom(Ai) допустимых значений атрибута Ai. Следовательно, кортеж (a1, ... , an) принадлежит отношению R тогда и только тогда,
когда истинна формула $$A_{1}(a_{1}) \wedge \dots \wedge A_{n}(a_{n}) \wedge R(a_{1}, \dots , a_{n})$$.
Множество таких предикатов для всех отношений базы данных и стандартных отношений,
определенных на областях ее атрибутов (обычно это отношения равенства и порядка: =, <, <=, >, >= ), образуют сингатуру базы данных.
Например, для приведенного выше отношения Сотрудники(5) предикаты-свойства соответствующих областей значений могут быть заданы следующим образом:
$$Номер(x) \Leftrightarrow x$$ - целое число,
$$ФИО(x) \Leftrightarrow x$$ - строка символов длины <= 30,
$$Отдел(x) \} \Leftrightarrow x \in \{ торговый, плановый, производственный\}$$,
$$Должность(x) \Leftrightarrow x$$ - строка символов длины <= 80,
$$Оклад(x) \Leftrightarrow x$$ - целое число в интервале от 1000 до 100 000.
Каждый кортеж отношения Сотрудники удовлетворяет формуле $$Сотрудники(n, f, o, d, z) \wedge Номер(n) \wedge ФИО(f) \wedge Отдел(o) \wedge Должность(d) \wedge Оклад(z)$$.
Ниже мы будем просто писать R(a1, ... , an), подразумевая, что значения ai
входят в соответствующие области dom(Ai). Каждая формула $$\Phi (x_{1}, \dots , x_{k})$$
со свободными переменными x1, ... , xk
в сигнатуре базы данных определяет множество состояний, т.е. наборов значений
ее свободных переменных, на которых она истинна. Такое множество наборов можно рассматривать
как множество кортежей, которые входят в новое отношение $$P_{\Phi } ^{(k)}$$, определяемое формулой $$\Phi.$$
Например, формула
$$\Phi( k, f) = \exists n \exists d \exists z \exists e ( Сотрудники(n, f, o, d, z) \wedge
Комнаты(n, e, k) \wedge \\ \wedge (o ='плановый')$$
задает отношение $$P_{\Phi }^{(2)}$$, определяющее список комнат сотрудников планового отдела:
| ФИО
| НомерКомнаты
|
|---|
| Сидоров Н.П. |
27 |
| Горев С.В. |
7 |
Отметим, что для конечных систем поиск значений свободных переменных формул логики предикатов, при которых они выполняются, и проверка истинности замкнутых формул производятся эффективно.
Реляционная алгебра
Для манипуляции отношениями Коддом в 1970 г. был предложен набор реляционных операторов,
позволяющих по одним отношениям получать другие. Каждый такой оператор является функцией
(вообще говоря, частичной), аргументами и значениями которой являются отношения.
Из базовых реляционных операторов можно с помощью суперпозиции образовывать сложные термы.
Совокупность получаемых таким образом операций над отношениями называется реляционной алгеброй.
В этом разделе мы рассмотрим семь основных реляционных операторов, введенных Коддом в качестве базиса реляционной алгебры, и покажем, как они выражаются в терминах логики предикатов.
Теоретико-множественные операции
Первую группу реляционных операторов представляют теоретико-множественные операции:
Объединение
Пересечение
Вычитание
Декартово произведение
В лекции 1 мы рассматривали все эти операции для множеств.
Особенности их использования в реляционной алгебре состоят в том, что
объединение, пересечение и вычитание применяются к отношениям, имеющим
одно и то же множество одинаково упорядоченных атрибутов.
Пусть имеются два таких отношения R(A1, ..., An) и S(A1, ..., An). Тогда результат их объединенния - это отношение $$P_{1}= R \cup S$$, содержащее все кортежи отношения R и
все кортежи отношения S (кортежи, содержащиеся и в R, и в S, входят в P
в одном экземпляре). Это отношение представляется формулой $$P_{1}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \vee S(x_{1}, \dots , x_{n})$$.
Результат пересечения - это отношение P2 = R \cap S, которое содержит кортежи, входящие и в R и
в S. Оно представляется формулой $$P_{2}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \wedge S(x_{1}, \dots , x_{n})$$.
Результат разности P3= R - S включает кортежи из R, не входящие в S. Это отношение представляется формулой $$P_{3}(x_{1}, \dots , x_{n})= R(x_{1}, \dots , x_{n}) \wedge \neg S(x_{1}, \dots , x_{n})$$.
Декартово произведение P4= R x S отношений R(A1, ..., An) и S(B1, ..., Bm) содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S. Список атрибутов P4 включает все атрибуты отношений R и S: (A1, ..., An, B1, ..., Bm).
Если у R и S имеются общие атрибуты, то они переименовываются. Обычно перед
именем атрибута общего атрибута Ai=Bj
помещается через точку имя его отношения, R.Ai и S.Bj.
Результат декартового произведения задается формулой $$P_{4}(x_{1}, \dots , x_{n}, y_{1}, \dots , y_{m}) = R(x_{1}, \dots , x_{n}) \wedge S(y_{1}, \dots , y_{m})$$
(мы предполагаем, что все переменные xi и yj разные).
Специальные реляционные операторы
К специальным реляционным операторам относятся:
Выбор
Проекция
Соединение
Деление
Оператор выбора, примененный к отношению R(A1, ..., An),
возвращает новое отношение P с тем же набором атрибутов, кортежи которого
составляют подмножество кортежей отношения R, удовлетворяющих некоторому
условию C. Это записывается как $$P = \sigma _{C}(R)$$. Условие C представляет из себя булевскую
формулу, которая построена из элементарных условий, включающих имена атрибутов R
и константы. Примерами элементарных условий являются равенства вида Ai = Aj, Ai=a
и неравенства вида Ai <= Aj, Ai <= a, Ai >= a.
Тогда отношение P задается формулой $$P(x_{1}, \dots , x_{n}) = R(x_{1}, \dots , x_{n}) \wedge C'$$, где формула C' получена
из условия C заменой имен атрибутов Ai на имена соответствующих переменных xi.
Например, оператору выбора $$\sigma _{оклад> 6000}(Сотрудники)$$, выбирающему сотрудников с окладом
свыше 6000,
соответствует формула $$\Phi (n, f, o, d, z) = Сотрудники(n, f, o, d, z) \wedge (z > 6000)$$,
задающая отношение $$P_{\Phi }$$:
| Номер
| ФИО
| Отдел
| Должность
| Оклад
|
|---|
| 1 |
Иванов А.А. |
торговый |
менеджер |
7000 |
| 5 |
Горев С.В. |
плановый |
зав.отделом |
10000 |
Оператор проекции, примененный к отношению R(A1, ..., An), возвращает
все кортежи этого отношения, из которых удалены значения атрибутов, не перечисленных
в списке параметров этой операции. Отношение P, являющееся проекцией R на подмножество атрибутов $$X = \{A_{i_1}, \ldots, A_{i_k} \}$$, записывается как $$P = \pi _{X}(R)$$.
Пусть $$\{A_1, \ldots, A_n \} \setminus X= \{A_{j_1},\ldots , A_{j_{n-k}}\}$$ - это атрибуты отношения, не попавшие в X. Тогда проекция
задается формулой $$P(x_{i_1}, \ldots, x_{i_k}) =
\exists x_{j_1} \ldots \exists x_{j_{n-k}}R(x_1, \ldots, x_n)$$.
Например, оператору проекции $$\pi _{ФИО, оклад}(Сотрудники)$$,
составляющему список окладов сотрудников,
соответствует формула $$\psi ( f, z) = \exists n \exists o \exists d Сотрудники(n, f, o, d, z)$$, задающая
двуместное отношение $$P_{\psi }$$:
| ФИО
| Оклад
|
|---|
| Иванов А.А. |
7000 |
| Сидоров Н.П. |
5000 |
| Сидорова М.И. |
6000 |
| Ольгина Н.А. |
5500 |
| Горев С.В. |
10000 |
Оператор соединения применяется к двум отношениям и позволяет
соединять попарно их кортежи, удовлетворяющие определенным условиям.
В реляционной алгебре он представлен в нескольких формах.
Пусть R и S - это отношения со схемами R(A1, ..., An, B1, ..., Bm) и S(B1, ..., Bm, C1, ..., Ck) с общими атрибутами B1, ..., Bm.
Тогда естественное соединение $$P= R \Join S$$ отношений R и S
содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S. При этом соединяются
лишь пары кортежей $$r \in R$$ и $$s \in S$$, имеющих одинаковые значения всех общих атрибутов B1, ..., Bm. Так как значения общих атрибутов совпадают они входят
в схему P по одному разу, т.е. P имеет схему P(A1, ..., An, B1, ..., Bm, C1, ..., Ck).
Нетрудно понять, что естественному соединению соответствует формула $$P(x_{1}, \dots , y_{1}, \dots , y_{m}, z_{1}, \dots , z_{k})= R(x_{1}, \dots , y_{1}, \dots , y_{m}) \wedge S(y_{1}, \dots , y_{m}, z_{1}, \dots , z_{k})$$.
Пусть в дополнение к отношениям Сотрудники и Комнаты в базу данных входит отношение Оборудование:
Оборудование
| Этаж
| НомерКомнаты
| Название
|
|---|
| 2 |
17 |
компьютер |
| 2 |
17 |
принтер |
| 3 |
7 |
ксерокс |
| 3 |
25 |
принтер |
Тогда отношение $$Доступ=Комнаты \Join Оборудование$$
определяет доступность
тех или иных аппаратов сотрудникам в их комнатах. Оно имеет схему Доступ (НомерСотрудника, Этаж, НомерКомнаты, Название) и представлено в следующей таблице:
Доступ
| НомерСотрудника
| Этаж
| НомерКомнаты
| Название
|
|---|
| 3 |
2 |
17 |
компьютер |
| 3 |
2 |
17 |
принтер |
| 1 |
2 |
17 |
компьютер |
| 1 |
2 |
17 |
принтер |
| 5 |
3 |
7 |
ксерокс |
Здесь соединение производится по двум общим атрибута м Этаж и НомерКомнаты. При этом в соединение не попали сведения о сотрудниках с номерами 2 и 7, в комнатах которых нет оборудования, и о принтере в комнате 25, так как в
ней нет сотрудников. Соответствующая формула имеет вид: $$Доступ(n, e, k, o) = Комнаты(n, e, k) \wedge Оборудование(e, k, o)$$.
Другой вариант оператора соединения - тета-соединение $$P_1= R \Join_C S$$ отношений R и S
содержит кортежи, которые составлены из
кортежей отношения R, продолженных кортежами отношения S, удовлетворяющими
условию C. Синтаксис этого условия такой же, как и у оператора выбора. Так как
в C могут входить не только равенства атрибутов, то атрибуты R и S с одинаковыми именами
входят в схему P1 дважды (обычно, как и в случае декартова произведения,
перед ними помещается через точку имя отношения ).
Оператор тета-соединения выражается через операторы выбора и декартового произведения: $$P_1= R \Join_C S = \sigma_C(R \times S)$$. Ему соответствует формула $$P_{1}(x_{1},\dots , x_{n}, y_{1}, \dots , y_{m}, y_{1}', \dots , y_{m}', z_{1},\dots , z_{k})=R(x_{1},\dots , x_{n}, y_{1}, \dots , y_{m}) \wedge S(y_{1}', \dots , y_{m}', z_{1},\dots , z_{k}) \wedge C'$$,
в которой C' - это формула C, где вместо имен атрибутов подставлены имена соответствующих
переменных.
Операторы реляционной алгебры можно соединять в сложные выражения, позволяющие выражать
необходимые пользователям запросы. Например, чтобы получить список фамилий сотрудников с
доступным каждому из них оборудованием, можно использовать выражение
$$F=\pi_{ФИО, Название}(Сотрудники~ \Join_{Номер =НомерСотрудника}~Доступ)=\\ = \pi_{ФИО, Название}
(Сотрудники\Join_{Номер =НомерСотрудника}\\( Комнаты \Join Оборудование)).$$
Результат его вычисления представлен в следующей таблице:
| ФИО
| Название
|
|---|
| Иванов А.А. |
компьютер |
| Иванов А.А. |
принтер |
| Сидорова М.И |
компьютер |
| Сидорова М.И |
принтер |
| Горев С.В. |
ксерокс |
Ее строки соответствуют парам значений переменных f,c, на которых истинна формула $$F(f,c) = \exists n \exists o \exists d \exists z \exists e \exists k (Сотрудники(n,f,o,d,z)\wedge Комнаты(n, e, k) \wedge Оборудование( e, k, c)$$.
Запросы
Пользователи извлекают информацию из баз данных с помощью запросов. Реляционная алгебра позволяет формулировать запросы в виде соответствующих выражений.
Однако их синтаксис не очень удобен для непрофессиональных пользователей. Поэтому
современные системы управления базами данных используют языки с более
простым и понятным синтаксисом.
Одним из самых популярных таких языков
является язык SQL (Structured Query Language - Структурный Язык Запросов). Сейчас
он служит стандартным языком запросов
для всех промышленных баз данных. Мы опишем здесь лишь простую форму основного
оператора этого языка SELECT (ВЫБРАТЬ). Она имеет вид:
SELECT <список полей (атрибутов)>
FROM <список таблиц>
WHERE <условия выбора>,
где <список полей ( атрибутов )> - список тех полей (или атрибутов ) таблиц, значения которых
будут входить в результаты запроса, <список таблиц> - список таблиц, из которых берутся
значения полей (если некоторые из них имеют поля с одинаковыми именами, то их именуют
как <имя таблицы>.<имя поля>), <условия выбора> - условия, которым должны удовлетворять
выбираемые значения полей, они представляют из себя бескванторную формулу, построенную из
атомных формул, в которых логические знаки $$\neg , \wedge , \vee$$ заменены на их английские
аналоги NOT, AND, OR, соответственно. В качестве переменных используются имена полей,
в качестве предикатов для числовых полей используются отношения порядка: >, $$\ge,$$ <, <=. В термах для числовых полей можно применять арифметические функции +, -, *, /. В термах для полей других типов обычно бывает можно использовать некоторый набор
стандартных функций соответствующих типов.
Пусть, например, мы хотим получить для базы данных из примера 8.5 список фамилий всех сотрудников,
работающих на 2-ом этаже. Соответствующий запрос выглядит так:
SELECT ФИО
FROM Сотрудники, Комнаты
WHERE Номер = НомерСотрудника AND Этаж = 2.
Нетрудно построить формулу логики предикатов, реализующую этот запрос:
$$\varphi_1=\exists Номер \existsОтдел \exists Должность \exists Оклад \exists НомерСотрудника \exists Этаж \\
\exists НомерКомнаты [ (Сотрудники(Номер, ФИО, Отдел, Должность, Оклад)\wedge \\
\wedge Комнаты(НомерСотрудника, Этаж, НомерКомнаты) ) \\ \wedge
(( Номер = НомерСотрудника ) \wedge (Этаж = 2))].$$
В качестве переменных в этой формуле используются имена полей ( атрибутов ) таблиц.
Свободными переменными являются выбираемые поля (в списке после SELECT ). Все остальные
переменные связаны кванторами существования в кванторной приставке. Матрица формулы состоит
из конъюнкции двух формул: первая представляет собой конъюнкцию предикатов-таблиц,
а вторая - это формула из условий выбора. Построенная таким образом формула
определяет множество состояний, на которых она истинна, а каждое из этих
состяний задает набор значений свободных переменных формулы, т.е. тех полей,
о которых задан запрос. Этот набор и является ответом на запрос (результатом запроса).
В нашем случае, $$\varphi _{1}$$ истинна на состояниях со значениями ФИО Иванов А.А
и Сидорова М.И., которые и являются ответом на исходный запрос.
Рассмотрим еще один пример. Пусть необходимо получить список сотрудников планового
отдела и комнат, в которых они трудятся. Запрос на SQL выглядит так:
SELECT ФИО, НомерКомнаты
FROM Сотрудники, Комнаты
WHERE Номер = НомерСотрудника AND Отдел = "плановый".
По описанным выше правилам построим формулу логики предикатов, реализующую этот запрос.
При этом заменим имена связанных переменных более короткими.
$$\varphi_2=\exists x_1\ \exists x_2\ \exists x_3\ \exists x_4 \ \exists x_5\ \exists x_6[(Сотрудники\\(x_1, ФИО, x_2, x_3, x_4)\ \wedge
Комнаты(x_5, x_6, НомерКомнаты) )\wedge\\
((x_1 = x_5)\ \wedge\ (x_2 =\ "плановый"))].$$
Эта формула истинна на состояниях со следующими парами свободных переменных (ФИО, НомерКомнаты) (мы представили их в виде новой таблицы):
| ФИО
| НомерКомнаты
|
|---|
| Сидоров Н.П. |
27 |
| Горев С.В. |
7 |
Таким образом, описанные выше SQL-запросы являются ни чем иным,
как "синтаксическим сахаром",
за которым скрываются формулы логики предикатов весьма специального вида (такие
формулы называются $$\exists$$ -формулами). Имеются и более сложные формы SQL-запросов,
которым соответствуют формулы логики предикатов более общего вида. Но в любом случае
SQL-запросы не выходят за рамки логики предикатов.
Ограничения целостности
Состояние базы данных постоянно меняется. В нее добавляются новые записи,
изменяются и удаляются старые. При этом нужно, чтобы во всех модификациях
состояние оставалось корректным
(например, для каждого сотрудника имелась лишь одна запись в таблице Сотрудники). Ограничение целостности - это условие, задаваемое для схемы базы данных,
которое ограничивает множество возможных состояний базы данных.
Вот типичные виды ограничений целостности:
ограничение на ключи: в таблице не должно быть двух строк с одинаковым значением некоторого поля (оно назывется ключом). В общем виде ограничение на ключи утверждает, что в таблице не должно быть двух строк с одинаковыми значениями нескольких заданных полей (такой набор полей также называется ключом таблицы);
ограничение на ссылки : значение некоторого поля в одной таблице должно быть среди значений некоторого поля в другой таблице. Это ограничение не позволит удалить из второй таблицы запись, на которую имеется ссылка из первой таблицы;
ограничение на значение : значение некоторого поля в таблице должно удовлетворять заданному условию (принадлежать определенному интервалу, быть больше (меньше) заданного числа, быть строкой длины не больше (не меньше) заданной, быть строкой, удовлетворяющей некоторому образцу и т.п.).
Современные системы управления базами данных позволяют задавать такие
ограничения при конструировании базы данных, а затем автоматически поддерживают
их выполнение, не давая пользователям производить модификации, которые могут
эти ограничения нарушить.
С точки зрения логики предикатов, ограничение целостности - это замкнутая
формула, которая должна быть истинна на допустимых состояниях базы данных.
Рассмотрим, как можно задать ограничения целостности указанных видов для
нашей базы данных (Сотрудники, Комнаты).
В таблице Сотрудники ключом является поле Номер:
$$\Phi_1=\forall Номер\ \forall x\ \forall y\ \forall z\ \forall v\ \forall x_1\ \forall y_1\ \forall z_1\ \forall v_1 [(Сотрудники\\( Номер, x, y, z, v) \wedge \ Сотрудники( Номер, x_1, y_1, z_1, v_1)) \rightarrow \\( (x=x_1)\ \wedge\ (y = y_1)\ \wedge\
(z = z_1)\ \wedge\ (v = v_1))].$$
Каждый сотрудник, для которого определена комната в таблице Комнаты, должен присутствовать в таблице Сотрудники:
$$\Phi_2= \forall НомерСотрудника\ \forall x\ \forall y [ Комнаты\\(НомерСотрудника, x, y) \rightarrow \\
\exists z\ \exists u\ \exists v\ \exists w ( Сотрудники( Номер, z, u, v, w)\ \wedge \ ( Номер= \\
НомерСотрудника))].$$
Оклад каждого сотрудника должен лежать в интервале (1000, 25000):
$$\Phi_3=\forall x\ \forall y\ \forall z\ \forall v\ \forall Оклад\ (Сотрудники( x, y, z, v, Оклад)\ \rightarrow\\ \indent ( (1000 < Оклад)\ \wedge\ ( Оклад < 25000))).$$
Задачи
Задача 8.1. Для определенной выше базы данных с отношениями (Сотрудники, Комнаты, Название) построить выражение реляционной алгебры,
задающее список фамилий сотрудников, в комнатах которых нет никакого оборудования.
Найти формулу логики предикатов, определяющую то же отношение.
Задача 8.2. Пусть имеются отношения R и S со схемами R(A1, ..., An, B1, ..., Bm) и S(B1, ..., Bm), соответственно. Частным $$R \div S$$ от деления отношения R на отношение S называется отношение с атрибутами A1, ..., An , каждый кортеж которого t в соединении с любым кортежом s отношения S входит в R.
Постройте выражение реляционной алгебры, эквивалентное $$R \div S$$,
и формулу логики предикатов, выражающую это отношение.
Задача 8.3. Напишите SQL-запросы и соответствующие формулы для получения
информации из базы данных (Сотрудники, Комнаты) из примера 8.5
и получите ответы на эти запросы.
Найти всех сотрудников с окладом больше 5500.
Найти все отделы, в которых есть сотрудники с окладом > 8000.
Составить список должностей и получаемых по ним окладов.
Составить список сотрудников торгового отдела, получающих зарплату от 6000 до 6500 и работающих не на 3-ем этаже.
Составить список комнат, в которых есть сотрудники с окладом меньше 5500 или больше 7500.
Задача 8.4. Определите, какие из приведенных ограничений целостности $$\Phi _{1}, \Phi _{2}, \Phi _{3}$$ выполняются для приведенного выше состояния базы данных (Сотрудники, Комнаты).
Задача 8.5. Напишите формулы, выражающие следующие ограничения целостности для базы (Сотрудники, Комнаты), и определите, какие из них выполняются для приведенного выше ее состояния.
В таблице Комнаты набор полей (НомерСотрудника, Комната) является ключом.
Для каждого сотрудника из таблицы Сотрудники в таблице Комнаты определено его место работы.
Номера всех комнат на 2-ом этаже больше 10, но меньше 20, а номера всех комнат на 3-ем этаже больше 20.
