Указания методические для студентов специальности 2205, 0755 «Проектирование и технология эвс», «Комплексная информационная безопасность автоматизированных систем» ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра информационной безопасности электронно- вычислительных систем (КИБЭВС) Давыдова Е.М., Новгородова Н.А. БАЗЫ ДАННЫХ Методические указания для студентов специальности 2205, 0755 «Проектирование и технология ЭВС», «Комплексная информационная безопасность автоматизированных систем» 2005 СОДЕРЖАНИЕ 1. ВВЕДЕНИЕ В БАЗЫ ДАННЫХ.............................................................. 4 1.1. Информационные системы, их разновидности.............................. 4 1.2. Состав АИС........................................................................................ 11 1.3.Архитектура, предметная область..................................................... 12 2. КОНЦЕПТУАЛЬНОЕ ПРОЕКТИРОВАНИЕ....................................... 17 3. МОДЕЛИ ДАННЫХ................................................................................ 25 3.1.Понятие модели..................................................................................... 25 3.2. Иерархические модели........................................................................ 26 3.3. Сетевые модели.................................................................................... 29 3.4. Реляционные модели данных............................................................ 30 3.4.1. Реляционная алгебра..................................................................... 31 3.4.2. Реляционное исчисление.............................................................. 36 3.5. Объектно-ориентированные БД........................................................ 38 4. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ.............. 40 4.1. Выбор ключевых полей...................................................................... 40 4.2. Ссылочная целостность...................................................................... 43 4.3. Введение в нормализацию данных................................................... 43 Первая нормальная форма...................................................................... 44 Вторая нормальная форма...................................................................... 45 Третья нормальная форма...................................................................... 47 Нормальная форма Бойса-Кодда........................................................... 49 Четвертая нормальная форма................................................................. 50 Пятая нормальная форма........................................................................ 50 4.3.Как проектируют базы данных........................................................... 51 5. ЯЗЫК ФОРМИРОВАНИЯ ЗАПРОСОВ К БАЗЕ ДАНЫХ................ 52 5.1. Оператор выбора.................................................................................. 53 5.1.1. Определение критерия отбора данных........................................ 57 5.1.2. Сортировка результатов запроса................................................ 60 5.1.3. Агрегирующие функции.............................................................. 62 5.1.4. Группировка данных и построение отчетов............................. 63 Использование нулевых значений......................................................... 66 5.1.5. Объединение таблиц и сложный анализ данных...................... 67 5.1.6. Подзапросы..................................................................................... 69 5.2. Команды манипулирования данными.............................................. 71 6. ФУНКЦИИ СУБД...................................................................................... 73 6.1 Функции управления, обеспечение абстракции данных................ 73 6.2 Методы размещения данных.............................................................. 75 Последовательный метод........................................................................ 77 Прямой метод доступа............................................................................. 77 Индексно-последовательный метод...................................................... 78 Индексно-произвольный метод доступа............................................. 78 6.3 Системные функции. Обеспечение сохранности и секретности.. 79 6.4 Обеспечение целостности.................................................................... 79 6.5 Функции пользователя. Актуализация данных............................... 82 7 ТРАНЗАКЦИИ............................................................................................ 83 8 технология клиент/сервер…………………………………………….86 9 БЕЗОПАСНОСТЬ БАЗ ДАННЫХ........................................................... 91 10 ПРОБЛЕМЫ ПРОЕКТИРОВАНИЯ ИНТЕРФЕЙСА...................... 93 Задания на курсовую работу................................................................... 100 ПРИЛОЖЕНИЕ А........................................................................................ 103 ПРИМЕР КУРСОВОЙ РАБОТЫ.............................................................. 103 ПРИЛОЖЕНИЕ Б........................................................................................ 114 1. ВВЕДЕНИЕ В БАЗЫ ДАННЫХ Информатика – это наука о применении компьютеров в различных сферах деятельности, то есть наука о компьютерных (иногда говорят — новых информационных) технологиях. Информатика занимается схематичным, «формализованным» представлением информации, ее обработкой, предписаниями по ее переработке и машинами, обрабатывающими информацию. Цель информатизации состоит в разработке способов решения задач информационной обработки на вычислительных машинах, а также в разработке, организации и эксплуатации вычислительных систем. Формирование моделей информатики нацелено на представление определенных структур, взаимодействий и процессов в какой–либо области применения (предметной области) с помощью формальных средств, таких как структуры данных, языки программирования или логические формулы. Задача информатики – исследовать свойства формальных моделей, развивать их далее и устанавливать связи между формальными моделями и реальным миром в данной предметной области в смысле постановки задачи. 1.1. Информационные системы, их разновидности В начальный период развития ЭВМ каждый программист, разрабатывая программы, разрабатывал и свою форму представления данных, т.е. информационную модель объекта. Это приводило к тому, что каждая программа работала со своими данными что, в конечном счете, вело к избыточности и множеству информационных моделей объекта. Важной предпосылкой создания единой информационной модели стала возможность сохранения больших объемов данных. Появились магнитные диски и удобный доступ к данным. Введем понятия: информация и данные. Под информацией (в бытовом понимании) понимают любые сведения о каком-либо событии, сущности, процессе и т.д., являющемся объектом операций: восприятия, передачи, преобразования или использования. Информативные образцы могут создаваться в самых разнообразных формах: в форме звуковых, световых или радиоволн, электрического тока или напряжения, магнитных полей, знаков на бумажном носителе и т.д. Поскольку существует потребность в информации при принятии решений в любой сфере деятельности: в производстве, в человеческих отношениях, в управлении и т.д., человек создал естественные информационные системы: лекции, общение между людьми, радио, газета и т.д. В нашем сложном мире любая взаимосвязь и коррекция действий возможны только благодаря информации. Недаром говорят: "Кто владеет информацией, тот владеет всем", или: "Самое ценное, что у нас есть, - это информация". Данные можно определить как информацию, фиксированную в определенной форме, пригодной для последующей обработки, хранения и передачи. Совокупность различных средств, предназначенных для сбора, подготовки, хранения, обработки и выдачи информации в интересах различных пользователей и приложений, представляет собой информационную систему (ИС). Информационная система объединяет следующие составляющие: - языковые средства и правила, используемые для отбора и подготовки информации к вводу в ЭВМ, для отображения картины реального мира в модель данных, для работы пользователя с системой, для предоставления пользователю выдаваемой системой информации; - информационный фонд системы; - способы и методы организации информационных массивов и всех процессов обработки информации в системе; - алгоритмы функционирования системы, т.е. алгоритмы всех процедур по созданию, ведению и обработке информационных массивов, алгоритмы формирования ответов на запросы, и др.; - программное обеспечение системы, в состав которого входят программы, реализующие все алгоритмы функционирования системы; - комплекс технических средств, функционирующих в системе; - персонал, обслуживающий ИС. При разработке информационных систем возникают два аспекта: инфологический и датологический. На этапе инфологического проектирования ИС решаются вопросы, о каких явлениях или объектах реального мира требуется накапливать информацию, какие их характеристики и взаимосвязи будут учитываться. Задача инфологического этапа проектирования базы данных - получение семантических (смысловых) моделей, отражающих конкретную предметную область. Таким образом, на этапе инфологического проектирования решается вопрос о предметной области. Датологический аспект решает вопросы о представлении в памяти машины информационной системы, т.е., исходя из существующих средств, решаются вопросы хранения и обработки информации, модели представления информации, методы ее преобразования и формируются правила смысловой интерпретации. Поскольку области применения информационных систем разнообразны, разнообразны и их свойства и особенности, присущие каждой ИС. Среди множества факторов, определяющих совокупность свойств конкретной ИС, можно выделить три основных: технический уровень системы; характер обрабатываемой информации; целевые функции, т.е. круг задач, для решения которых данная система предназначена. Рассмотрим последовательно все три фактора. По техническому уровню ИС разделяются на ручные, механизированные, автоматизированные и автоматические. В ручных ИС все процессы обработки информации осуществляются вручную. Эти ИС имеют небольшой объем и хранятся на специальных карточках (например, перфокарты, личные карточки студентов, картотеки) различных типов. Примером ручной ИС может служить библиотечный каталог. В механизированных ИС для обработки и поиска информации используются различные средства механизации, а именно счетно-перфорационные машины. Кроме того, в комплект технических средств входит набор перфорационных машин, посредством которых информация заносится на перфокарты. В автоматизированных и автоматических ИС для хранения, обработки и поиска информации используются ЭВМ. Кроме этих операций, ЭВМ используется при выполнении операций, связанных со сбором, подготовкой и передачей информации, а также выдачей ее пользователю. При функционировании автоматизированных информационных систем (АИС), являющихся наиболее распространёнными, на различных этапах технологического процесса обработки информации принимает участие человек, который является полноправным партнером ИС. В автоматических ИС все процессы протекают без участия человека. Обычно автоматические ИС используются в составе крупных АСУ технологическими процессами и объектами. “партнерами “ автоматических ИС являются роботы, станки с числовым программным обеспечением, технологические процессы. Входная информация в таких системах представляется в форме сигналов или каких-либо физических величин, выходная информация используется для управления или регулирования, например, технологического процесса. По характеру обрабатываемой информации ИС делятся на документальные и фактографические. Документальные ИС служат для работы с документами на естественном языке: монографиями, научными отчетами, диссертациями, текстами законодательных актов и т.д. Основной задачей документальных ИС является поиск документов по их содержанию. Это требует понимания системой смысла запросов. Документальные модели данных соответствуют представлению о слабо структурированной информации, ориентированной в основном на свободные форматы документов, текстов на естественном языке[7]. Модели, основанные на языках разметки документов, связаны прежде всего со стандартным общим языком разметки – SGML (Standard Generalised Markup Language), который был утвержден ISO в качестве стандарта еще в 80-х годах. Этот язык предназначен для создания других языков разметки, он определяет допустимый набор тегов (ссылок), их атрибуты и внутреннюю структуру документа. Контроль за правильностью использования тегов осуществляется при помощи специального набора правил, называемых DTD-описаниями, которые используются программой клиента при разборе документа. Для каждого класса документов определяется свой набор правил, описывающих грамматику соответствующего языка разметки. С помощью SGML можно описывать структурированные данные, организовывать информацию, содержащуюся в документах, представлять эту информацию в некотором стандартизованном формате. Но ввиду своей сложности SGML использовался в основном для описания синтаксиса других языков (наиболее известным из которых является HTML), и немногие приложения работали с SGML-документами напрямую. Гораздо более простой и удобный, чем SGML, язык HTML позволяет определять оформление элементов документа и имеет некий ограниченный набор инструкций — тегов, при помощи которых осуществляется процесс разметки. Инструкции HTML в первую очередь предназначены для управления процессом вывода содержимого документа на экране программы-клиента и определяют тем самым способ представления документа, но не его структуру. В качестве элемента гипертекстовой базы данных, описываемой HTML, используется текстовый файл, который может легко передаваться по сети с использованием протокола HTTP. Эта особенность, а также то, что HTML является открытым стандартом и огромное количество пользователей имеет возможность применять возможности этого языка для оформления своих документов, безусловно, повлияли на рост популярности HTML и сделали его сегодня главным механизмом представления информации в Интернете. XML (Extensible Markup Language) — это язык разметки, описывающий целый класс объектов данных, называемых XML - документами. Он используется в качестве средства описания грамматики других языков и контроля за правильностью составления документов. То есть сам по себе XML не содержит никаких тегов, предназначенных для разметки, он просто определяет порядок их создания. Тезаурусные модели основаны на принципе организации словарей, содержат определенные языковые конструкции и принципы их взаимодействия в заданной грамматике. Эти модели эффективно используются в системах-переводчиках, особенно многоязыковых переводчиках. Принцип хранения информации в этих системах и подчиняется тезаурусным моделям. В процессе индексирования документов используется и составляется тезаурус - словарь, содержащий перечисление основных лексических единиц предметной области и описание парадигматических отношений между ними. Парадигматические отношения - это семантические отношения, существующие между лексическими единицами языка независимо от контекста. Поиск нужного документа производится по соответствующему запросу. Дескрипторные модели — самые простые из документальных моделей, они широко применялись на ранних стадиях использования документальных баз данных. В этих моделях каждому документу соответствовал дескриптор — описатель. Дескриптор - это некоторое множество слов или словосочетаний, которые соответствуют основным понятиям предметной области и включены в ее тезаурус. Дескриптор имел жесткую структуру и описывал документ в соответствии с теми характеристиками, которые требуются для работы с документами в разрабатываемой документальной БД. Как определить о чем идет речь, когда употребляется слово рак - животное, заболевание или созвездие? Для распознавания того, о чем идет речь, необходимо составить тезаурус для каждого из трех вариантов поиска. При поиске нужного документа возможны ситуации: неточность поиска (информационный шум); неполнота (не все документы найдены); релевантные документы (соответствующие запросу). Качество поиска документа оценивается по точности поиска и полноте. Полнота поиска определяется по формуле: R=A/C , где А - число документов, релевантных запросу, С - общее число документов, имеющихся в системе. А точность поиска нужного документа определяется по формуле: Р =А/L , где L - общее количество документов, выданных в ответ на запрос. В фактографических ИС хранимая и обрабатываемая информация представляет собой конкретные сведения, факты, примеры, результаты измерений, справочные и статистические данные. Информация часто носит оперативный характер. Она выдается пользователю или прикладным программам для обработки. Фактографические ИС реализуются банками данных. Банк данных - это автоматизированная информационная система, включающая в свой состав комплекс специальных методов и средств (математических, информационных, программных, языковых, организационных и технических) для поддержания динамической модели предметной области с целью обеспечения информационных запросов пользователей[2]. В результате развития технологии ИС система доступа к данным и данные, которые накапливаются в системе, были логически разделены. Поэтому БнД состоит из двух частей: 1) базы данных (БД), которая является датологическим представлением информационной модели предметной области; 2) системы управления базой данных (СУБД), с помощью которой и реализуется централизованное управление данными, хранимыми в базе, доступ к ним и поддержание их в состоянии, соответствующем состоянию предметной области. Примером фактографических систем служат: учет складских запасов, обработка заказов и товарно-транспортных накладных, учет поставок, подготовка форм статистической отчетности и т.д. СУБД - программная система, предназначенная для создания БД, поддержания ее в актуальном состоянии, обеспечения эффективного доступа к ней. Доступ к БД возможен только посредством СУБД. СУБД общего назначения не ориентированы на определенную предметную область и предоставляются пользователю как коммерческое изделие, обладающее средствами настройки для работы с конкретной БД в условиях конкретного применения. СУБД общего назначения входит чаще всего в состав инструментального средства для создания автоматизированных информационных систем и позволяет сократить сроки разработки таких систем. По целевым функциям (назначение самой ИС) системы подразделяются: информационно-справочные; управленческие; информационно - расчетные; информационно - логические. Информационно-справочные системы обеспечивают информационные запросы пользователя, примером такой системы может служить система резервирования мест на авиационном и железнодорожном транспорте. Управленческие ИС служат для решения задач АСУ предприятия: ИС больниц, автоматизированных складов, материально-технического снабжения, учета кадров, бухучета и т.д. Они, как правило, ориентированы на выдачу различного рода справок, отчетных форм для руководства предприятием. В информационно-расчетных ИС хранимая информация используется для решения расчетных задач. Например, статистический учет и анализ, прогноз месторождений и погоды. К этим же системам относятся системы, функционирующие в составе САПР. Информационно-логические системы способны выдавать информацию, не введенную ранее в систему в непосредственном виде, а вырабатываемую на основании логического анализа, обобщения и т.д. Это, как правило, интеллектуальные ИС. 1.2. Состав АИС Любая АИС функционирует в окружении внешней среды, которая является источником входной и потребителем выходной информации. Начиная с входа в систему и заканчивая выходом, информационный поток проходит несколько этапов обработки: - сбор, регистрация и первичная обработка; - передача по каналу связи от источника к ЭВМ; - перенос на машинные носители; - создание и поддержка информационных фондов; - внутримашинная обработка и формирование выходных форм; - передача по каналу связи от ЭВМ к пользователю; - преобразование к виду, пригодному для восприятия пользователем. Подсистема СБОРА И ПЕРВИЧНОЙ ОБРАБОТКИ , как привило, занимается сбором информации на естественном языке. В результате первичной проверки отбирается информация, которой нет в АИС и которая будет в дальнейшем введена в ЭВМ. Эта информация на первоначальном этапе обработки приводится к виду, пригодному для ввода в ЭВМ, и фиксируется на различного рода носителях. Подсистема ВВОДА получает информацию от подсистемы СБОРА И ПЕРВИЧНОЙ ОБРАБОТКИ в пригодном для ввода в ЭВМ виде. Осуществляет перенос информации в систему (на машинные носители), при этом производятся контроль за правильностью переноса информации и устранение возникших ошибок. Введенная информация размещается в ЭВМ и образует информационный фонд АИС. Над элементами информационного фонда осуществляются различные операции внутримашинной обработки: сортировка, поиск, различные арифметические и логические операции, т.е. операции, которые обеспечивают поддержание АИС в актуальном состоянии. Здесь же формируется выходная информация в соответствии с заданием на обработку. Запрос пользователя перед вводом в ЭВМ также проходит определенную обработку и рассматривается ЭВМ как задание на внутримашинную обработку. Формирование и поддержка информационных массивов, а также все операции внутримашинной обработки осуществляются под управлением специального комплекса программ, входящих в подсистему ВНУТРИМАШИННОЙ ОБРАБОТКИ . Таким образом, в систему ОБРАБОТКИ И ХРАНЕНИЯ информации входят: информационный фонд, подсистема внутримашинной обработки. Кроме того, сюда следует включить технические средства ЭВМ: средства ввода/вывода, средства хранения информации. Подсистема ВЫДАЧИ И ОТОБРАЖЕНИЯ (вывода) обеспечивает выдачу ответа на запрос, представляя его в форме, удобной для восприятия пользователем. В состав входит комплекс программ, обеспечивающих нужный вид выходной информации, а также технические средства, на которых отображается выходная информация: принтеры, дисплеи, графопостроители, табло, индикаторы. Подсистема СВЯЗИ необходима в том случае, когда источники информации, ЭВМ и пользователи удалены друг от друга. В систему связи входят каналы передачи данных: телеграфные, телефонные и компьютерные сети; удаленные терминалы: дисплеи, специальные терминалы, абонентские пункты; программное обеспечение, позволяющее связать терминалы с центральной ЭВМ. Рисунок 1 Состав АИС 1.3.Архитектура, предметная область. Реальный мир многообразен. Нет такой ЭВМ, в которую можно было бы занести весь окружающий нас мир. В своей деятельности каждый использует часть от всего его многообразия, т.е. модель, адекватно представляющую интересующую нас область. Часть реального мира, сведения о которой накапливаются в базе данных и подвергаются обработке, называют предметной областью . Определение предметной области (ПО) является начальным этапом при проектировании любой ИС. Именно на этом этапе выявляются все потребности и все пользователи, определяющие содержание будущей системы. Предметная область БД определена, если известны существующие в ней объекты, их свойства и отношения. Объектом считают любые предметы, события, понятия и т.п., которые представляют интерес для пользователей. Проектирование БД начинается с предварительной структуризации ПО. В хорошо спроектированной схеме структура базы данных оказывается легко доступной для анализа и при модификации базы не возникает противоречий. Объекты (сущности) реального мира, о которых будет накапливаться информация, подвергаются классификации, и фиксируется совокупность их свойств (атрибутов), посредством которых будут описаны в БД типы объектов. Например, объект ЭВМ можно характеризовать такими атрибутами: тип и число процессоров, скорость вычислений, объем оперативной памяти, система команд, числом портов ввода/вывода и т.д. Кроме того, фиксируются виды отношений (взаимосвязей) между объектами. Объектная система имеет следующие составляющие: Объект (Сущность) Свойство (Атрибут) Объектное отношение (Связь) Время Выбор объектов осуществляется в соответствии с назначением АИС. Объекты могут быть атомарные и составные. Для составного объекта должны быть определены его внутренние составляющие (которые в свою очередь могут быть объектами). Таким образом, при проектировании необходимо определить внутреннюю структуру объекта. Каждый объект в каждый момент времени характеризуется определенным состоянием. Состояние объекта описывается с помощью некоторого набора свойств (атрибутов) и связей (отношений) с другими объектами. Каждый объект в системе отличается от других своим набором свойств. Выбор существенного атрибута или атрибутов носит субъективный характер. Объекты имеют определенное состояние, как в отдельные моменты времени, так и в течение некоторых интервалов времени. Учитывая фактор времени при проектировании, можно в дальнейшем строить динамические модели, в которых отражается зависимость от времени составляющих объектной системы. Объекты группируются в группы однородных объектов по структуре и поведению. Группа называется типом объектов. При этом все экземпляры данного типа обладают одинаковыми свойствами (атрибутами). Свойства типа "наследуются" каждым экземпляром объекта данного типа. Для того чтобы отличить один объект от других объектов данного типа, необходим уникальный идентификатор, называемый первичным ключом. В качестве ключа можно использовать атрибут или группу атрибутов. Между объектами могут существовать связи, имеющие различный содержательный смысл. В качестве объектов в моделях ПО могут рассматриваться, как материальные объекты реальной действительности (предприятия, изделия, сотрудники и т.д.), так и нематериальные (описание явлений, ы статей и т.д.). Для примера рассмотрим магазин и в качестве объекта возьмем, например, книги. Атрибутами этого товара будут наименование товара (автор и название), тематика, тираж, цена. Объектом также может быть издательство, которое выпустило данную книгу. В качестве атрибутов в этом случае будут наименование издательства, адрес, телефон, ответственное лицо. Между товаром в книжном магазине и издательством существует связь - поставка товара. Связи могут быть обязательными и факультативными. Обязательные связи определены необходимостью связи объектов. Совокупность типов объектов ПО и типов связей между ними характеризует типовую структуру предметной области. При моделировании ПО проектировщик разбивает ее на ряд локальных областей, моделируя каждую область отдельно, а затем выполняет их объединение посредством связей. Особенность современных технологий баз данных состоит в том, что в настоящее время используется трехуровневая архитектура ANSI/SPARC представления БД: 1) концептуальный уровень; 2) внешний уровень; 3) внутренний уровень. На первом, концептуальном уровне, описываются элементы данных и связи между ними, которые являются отражением объектов и связей реального мира. При построении концептуальной модели проводится анализ информационных потребностей пользователей и определение нужных им элементов данных. На основе концептуального проектирования строится единое логическое описание всех элементов данных и отношений между ними. Каждая группа пользователей в зависимости от потребностей получает свое представление в данных в базе данных. Каждая из групп «видит» только необходимую ей часть данных. Эта часть (внешний уровень) определяется (выводится) из полной концептуальной модели БД. Внутренний уровень – уровень хранения БД, обеспечивает представление данных в памяти ЭВМ. Конечный пользователь всегда работает с внешним представлением БД. За логическую и физические структуры отвечает администратор БД. Проектирование БД начинается с концептуального уровня, когда пользовательские представления данных внешнего уровня интегрируются в единую концептуальную схему баз данных. Рисунок 2 Трехуровневая архитектура базы данных в соответствии со стандартом ANSI/SPARC Контрольные вопросы. 1. Объясните своими словами термины: информационная система, база данных, предметная область. 2. Перечислите и кратко охарактеризуйте каждый компонент современной информационной системы, использующей базу данных. 3. Какие из следующих утверждений могут рассматриваться как данные, какие – как информация? а) Товар К345-Б выгоден. б) Товар К345-Б производится фирмой «Диалог». в) Сергей Иванов в прошлом году получил комиссионных на большую сумму, чем другой торговый агент. г) Катя Иванова родилась 17 декабря 1988 года. д) Сегодня стоит хорошая погода. 4. Объясните своими словами понятия: концептуальная модель, внешняя модель. 5. Напишите, чем характерны документальные системы. 6. Объясните, чем концептуальная модель отличается от логической модели. 7. Какие составляющие имеет объектная система. 8. Из каких подсистем состоит АИС? 9. Объясните своими словами понятие банк данных? 10. Какие составляющие имеет информационная система? 2. КОНЦЕПТУАЛЬНОЕ ПРОЕКТИРОВАНИЕ Проектирование БД представляет собой сложный процесс, поскольку необходимо построить модель реального мира таким образом, чтобы ею можно было воспользоваться для решения поставленных задач. Модель должна быть адекватна той предметной области, для которой она создается [2,3,4,7]. Главными элементами концептуальной модели являются объекты и отношения между ними. Объекты – это сущности (вещи, свойства, явления и т.д.), о которых должна накапливаться информация в разрабатываемой системе. Множество всех объектов, имеющих некоторое общее свойство Р, называется объектным множеством. Элемент объектного множества называется объект-элемент или экземпляр сущности . Рисунок 3 Пример объектного множества Объектные множества можно разделить на лексические и абстрактные. Элементы лексического объектного множества можно отобразить соответствующими знаками, например буквами алфавита. К лексическим множествам можно отнести такие множества, как ФИО, номер студенческого билета, дата зачисления в ВУЗ и т.д. СТУДЕНТ в данном примере – это абстрактное объектное множество, его нельзя отобразить знаком или буквами поскольку объект СТУДЕНТ не является именем или номером студенческого билета, т.к. имя и номер студенческого билета могут меняться, а студент от этого не изменится. Элементы абстрактных множеств часто представляются внутренними номерами, которые вне системы не имеют смысла. Эти внутренние номера называют идентификаторами объекта или ключами, поскольку они однозначно определяют экземпляр объектного множества. Объектные множества могут иметь сложную внутреннюю структуру, которая учитывается при проектировании. Некоторые объектные множества могут содержаться внутри других объектных множеств. Например. Множество СТУДЕНТ_ФВС содержится в множестве СТУДЕНТ а б Рисунок 4 Представление конкретизация/обобщение Здесь СТУДЕНТ_ФВС является конкретизацией объектного множества СТУДЕНТ, а СТУДЕНТ является обобщением объектного множества СТУДЕНТ_ФВС. Связи выступают в модели в качестве средства, с помощью которого представляются отношения между объектными множествами, имеющими место в предметной области. Рисунок 5 Объектное отношение Построенное объектное отношение представляет собой составное объектное множество: СЕМЕЙНАЯ_ПАРА. Рисунок 6 Составное объектное множество При анализе отношений между объектными множествами могут встречаться бинарные (между двумя множествами), тернарные и, в общем случае, n-арные отношения. Наиболее часто встречаются бинарные отношения. Мощностью называется максимальное количество элементов одного объектного множества, связанных с одним элементом другого объектного множества. Мощности отношений могут быть один_к_одному, один_ко_многим, многие_ко_многим. Отношение, максимальная мощность которого как минимум в одном направлении равна одному, называется функциональным . В предыдущем примере отношение состоит в браке имеет мощность один_к_одному. Ниже приведены примеры отношений один_ко_многим и многие_ко_многим. Рисунок 7 Отношение один_ко_многим Рисунок 8 Отношение многие_ко_многим Атрибут – это поименованная характеристика объектного множества, которая принимает значения из некоторого множества значений. Можно атрибут определить по-другому: функциональное отношение объектного множества к другому объектному множеству. Значение атрибута однозначно определено для каждого элемента объекта. Например, для описания свойств объектного множества КНИГА можно использовать атрибуты: НАЗВАНИЕ, ФАМИЛИЯ_АВТОРА, ЦЕНА, ГОД_ИЗДАНИЯ. Атрибуты могут изменяться, в то время как сам объект остается тем же. В приведенном выше примере атрибут ЦЕНА может со временем измениться. Может быть пустое значение атрибута, т.е. атрибут не определен. Например, объект КНИГА может не иметь значение атрибута ФАМИЛИЯ_АВТОРА. Атрибуты, значение которых не меняется, можно использовать в качестве ключей. Если объект является конкретизацией другого объекта, то он наследует все атрибуты и отношения обобщенного объекта. Необходимо заметить, что конкретизированный объект может иметь свои дополнительные атрибуты. Конкретный человек Иванов Иван Степанович относится к множеству ЖЕНАТЫЙ ЧЕЛОВЕК, которое является подмножеством объектного множества ЧЕЛОВЕК. Иванов Иван Степанович наследует атрибуты: ИНН, ИМЯ, АДРЕС и отношение РАБОТАЕТ_В. Обладает собственным атрибутом СУПРУГ. Рисунок 9 Наследование отношений и атрибутов Рассмотрим пример - модель проектной организации. Проектная организация разрабатывает некие проекты, для которых необходимы определенные детали. Проектная организация связана с рядом поставщиков деталей. В организации несколько отделов. На основании этих данных можно построить следующую модель (рисунок 10). Рассмотрим объекты ПОСТАВЩИК, ПРОЕКТ, ДЕТАЛЬ. При построении бинарных отношений ПОСТАВЩИК_ПРОЕКТ (П-П), ПРОЕКТ_ДЕТАЛЬ (Д - П), ПОСТАВЩИК_ДЕТАЛЬ (П-Д) можно ответить на вопросы: какие детали нужны для проекта А1; поставляет ли поставщик АВ детали для проекта А1; поставляет ли поставщик АВ деталь АС. Но если нужно ответить на вопрос: поставляет ли поставщик АВ деталь АС для проекта А1, то исходя из построенной модели на этот вопрос ответить сложно. Рисунок 10 Модель предметной области для проектной организации с бинарными связями Рисунок 11 Модель с другими типами связей В этом случае добавляют тернарную связь ПОСТАВЩИК-ДЕТАЛЬ-ПРОЕКТ (П-Д-П). Над проектом работают много служащих, но из всей массы служащих нет возможности выделить руководителя проекта. В таких случаях можно добавить дополнительную связь РУКОВОДИТЕЛЬ-ПРОЕКТ (П-РП). Может возникнуть необходимость в получении информации о том, из каких частей состоит полученная деталь. Для получения такой информации следует построить отношение ДЕТАЛЬ-ДЕТАЛЬ (Д-Д). В результате преобразований получим модель, приведенную на рисунке 11. Рассмотрим более сложные отношения. Допустим, что необходимо отследить продажу разных видов товаров по фирмам. Для этого построим отношение ТОВАР-ФИРМА, с атрибутом – КОЛИЧЕСТВО (рисунок 12). Возникает вопрос: как отследить количество проданного товара? Если КОЛИЧЕСТВО припишем в качестве атрибута ко множеству ТОВАР, в этом случае невозможно отследить, в какую фирму и сколько продано товара (рисунок 12 а). Если атрибут КОЛИЧЕСТВО припишем фирме, то неизвестно, какой товар продан фирме (рисунок 12 б). Можно заметить, что атрибут КОЛИЧЕСТВО зависит как от товара, так и от фирмы, в которую продан товар. Поэтому КОЛИЧЕСТВО является атрибутом отношения ТОВАР-ФИРМА (рисунок 12 в). а) б) в) Рисунок 12 Модели отслеживания продаж В дополнения к вышесказанному рассмотрим пример: модель формирования заказа на товар (рисунок 13). Поставщику сделан заказ на поставку товара. В приведенной модели ЦЕНА, ОПИСАНИЕ, ИНВЕНТАРНЫЙ НОМЕР относятся к объектному множеству ТОВАР. НОМЕР, НАЛОГ, ИТОГО, ДАТА относятся к объектному множеству ЗАКАЗ. КОЛИЧЕСТВО и СУММА являются атрибутами составного объекта, поскольку зависят и от объекта ТОВАР и от объекта ЗАКАЗ. При этом следует обратить внимание на то, что СУММА – это вычисляемый атрибут. Рисунок 13 Модель формы заказа Концептуальная модель данных создается на основании анализа вопросов, на которые пользователи хотят получить ответы. При проектировании большой базы данных необходимо работать с разными группами пользователей и создавать несколько моделей данных, несколько локальных представлений, которые затем нужно объединить. Для каждой локальной области необходимо сформулировать сущности, требуемые для ее описания. Сделать это достаточно трудно. Например, выделим две сущности: ДЕТАЛЬ, ИЗДЕЛИЕ и связь – ВХОДИТ В СОСТАВ : В этом случае, достаточно просто проследить, в какие еще изделия входит деталь. Если эта информация не нужна, то ДЕТАЛЬ можно рассматривать как атрибут сущности ИЗДЕЛИЕ. С какой точки зрения рассматривать предметную область, зависит от того, что конечный пользователь хочет получить на свои запросы к БД. Объединение локальных представлений носит итеративный характер, в процессе которого выявляются противоречия между локальными представлениями, вызванные некорректностью требований, ошибками, неполнотой спецификаций. Процесс объединения моделей включает удаление объектных множеств, отношений и атрибутов, которые являются избыточными, и образование новых абстрактных объектных множеств более высокого порядка путем определения новых отношений и продолжается до тех пор, пока не будут устранены все противоречия. В результате проектирования получаем концептуальную модель ПО, оформленную в виде диаграмм. Данный процесс требует плотного взаимодействия разработчиков и пользователей БД. Следующим этапом проектирования БД является выбор модели данных, которая определяет правила порождения допустимых структур данных, возможные операции над такими структурами, а также классы представимых средствами этой системы ограничений целостности данных. 3. МОДЕЛИ ДАННЫХ Модель предметной области состоит, как правило, из описания конкретных фактов, а также некоторых общих понятий и закономерностей. Первые образуют базу данных, вторые - базу знаний (БЗ). К знаниям относят информацию о логике решения задач, а к данным - информацию, которая должна быть проанализирована в соответствии с этой логикой. Выделяют специфические признаки, отличающие данные от знаний: 1) внутренняя интерпретируемость, т.е. в знаниях находится информация, раскрывающая смысл элементов знаний - информационная и описательная части. Фиксируются все сведения об информационной единице, которые могут понадобиться системе или пользователю для работы с ней; 2) структурированность - свойство декомпозиции сложных объектов в более простые и установление соответствующих связей между ними; 3) связность - в знаниях отражаются закономерности относительно фактов, процессов, явлений и причинно-следственные связи между ними; 4) активность - знания обладают способностью порождения новых знаний, например, при обнаружении неполноты или противоречивости знаний. В качестве информационных единиц, характеризующих некоторое знание, могут выступать присоединенные или встроенные процедуры, что позволяет активизировать эти процедуры в результате появления в базе тех или иных информационных единиц или связей между ними. Это свойство определяется активностью знаний, их первичностью по отношению к процедурам, что не характерно для данных, играющих по отношению к процедурам пассивную роль. 3.1.Понятие модели В различных системах для задания запроса (например, поискового) из программы пользователя к СУБД применяются разные методы. Можно сказать, что каждая СУБД имеет свои языковые средства, называемые языком данных (ЯД). При этом необходимо учитывать, что ЯД не язык программирования в традиционном смысле. Язык данных задает правила обработки запроса (например, поиска), а также указывает элементы данных, т.е. ЯД предполагает определенную структуризацию данных (средства описания данных) и средства описания действий, которые необходимо выполнять над данными (средства манипулирования данными). Совокупность средств описания и средств манипулирования называется моделью данных. Модель знаний содержит набор формальных правил записи знаний (модель данных и семантическое соответствие) и примитивы манипулирования знаниями (правила логического вывода) В настоящее время широко известны три типа моделей данных: иерархическая, сетевая и реляционная. Наиболее перспективной для дальнейшего развития и применения считается реляционная модель представления данных. Основные исследования всех трех типов моделей данных закончены, и они показали, что все три типа равномощны. Необходимо заметить, что появилась еще одна модель данных – объектно-ориентированная. 3.2. Иерархические модели Иерархическая модель данных возникла из практики. Впервые СУБД, использующие эту модель данных, были созданы в 1960 -х годах для поддержки лунного проекта Аполлон. Основной посылкой создания стала необходимость управления миллионами деталей, связанных друг с другом иерархическим образом. Иерархические модели удобны и используются для построения рубрикаторов и классификаторов. В основе модели лежит граф типа дерево. Граф – это объект, состоящий из двух множеств: множества вершин X={x1 , x2 , . . . ,x3 } и множества линий, соединяющих эти вершины, называемых множеством ребер или дуг. Применительно к модели данных вершины используются для интерпретации сущностей, а линии - для интерпретации связей между типами сущностей. Древовидная структура или граф типа дерево- это связный граф, не имеющий циклов. Обычно выделяют вершину, в которую не заходит ни одна линия, в этом случае граф становится ориентированным. КОРЕНЬ 1 уровень исходная вершина 2 уровень порожденная вершина 3 уровень 4 уровень концевые вершина (листья) Рисунок 14 Иерархическая структура Иерархическая структура удовлетворяет следующим условиям: 1. Иерархия начинается с корневой вершины. 2. Каждая вершина соответствует одному или нескольким атрибутам. 3. На уровнях с большим номером находятся порожденные вершины. 4. Доступ к каждой вершине происходит через корневую по единственному пути. 5. Каждая вершина, находящаяся на i -том уровне, связана только с одной вершиной (i-1) -го уровня. 6. Корневая вершина связана с одной или несколькими порожденными (зависимыми) вершинами. 7. Существует произвольное количество вершин каждого уровня. В терминологии иерархической модели существует несколько основных понятий: - Тип сегмента – это поименованная совокупность типов элементов данных, в него входящих, соответствует объекту. - Экземпляр сегмента образуется из конкретных значений полей или сегментов данных, в него входящих. Набор всех экземпляров сегментов, подчиненных одному экземпляру корневого сегмента, называется физической записью. Количество экземпляров потомков может быть различным для разных экземпляров родительских сегментов, поэтому в общем случае физические записи имеют различную длину. На рисунках 14, 15 представлена иерархическая структура, соответствующая отношениям в ВУЗе. В ВУЗе несколько факультетов. В примере на рисунке 15 их указано четыре. В реальной жизни их может быть другое количество. Каждый факультет "содержит" разное количество кафедр. Рисунок 14 Рисунок 15 Неудобство такой системы представления данных заключается в том, что реальный мир не может быть легко представлен в виде древовидной структуры с единственным корнем. Примерно в это же время сформировалась другая модель данных – сетевая. 3.3. Сетевые модели Сетевые модели данных также базируются на использовании графовой модели представления информации. Вершины соответствуют типам, дуги - связям типов. В сетевой модели допускаются произвольные связи между сущностями. Одно из основных достижений сетевой модели данных состоит в том, что впервые были введены языки представления данных (Data Definition Language, DDL) и языки манипулирования данными (Data Manipulation Language, DML). При реализации сетевой модели можно применять различные представления данных, но основой описания является понятие набора. Кроме понятия набора данных в сетевых БД применяется понятия: элемент данных, агрегат данных и запись. Элемент данных – это минимальная единица информации, доступная пользователю с использованием СУБД. Агрегат данных соответствует следующему уровню обобщения модели и представляет собой вектор или повторяющуюся группу. Совокупность агрегатов или элементов данных образует запись. Набор представляет собой поименованное двухуровневое дерево. Исходная запись (1-й уровень) называется владельцем набора, а порожденные записи - членами этого набора. Каждый из членов одного набора может быть объявлен владельцем другого набора. Фактически наличие подобных возможностей позволяет промоделировать отношения МНОГИЕ_КО_МНОГИМ. Таким образом, можно описать достаточно сложную сетевую структуру. Среди всех наборов данных выделяю специальный тип набора, называемый «Сингулярным набором», владельцем которого формально определена вся система. Принципиальное значение в сетевой модели имеет то положение, что предусматривается обработка (одновременная обработка) только одиночных объектов из базы данных. Механизмы доступа к данным и навигация сложны, так как необходимо, двигаясь по структуре: а) найти нужную запись; б) сделать ее текущей; в) извлечь в рабочий буфер; г) изменить данные; д) записать содержимое буфера в БД. Возможен переход от представления одной структуры данных к другой. Приёмы просты, но приводят к избыточности в логическом представлении данных. 3.4. Реляционные модели данных Теоретической основой этой модели данных стала теория отношений. Было показано, что множество отношений замкнуто относительно некоторых специальных операций, т.е. образует вместе с этими операциями абстрактную алгебру. Реляционная модель была предложена в 1970 году Коддом. Основу реляционной модели данных составляет совокупность данных, сформированных в виде таблицы. Такая форма привычна для специалистов, пользующихся различного рода справочной литературой. Формальным аналогом таблицы выступает отношение. Пусть дана совокупность множеств D 1 , D 2 , … Dn . Декартово произведение D 1 x D 2 x . . . x Dn - множество всех возможных кортежей < d 1 , d 2, . . . dn > таких, что di є Di , i = 1,…, n . Множества Di называют доменами . N -арным отношением R называется некоторое подмножество декартова произведения этих множеств: R Í D 1 x D 2 x . . . x Dn . Пример. Пусть заданы множества D 1 = {а1 ,а2 ,а3 ,а4 ,а5 } и D 2 ={ b 1 , b 2 , b 3 }, тогда декартово произведение этих множеств запишется как D1 x D2 = {<a1 ,b1 >,<a1 ,b2 >,<a1 ,b3 >,<a2 ,b1 >, . . .,<a5 ,b3 >}. Построим отношение R={<a1 ,b3 >,<a2 ,b1 >,<a2 ,b3 >,<a3 ,b1 >,<a3 ,b3 >}. Очевидно, что R Ì D 1 x D 2 . Совокупность кортежей, записанных друг за другом, образует таблицу, строки которой соответствуют кортежам, а столбцы - атрибутам. A1 A2 a1 b3 a2 b1 a2 b3 a3 b1 a3 b3 Атрибут Ai представляет собой подмножество домена Di . Для предыдущего примера атрибутами являются множества A 1 = { a 1 , a 2 , a 3 }, A 2 ={ b 1 , b 3 }, при этом A 1 Ì D 1 и A 2 Ì D 2 . Запись: R ( A 1 , A 2 ,…, An ) называется схемой отношения R и содержит наряду с названием отношения названия атрибутов. Если атрибуты принимают значения из одного и того же домена, то они называются Q -сравнимыми , где Q - множество допустимых операций сравнения, заданных для данного домена. Схемы двух отношений называются эквивалентными , если они имеют одинаковую степень и возможно такое упорядочение имен атрибутов в схемах, что на одинаковых местах будут располагаться сравнимые атрибуты, то есть атрибуты, принимающие значения из одного домена. Поскольку отношение - это подмножество, то следует отметить, что оно не может содержать двух одинаковых кортежей. Подмножество K = { Ai 1 , Ai 2 ,..., Aik } заданной схемы отношения R(A 1 , A 2 ,…, An ) будем называть ключом, если в двух различных кортежах отношения R значения в каждом атрибуте из K не все одинаковы и ни одно собственное подмножество K этим же свойством не обладает. Другими словами, ключ - это такое множество атрибутов, которое при задании этих атрибутов однозначно определяет кортеж. Отношение(в БД) моделирует реальную ситуацию, и в соответствии со свойствами отношений в таблице могут присутствовать только атрибуты, обладающие свойством симметричности. В результате вышесказанного реляционная таблица обладает рядом специфических свойств: 1. В таблице нет двух одинаковых строк. 2. Таблица имеет столбцы, соответствующие атрибутам отношения. 3. Каждый атрибут в отношении имеет уникальное имя. 4. Порядок строк в таблице произвольный. 5. Два отношения, отличающиеся только порядком следования столбцов, интерпретируются как одинаковые. Операции над отношениями выполняются методами реляционного исчисления и реляционной алгебры. Кодд показал, что реляционная алгебра и реляционное исчисление - эквивалентны. 3.4.1. Реляционная алгебра Множество М вместе с набором операций где ni – арность операции ji, называется алгебраической структурой, универсальной алгеброй или просто алгеброй. Множество М называется основным (несущим множеством ), множество операций å называется сигнатурой . Основным множеством в реляционной алгебре является множество отношений. Поскольку отношение можно представить в виде таблицы, то здесь в качестве операндов будем рассматривать реляционные таблицы. Пусть заданы отношения R и S , которые содержат перечни изделий, выпускаемых разными фирмами F1 и F2 соответственно. S Prod_id Prod 1035 Cвитер 2241 Настольная лампа 2249 Светильник 2378 Бронзовая скульптура R Prod_id Prod 1055 Cвингер 2246 Люстра 2249 Светильник Основные операции реляционной алгебры: сумма, пересечение, вычитание, произведение, выбор, проекция, Q - соединение, деление. Первые четыре взяты из теории множеств, следующие применяются в реляционной модели данных. Объединением двух отношений R и S :R È S называется множество всех кортежей, содержащихся в R и S. Q Prod_id Prod 1035 Cвитер 2241 Настольная лампа 1055 Cвингер 2246 Люстра 2249 Светильник 2378 Бронзовая скульптура В результате операции объединения получим следующую таблицу: Необходимо отметить, что объединяются таблицы только с одинаковыми атрибутами и кортежи одинаковые для обеих таблиц, входят в результирующую таблицу Q только один раз. Q Prod_id Prod 2249 Светильник Пересечением R Ç S отношений R и S является множество кортежей, одновременно содержащихся в отношениях R и S . В этом случае в отношении Q содержится перечень изделий, выпускаемых обеими фирмами. Разностью R\S отношений R и S называется отношение, содержащее множество всех кортежей, содержащихся в R и не содержащих кортежи из S . В результате выполнения операции разность получим отношение Q , содержащее перечень изделий, выпускаемых только фирмой F2 . R\S Q Необходимо отметить, что для получения перечня изделий, выпускаемых только фирмой F1 , необходимо выполнить операцию S \ R . В этом случае получаем отношение Q1 вида: Prod_id Prod 1055 Свингер 2246 Люстра Q1 Prod_id Prod 1035 Свингер 2241 Настольная лампа 2378 Бронзовая скульптура Декартовым произведением RxS отношений R и S является множество кортежей t = <r1 , r2 ,…,rm , S1 , S2 ,…, Sn >, где первые m элементов кортежа t образуют кортеж из множества R , последние n элементов из отношения S , т.е. <r1 , r2 , …, rm > Î R и <S1 , S2 ,…, Sn > Î S . Рассмотрим две таблицы А и В. А В id N цвет статус 10 27 Зеленый Красный Cиреневый 22 17 54 11 35 В результате выполнения операции произведения получим таблицу Т=АхВ вида Т id N цвет статус 10 10 10 11 11 11 27 27 27 35 35 35 Зеленый Красный Сиреневый Зеленый Красный Сиреневый 22 17 54 22 17 54 Произведение создано путем присоединения к каждой строке таблицы А каждой строки таблицы В. Выборкой aF (R) из отношения R является множество кортежей отношения R, для которых истинен предикат F. Предикат – это некоторое условие, выраженное в форме логического утверждения. Условия в основном такие же, какие используются в операторе IF в выражениях традиционных языков программирования. В качестве операндов здесь выступают столбцы реляционной таблицы, используются арифметические операторы сравнения <, ≤, =, ≥ , ≠ , > и логические операторы ^ (И), | (ИЛИ), ¬ (НЕ). В выражении условия могут присутствовать скобки. В результате выполнения операции «выборка» из реляционной таблицы получим реляционную таблицу, все кортежи которой будут удовлетворять заданному условию. Пусть существует реляционная таблица, в которой перечислены фамилии студентов 1 курса и их оценки по предметам «Математика», «Физика», «Информатика». Необходимо найти всех студентов, которые сдали эти предметы на «5». Условное выражение в этом случае запишется как («Математика»=5)^(«Физика»=5)^(«Информатика»=5) Пусть R (А1 , А2 ,…, Аn ) – n-арное отношение. Проекцией Пх (R) отношения R на множество доменов Х={Аi1 , …, Аik } называется такое множество всех кортежей t = <ν1 , ν2 ,…, νk > , что существует кортеж r = <r1 , …, rm > отношения k , в котором rij = νj , j =1, …, k . Операция “проекция” позволяет исключить из таблицы ненужные столбцы, т.е. во вновь создаваемую реляционную таблицу выбираются только необходимые столбцы. Необходимо отметить, что операция создания проекций автоматически удаляет повторяющиеся кортежи из результирующей таблицы. Операция соединения используется для связывания данных между таблицами. Новое отношение строится посредством конкатенации кортежей двух исходных отношений. У этой операции есть несколько версий: естественное соединение, тета–соединение и внешнее соединение. При естественном соединении связываются таблицы, когда общие столбцы имеют равные значения. Пусть отношение А и В имеют следующие схемы отношения соответственно. А = {x1 , x2 ,…, xm y1 ,…, yn }, B = {y1 ,…, yn z1 ,… zp } Естественным соединением называется отношение с заголовком {x, y, z} и телом, содержащим множество всех кортежей {X:x, Y:y, Z:z} ткаих, что в отношении А значение атрибута Х равно х, значение атрибута Y равно у, а в отношении В значение атрибута Y равно y, а атрибута Z равно z. R Q В результате применения операции естественного соединения получим таблицу Т. a1 a2 a3 b1 b2 b3 b1 b2 b3 c1 c2 c3 Т a1 a2 a3 b1 b2 b3 c1 c2 c3 Тета-соединение – это соединение с определенным условием, в котором участвуют столбцы из каждой таблицы. Например, получить Р соединением А и В при условии L. Это означает, что два столбца будут определенным образом сравниваться, при этом может использоваться один из операторов сравнения =, ≠, <, >, ≤ , ≥ . То есть связываются таблицы, когда значения из определенных столбцов находятся в определенном отношении. Внешнее соединение расширяет естественное соединение. Сначала выполняется естественное соединение, затем, если какая-либо строка одной из исходных таблиц не подходит ни к одной строке второй таблицы, она включается в таблицу соединения, а все дополнительные столбцы заполняются пустыми значениями. R Q В результате применения операции внешнего соединения получим таблицу Т1 . a1 a2 a3 b1 b3 b4 b1 b2 b4 c1 c2 c3 Т1 a1 a3 а2 - b1 b4 b3 b2 c1 c3 - c2 Операция деления создает новую таблицу путем выбора строк одной таблицы, соответствующих каждой строке другой таблицы. Является обратной операции декартова произведения. Для нее выполняется условие: (R * S)/S=R. 3.4.2. Реляционное исчисление Реляционное исчисление базируется на теоретических основах исчисления предикатов. Использование реляционного исчисления дает возможность манипулировать с данными на уровне выходного документа, что позволяет строить удобные для пользователя языки манипулирования данными непроцедурного типа. Логика предикатов является компонентом естественного языка и содержит те составные его части, которые не содержат внутри себя нечеткостей. Напомним, что предикат – это функция, аргументы которой принимают значения из предметной области М, и значение которой суть 0 или 1. F(n) (…) : Mn ® {0,1}, Mn = M ´ M ´…´ M. Введем алфавит, используемый в языке предикатов. Сущность обозначают латинскими буквами a, b, c,…x, y, z. Множество, о котором будет идти речь, называется предметной областью и обозначается М. a, b, c,…x, y, z ÎМ Константные элементы из М обозначаются a, b, c. Буквами ближе к концу алфавита обозначаются переменные. Для обозначения предикатов будем использовать функциональные символы, в скобках через запятую – последовательность констант и переменных: F(2) (x,y), S(1) (a), H(3) (x,y,z), индекс обозначает местность предиката. Определим предикат <, он запишется - F(2) (x,y), где х, у ÎМ и М={1,2,…,9}. Значение функции, константы и переменные объединяются одним названием – терм. При построении высказываний используются логические связи Ù - коньюнкция (И), Ú - дизьюнкция (ИЛИ), ¬ - отрицание (НЕ), ® импликация (ЕСЛИ…, ТО…), n – эквивалентность (ЕСЛИ И ТОЛЬКО ЕСЛИ), Ä - дизьюнкция с исключением (ИЛИ…, ИЛИ…). Таблица 5.1 Таблица истинностей для операций a b a b A b a b a b a~b 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 Кроме того, применяются термы сравнения, имеющие общий вид xi ○ xj , где ○ - символ операции сравнения: =, ≠, <, >, ≤ , ≥. Кванторы существования $ и всеобщности " позволяют отнести высказывание ко всему рассматриваемому множеству. Рассмотрим произвольный одноместный предикат F(x). Выражение ($х)F(x) означает, что существует х, для которого F(x) истинно. 0, если при любом х F(x) ложно; ($х)F(x) = 1, если существует хотя бы один х, при котором высказывание F(x) - истина. Выражение ("х) F(x) означает, что для всех х F(x) истинен. 0, если есть хотя бы один хÎМ, при котором F(x)=0; ("х) F(x) = 1, если для всех хÎМ, F(x) =1. По определению кванторов всеобщности и существования имеем следующие соотношения: ($х)Р(x) ↔(P(b1 ) ÚP(b2 ) Ú…ÚP(bm ); ("х)P(x)↔ (P(b1 ) ÙP(b2 ) Ù…ÙP(bm ); где {b1 , b2 ,…,bm }=X – область определения аргумента х. Реляционное исчисление и предикаты В реляционном исчислении принято связывать с отношением R ( A 1 , A 2 ,…, An ) некоторый предикат Р(х1 , х2 ,…, xn ), при этом аргументы (отношения и предиката) имеют одинаковые области определения таким образом, что, если Р(а1 , а2 ,…,а n ) =1, то кортеж (а1 , а2 ,…,а n ) принадлежит отношению R , ai Î A , i = 1,…,n. В противном случае кортеж не входит в состав указанного отношения. Отсюда следует, что посредством задания некоторого предиката может быть задано и соответствующее ему отношение. На основании предикатов, операций над ними и правил строятся правильные формулы. Реляционное исчисление является одним из видов исчисления предикатов, используемого в качестве основы для создания языка запросов к базе данных. Существует реляционное исчисление кортежей и доменов. В реляционном исчислении кортежей запрос имеет вид: , где x - переменная для кортежей; f - формула исчисления. Смысл запроса состоит в том, чтобы найти множество кортежей, для которых формула f(x) - истина. Операции делятся на две большие группы: поиск (запрос) и обновление данных. Например, запросы к базе данных выражаются в виде формул: сумма R È S :{ T | R ( T ) Ú S ( T )}; произведение R Ç S:{T|R(T) Ù S(T)}; разность R-S:{T|R(T) Ù Ø S(T)}. Если вместо значений переменных для кортежей возьмем значения переменных для доменов? получим реляционное исчисление доменов. 3.5. Объектно-ориентированные БД При всей эффективности и успехе развития реляционных БД, существуют некоторые приложения, которые в результате своей сложности плохо реализуются перечисленными выше моделями данных. Объектно-ориентированные СУБД (ООСУБД) позволяют обрабатывать сложные объекты, содержат наследование и другие свойства, что делает возможным реализацию объектно-ориентированных концептуальных моделей. Объектно-ориентированный подход достаточно прост. Прежде всего вспомним, что в информатике необходимо обеспечивать тесные связи между информационными системами и системами из реального мира которые они представляют. Во многих моделях свойственна потеря семантики, поэтому всегда существует риск, что разработанная система «неправильно построена». Она либо встречает сопротивление пользователей, либо не может решить поставленную задачу. Обычно объекты реального мира обладает некоторыми свойствами и применимыми к ним функциями, которые обеспечивают их определение и классификацию. Объекты связываются друг с другом либо на межобъектной основе в соответствии с бизнес правилами, либо с помощью некоторого вида наследования свойств. Далее, к объектам реального мира применяются некоторые операции и функции. Когда эти объекты моделируются и транслируются в структуры данных, например, в реляционную, имеет место потеря семантики. Даже при реализации моделей способных «удерживать» семантику, например, «сущность-связь» - результаты не обнадеживающие. Дело в том, что сами системы БД не поддерживают семантику внутренними средствами. При разработке ООБД необходимо было создание структур, которые могли учитывать специфику приложений и удерживать семантику. Концепции ООБД: Индивидуальность объектов. Каждый объект в объектно-ориентированной (ОО) системе имеет индивидуальный идентификатор, обычно называемый ID объекта или IDentificator. Использование ID позволяет изменять значение любого атрибута объекта, в том числе и атрибутов, образующих первичный ключ, не нарушая при этом ссылок на данный объект. Концепция ID берет начало от реляционных БД. Атрибуты. Данный объект всегда имеет два аспекта: состояние и поведение. Состояние определяется множеством значений его атрибутов (или свойств, или экземплярных переменных, или полей). В ОО средах значение любого заданного атрибута должно подчиняться некоторым правилам, связанным с типом данных, с диапазоном или списком значений, а также с характеристикой, указывающей, единственное или множественное значение может быть задано и т.д. Методы. Методы описывают поведение объекта. Благодаря передачи явных сообщений между объектами системы, вызов инкапсулированных методов и доступ к атрибутам заданного объекта осуществляется в соответствии с правилами данной ООСУБД. Классы. Классы, называемые также типами, являются инструкциями, которые представляют собой группы объектов обладающих одним и тем же множеством атрибутов и методов. Классы могут быть примитивными, в этом случае не иметь атрибутов. Они могут иметь атрибуты и методы и в этом случае все объекты, относящиеся к данному классу имеют одни и те же множества атрибутов и объектов. Иерархии классов и наследование. Подклассы наследуют атрибуты суперкласса и имеют некоторые новые атрибуты, специфические для принадлежащих им объектов. Долговременное хранение. Корни ОО БД лежат в языках программирования. Создание нового долговременно хранимого объекта в языке программирования, порождает объект БД, который может использоваться непосредственно в программе без необходимости отображать его в структуры памяти языка программирования. 4. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ Существуют два основных подхода к моделированию предметной области при проектировании БД. Первый подход, называемый функциональным, требует учитывать все особенности приложения, предназначенного для работы с проектируемой базой данных. Сначала составляется подробный список всех основных операций приложения. На основе списка задач определяются необходимые таблицы и их структуры. Использование Функционального подхода позволяет максимально оптимизировать структуру БД для выполнения указанного перечня задач. Такая структура в дальнейшем менее пригодна для изменения. Второй подход объектный предлагает рассматривать предметную область без непосредственного учета требований приложений, которые будут работать с БД. При разработке структуры необходимо выделить в предметной области наиболее важные объекты. Сопоставить им отдельную таблицу. Использование второго подхода обеспечивает минимальное количество ошибок проектирования и зафиксировать реальные связи между объектами предметной области. Оба подхода используются при проектировании БД. 4.1. Выбор ключевых полей Рассмотрим шаги проектирования. Взглянем на фрагмент таблицы Customers (клиенты) из базы данных NorthWind. Она выглядит следующим образом: CustomerID CompanyName City Country ALFKI Alfreds Futterkiste Berlin Germany ANATR Ana Trujillo Emparedados y helados Mexico D.F. Mexico ANTION Antonio Moreno Taqueria Mexico D.F. Mexico AROUT Around the Horn London UK Поскольку строки в таблице не упорядочены, нам нужна колонка (или набор из нескольких колонок) для уникальной идентификации каждой строки. Такая колонка (или набор колонок) называется первичным ключом (р rimary key ). Первичный ключ любой таблицы обязан содержать уникальные непустые значения для каждой строки. Выбор первичного ключа задача очень важная. Часто в проектируемых БД содержащих сведения о клиентах, в качестве первичного ключа выбирают фамилию имя отчество, что является неверным, поскольку эти три поля достаточно часто совпадают и при вводе фамилий чаще всего возникают ошибки ввода. Если в качестве идентификатора использовать наименование компании, то это тоже чревато неприятностями поскольку, например, наименование компании АТ & Т, А.Т. and T, Ma Bell с точки зрения человека это одна компания, а с точки зрения компьютера разные. Чаще всего используют специальный дополнительный столбец, который и будет использоваться в качестве первичного ключа. Если первичный ключ состоит из более чем одной колонки, он называется составным первичным ключом ( composite primary key ). Типичная база данных обычно состоит из нескольких связанных таблиц. Ниже показан фрагмент таблицы Orders (заказы): OrderID CustomerID OrderDate Freight ShipAddress 10254 CHOPS 11.07.96 22.98 Hauptstr.31 10259 CENTC 18.07.96 3.25 Sierras de Granada 9993 10265 BLONP 25.07.96 55.28 24,place Kleber 10278 BERGS 12.08.96 92.69 Berguvsvagen 8 10280 BERGS 14.08.96 8.98 Berguvsvagen 8 ... ... ... ... ... Поле CustomerID этой таблицы содержит идентификатор клиента, разместившего данный заказ. Если нам нужно узнать, как называется компания, разместившая заказ, мы должны поискать это же значение идентификатора клиента в поле CustomerID таблицы Customers и в найденной строке прочесть значение поля CompanyName. Иными словами, нам нужно связать две таблицы, Customers и Orders, по полю CustomerID. Колонка, указывающая на запись в другой таблице, связанную с данной записью, называется внешним ключом ( foreign key ). Как видим, в случае таблицы Orders внешним ключом является колонка CustomerlD (рис. 16). Иначе говоря, внешний ключ - это колонка или набор колонок, чьи значения совпадают с имеющимися значениями первичного ключа другой таблицы. Подобное взаимоотношение между таблицами называется связью ( relationship ). Связь между двумя таблицами устанавливается путем присвоения значений внешнего ключа одной таблицы значениям первичного ключа другой. Customers Orders OrderID (PK) CostomerID (FK) OrderDate Freight ShipAddress CostomerID (PK) CompanyName City Country Рисунок 16 Первичные и внешние ключи в таблицах Customers и Orders Если каждый клиент в таблице Customers может разместить только один заказ, говорят, что эти две таблицы связаны соотношением один-к-одному ( one - to - one relationship ). Если же каждый клиент в таблице Customers может разместить ноль, один или много заказов, говорят, что эти две таблицы связаны соотношением один-ко-многим ( one - to - many relationship ) или соотношением master - detail . Подобные соотношения между таблицами используются наиболее часто. В этом случае таблица, содержащая внешний ключ, называется detail-таблицей, а таблица, содержащая первичный ключ, определяющий возможные значения внешнего ключа, называется master-таблицей. В нашем примере таблица Orders содержит внешний ключ CostomerID, который является внешним ключом. Таблица Customers является master-таблицей, а таблица Orders - detail-таблицей. Группа связанных таблиц называется схемой базы данных ( database schema ). Информация о таблицах, их колонках (имена, тип данных, длина поля), первичных и внешних ключах, а также иных объектах базы данных называется метаданными ( metadata ). Любые манипуляции с данными в базах данных, такие как выбор, вставка, удаление, обновление данных, изменение или выбор метаданных, называются запросом к базе данных ( query ). Обычно запросы формулируются на каком-либо языке, который может быть как стандартным для разных СУБД, так и зависящим от конкретной СУБД. 4.2. Ссылочная целостность Выше мы уже говорили о том, что первичный ключ любой таблицы должен содержать уникальные непустые значения для данной таблицы. Это утверждение является одним из правил ссылочной целостности ( referential integrity ). Некоторые (но далеко не все) СУБД могут контролировать уникальность первичных ключей. Ссылочная целостность обеспечивает контроль правильности ссылок и блокирует выполнение ошибочных операций. Например, при попытке присвоить первичному ключу значение, уже имеющееся в другой записи, СУБД сгенерирует диагностическое сообщение, обычно содержащее словосочетание primary key violation . Это сообщение в дальнейшем может быть передано в приложение, с помощью которого конечный пользователь манипулирует данными. Если две таблицы связаны соотношением master - detail , внешний ключ detail-таблицы должен содержать только те значения, которые уже имеются среди значений первичного ключа master-таблицы. Если корректность значений внешних ключей не контролируется СУБД, можно говорить о нарушении ссылочной целостности. В этом случае, если мы удалим из таблицы Customers запись, имеющую хотя бы одну связанную с ней detail -запись в таблице Orders, это приведет к тому, что в таблице Orders окажутся записи о заказах, размещенных неизвестно кем. Если же СУБД контролирует корректность значений внешних ключей, то при попытке присвоить внешнему ключу значение, отсутствующее среди значений первичных ключей master-таблицы либо при удалении или модификации записей master-таблицы, приводящих к нарушению ссылочной целостности, СУБД сгенерирует диагностическое сообщение. Сообщение обычно содержит словосочетание foreign key violation , которое в дальнейшем может быть передано в пользовательское приложение. 4.3. Введение в нормализацию данных Обсудим один из основных принципов проектирования данных - принцип нормализации. Нормализация представляет собой процесс реорганизации данных путем ликвидации повторяющихся групп и иных противоречий в хранении данных с целью приведения таблиц к виду, позволяющему осуществлять непротиворечивое и корректное редактирование данных. Нередко после нормализации к структуре БД добавляется одна или несколько таблиц. Теория нормализации основана на концепции нормальных форм. Говорят, что таблица находится в данной нормальной форме, если она удовлетворяет определенному набору требований. Теоретически существуют пять нормальных форм, но на практике обычно используются только первые три. Это делается с целью упрощения структуры БД. Первая нормальная форма Проиллюстрируем процесс нормализации на примере, использующем данные из базы NorthWind. Предположим, что мы регистрируем все заказанные продукты в следующей таблице: OrderlD ProductlD CustomerlD Address Quantity OrderDate 10265 17 BLONP 24, place Kleber 30 07.25.96 10265 70 BLONP 24, place Kleber 20 07.25.96 10278 44 BERGS Berguvsvagen 8 16 08.12.96 10278 59 BERGS Berguvsvagen 8 15 08.12.96 10278 63 BERGS Berguvsvagen 8 8 08.12.96 10278 73 BERGS Berguvsvagen 8 25 08.12.96 10280 24 BERGS Berguvsvagen 8 12 08.14.96 10280 55 BERGS Berguvsvagen 8 20 08.14.96 10280 75 BERGS Berguvsvagen 8 30 08.14.96 10289 3 BSBEV Fauntleroy Circus 30 08,26.96 10289 64 BSBEV Fauntleroy Circus 9 08.26.96 10297 39 BLONP 24, place Kleber 60 09.04.96 10297 72 BLONP 24, place Kleber 20 09.04.96 10308 69 ANATR