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

Введение в реляционные СУБД и программирование на SQL

Курс лекций для студентов ВМК

Казань 2002

© Н.Р.Бухараев, доцент, к. ф.-м. н., Казанский государственный университет

Факультет вычислительной математики и кибернетики

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

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

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

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

Напомним, что декартовым произведением T₁´T₂´…´T_n множеств T₁,T₂,…,T_n называется множество всех кортежей длины n (или, попросту, n-ок)

T₁´T₂´…´T_n =_def {<t_1,t_2,…, t_n>: " i Î 1..n (t_i Î T_i )},

а n-арным отношением (типа T₁´T₂´…´T_n) - некоторое множество кортежей R, R Ì T₁´T₂´…´T_n , т.е. любое подмножество некоторого декартова произведения. Обычно в математике отношение идентифицируют с некоторым свойством кортежей (пар, троек и т.д.) и отождествляют с предикатами (булевскими функциями):

R(t_1,t_2,…, t_n )=true » <t_1,t_2,…, t_n >Î R » "элементы t_1,t_2,…, t_n обладают (связаны) свойством R".

Наоборот, с каждой n-местной функцией f мы привыкли отождествлять отношение {<x_1,x_2,…, x_n, y>: <x_1,x_2,…, x_n> Î Dom(f) , y=f(x_1,x_2,…, x_n)Î Val(f)} - графиком функции f. Таким образом, с формальной стороны, языки теории функций и теории отношений равномощны как языки описаний. Содержательно же, практически - это существенно разные точки зрения; в том числе, с точки зрения практики математической - так, центральный и труднейший для математики вопрос - решение уравнений можно трактовать как переход от отношения к функции (или системе функций). Например, от отношения ax²+bx+c=0 к системе x_1,2=(-b+/-√(b²-ac))/2a). Фундаментальная содержательная разница между отношениями и функциями – это разница между многозначностью и однозначностью. Не удивительно поэтому, что функции воспринимается нами обычно как более простое понятие, по сравнению с отношениями.

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

В данном случае – некоторой (не обязательно - взаимно-однозначной) функцией именования (обозначения, “называния”) типов Meaning. Пусть Val(f)={T₁,T₂,…, T_n}. Формально, именованное декартово произведение ´Meaning=T₁´T₂´…´T_n(Meaning) типов T₁,T₂,…, T_n относительно функции именования Meaning есть класс всех функций выбора f на множестве имен этих типов Names=DOM(Meaning) – т.е. всех функций таких, что

" nÎ Names (f(n) Î Meaning(n))

Именованное отношение, или таблица, есть произвольное подмножество ´Meaning.

Хотя далее мы предполагаем функцию именования явно заданной контекстом и используем для именованного декартового произведения то же обозначение, что и для классического, просим читателя быть внимательным. В быту, чаще всего, мы не различаем имена и значения, что нередко – и в быту и, особенно, в программировании – приводит к большим недоразумениям. (Так, например – верно ли, что Маша состоит из 4 букв?)

Классические языки описания предикатов (отношений) - математическая логика (соответственно, теория множеств). Так, связь между людьми и домами можно выразить в виде предиката Живет: tЛюди ´ tДома à Boolean, Живет(x,y)=true » <x,y> Î Живет » " x живет в доме y". В программировании популярен более бедный, но и более наглядный язык диаграмм "сущность-связь", или ER-диаграмм (от англ. Entity - цельность, сущность и Relations - отношение, связь).

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

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

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

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

Графическое отражение факта "Иванов, 19 лет и Петров, 21 год, живут по адресу Казань, ул. Большая, 12, а Сидоров, 33 лет живет по адресу Нижнекамск, улица Зеленая, 24" или, в более традиционной математической записи: Живет à

{ <<Иванов, 19>, <Казань, Большая,12> >,

<<Петров, 21>, <Казань, Большая, 12> >,

< <Сидоров, 33>, <Нижнекамск, Зеленая, 24>>}

(для краткости мы, в ущерб точности, опустили именование вида

{<Люди à <Фамилия àИванов, Возраст à19>, Домаà <Город à Казань, Улица à Большая, Номер à12>,….)

В терминологии СУБД, именованное n-арное отношение Тпринято называтьтаблицей (table), составляющие его кортежи-n-ки строками или записями (record), а их имена - столбцами или полями (field) записи.

Отметьте - множество всех состояний каждой таблицы состоит из всех отношений одного типа, т.е. подмножеств одного фиксированного в ходе проектирования декартового произведения. Таблицы - динамический тип «по строкам», т.е. могут содержать переменное число записей, но не «по столбцам», поскольку число и типы полей фиксированы в процессе проектирования БД.

Основной целью использования БД является ответы на запросы пользователей, т.е. получение интересующей их информации – не только непосредственно физически хранящейся в БД, так и логически из нее выводимой.

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

Примеры запросов - "По какому адресу живет Иванов 19 лет?", "Сколько человек живут на данной улице?", "Кто самый старший в данном доме?" и т.п.

С точки зрения математики, ответ на запрос есть вывод решения некоторого класса предикатных уравнений - например, Живет(<Иванов, 19>,x)=true - посредством некоторого заданного класса эквивалентных преобразований. С преобразованиями классического в СУБД классов – алгеброй отношений Кодда – мы познакомимся позже.