Массив (программирование)

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

Индекс массива - целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива.

Общее описание

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

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

Пример статического массива на Паскале -

WordArray: array [ Word ] of Integer ; // Статический, размер = High(Word) + 1 multiArray: array [ Byte , 1 ..5 ] of Char ; // Статический массив, 2 измерения rangeArray: array [ 5 ..20 ] of String ; // Статический массив, размер = 16

Пример статического массива на Си -

Int Array[ 10 ] ; // Статический, размер 10, базовый тип данных - целое число (int) double Array[ 12 ] [ 15 ] ; // Статический массив, 2 измерения, базовый тип данных - число // с дробной частью (double)

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

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

Объявление типа «массив» в Паскале -

Type TArrayType = array [ 0 ..9 ] of Integer ; (* Объявления типа "массив" *) var arr1, arr2, arr3: TArrayType; (* Объявление трёх переменных-массивов одного типа *)

Специфические типы массивов

Динамические массивы

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

Пример динамического массива на Delphi

ByteArray: Array of Byte ; // Одномерный массив multiArray: Array of Array of string ; // Многомерный массив

Пример динамического массива на Си

Float *array1; // Одномерный массив int **array2; // Многомерный массив array1=(float *) malloc (10 *sizeof (float ) ) ; // выделение 10 блоков по sizeof(float)байт каждый array2=(int **) malloc (16 *sizeof (int ) ) ; // выделение 16*8 блоков по sizeof(int) байт каждый for (i=0 ;i<16 ;i++) array2[ i] =(int *) malloc (8 *sizeof (int ) ) ;

Гетерогенные массивы

Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных . Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу - типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Отсутствие их поддержки в языке программирования приводит к необходимости реализации более сложных схем хранения данных. С другой стороны, реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.

Массивы массивов

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

Реализация

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

1. Под массив выделяется непрерывный блок памяти объёмом S*m 1 *m 2 *m 3 …m n , где S - размер одного элемента, а m 1 …m n - размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
2. При обращении к элементу массива A адрес соответствующего элемента вычисляется как B+S*(i 1p *m 1 +i 2p *m 2 +…+i (n-1)p *m n-1 +i np), где B - база (адрес начала блока памяти массива), i kp -значение k-го индекса, приведённое к целому с нулевым начальным смещением.

Таким образом, адрес элемента с заданным набором индексов вычисляется, так что время доступа ко всем элементам массива одинаково.

Первый элемент массива, в зависимости от языка программирования , может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based), и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых ЯП, однако этот метод был популяризирован в языках более высокого уровня языком программирорования С.

Более сложные типы массивов - динамические и гетерогенные - реализуются сложнее.

Достоинства

• легкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)
• одинаковое время доступа ко всем элементам
• малый размер элементов: они состоят только из информационного поля

Недостатки

• для статического массива - отсутствие динамики, невозможность удаления или добавления элемента без сдвига других
• для динамического и/или гетерогенного массива - более низкое (по сравнению с обычным статическим) быстродействие и дополнительные накладные расходы на поддержку динамических свойств и/или гетерогенности.
• при работе с массивом в стиле C (с указателями) и при отсутствии дополнительных средств контроля - угроза выхода за границы массива и повреждения данных

Отношения (таблицы) отвечают определенным условиям целостности . РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.

Кроме того, в состав реляционной модели данных включают теорию нормализации .

Термин «реляционный» означает, что теория основана на математическом понятии отношение (relation ). В качестве неформального синонима термину «отношение» часто встречается слово таблица . Необходимо помнить, что «таблица» есть понятие нестрогое и неформальное и часто означает не «отношение» как абстрактное понятие, а визуальное представление отношения на бумаге или экране. Некорректное и нестрогое использование термина «таблица» вместо термина «отношение» нередко приводит к недопониманию. Наиболее частая ошибка состоит в рассуждениях о том, что РМД имеет дело с «плоскими», или «двумерными» таблицами, тогда как таковыми могут быть только визуальные представления таблиц. Отношения же являются абстракциями, и не могут быть ни «плоскими», ни «неплоскими».

Для лучшего понимания РМД следует отметить три важных обстоятельства:

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

Принципы реляционной модели были сформулированы в -1970 годах Э. Ф. Коддом (E. F. Codd) . Идеи Кодда были впервые публично изложены в статье «A Relational Model of Data for Large Shared Data Banks» , ставшей классической.

Строгое изложение теории реляционных баз данных (реляционной модели данных) в современном понимании можно найти в книге К. Дж. Дейта . «C. J. Date. An Introduction to Database Systems» («Дейт, К. Дж. Введение в системы баз данных»).

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

Примечания

Литература

• Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. - 8-е изд. - М .: «Вильямс», 2006. - 1328 с. - ISBN 0-321-19784-4
• Томас Коннолли, Каролин Бегг Базы данных. Проектирование, реализация и сопровождение. Теория и практика = Database Systems: A Practical Approach to Design, Implementation, and Management Third Edition. - 3-е изд. - М .: «Вильямс», 2003. - С. 1436. - ISBN 0-201-70857-4
• Кузнецов С. Д. Основы баз данных. - 2-е изд. - М .: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. - 484 с. - ISBN 978-5-94774-736-2
• Когаловский М.Р. Энциклопедия технологий баз данных. - М .: Финансы и статистика, 2002. - С. 800. - ISBN 5-279-02276-4

Wikimedia Foundation . 2010 .

Смотреть что такое "Реляционная модель данных" в других словарях:

Разработанная Э.Коддом в 1970г. логическая модель данных, описывающая: структуры данных в виде (изменяющихся во времени) наборов отношений; теоретико множественные операции над данными: объединение, пересечение, разность и декартово произведение; … Финансовый словарь

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

Реляционная модель данных - 61. Реляционная модель данных Модель данных, основанная на представлении данных в виде набора отношений, каждое из которых представляет собой подмножество декартова произведения определенных множеств, и манипулировании ими с помощью множества… … Словарь-справочник терминов нормативно-технической документации

Реляционная база данных база данных, основанная на реляционной модели данных. Слово «реляционный» происходит от англ. relation (отношение). Для работы с реляционными БД применяют реляционные СУБД. Использование реляционных баз… … Википедия

реляционная база данных - База данных, реализованная в соответствии с реляционной моделью данных. [ГОСТ 20886 85] реляционная БД База данных, логически организованная в виде набора отношений ее компонентов. Характерной особенностью реляционной базы данных является… … Справочник технического переводчика

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

В классической теории баз данных, модель данных есть формальная теория представления и обработки данных в системе управления базами данных (СУБД), которая включает, по меньшей мере, три аспекта: 1) аспект структуры: методы описания типов и… … Википедия

Иерархическая модель данных представление базы данных в виде древовидной (иерархической) структуры, состоящей из объектов (данных) различных уровней. Между объектами существуют связи, каждый объект может включать в себя несколько объектов… … Википедия

Необходимо перенести в эту статью содержимое статьи Сетевая СУБД и поставить оттуда перенаправление. Вы можете помочь проекту, объединив статьи (cм. инструкцию по объединению). В случае необходимости обсуждения целесообразности объединения,… … Википедия

- (англ. Associative model of data) это предложенная Саймоном Уильямсом:2 модель представления данных, в которой база данных состоит из двух типов структур данных элементов и ссылок, хранимых в единой однородной общей… … Википедия

Локальная модель

Файл-серверная модель

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

Количество клиентов ограничено десятками.

Плюсы:

1. Многопользовательский режим работы с данными;

2. Удобство централизованного управления доступом;

3. Низкая стоимость разработки;

Минусы:

1. Низкая производительность;

2. Низкая надежность;

3. Слабые возможности расширения;

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

надежность приложения.

Модель удаленного доступа

Модель сервера данных

Модель телеобработки

Модель сервера приложений

2.​ Архитектура базы данных. Физическая и логическая независимость

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

В процессе научных исследований, посвященных тому, как именно должна быть устроена СУБД , предлагались различные способы реализации. Самым жизнеспособным из них оказалась предложенная американским комитетом по стандартизации ANSI (American National Standards Institute) трехуровневая система организации БД , изображенная на рис. 2:

Рис. 2. Трехуровневая модель системы управления базой данных, предложенная ANSI

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

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

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

Эта архитектура позволяет обеспечить логическую (между уровнями 1 и 2) и физическую (между уровнями 2 и 3) независимость при работе с данными. Логическая независимость предполагает возможность изменения одного приложения без корректировки других приложений, работающих с этой же базой данных. Физическая независимость предполагает возможность переноса хранимой информации с одних носителей на другие при сохранении работоспособности всех приложений, работающих с данной базой данных. Это именно то, чего не хватало при использовании файловых систем.

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

3.​ Модели данных.

Основа информационной системы, объект ее обработки - база данных (БД). База данных - это совокупность сведений о конкретных объектах реального мира в какой-либо предметной области или разделе предметной области. Например, база данных по вузам (высшее образование), база данных по лекарственным препаратам (медицина), база данных по автомобилям (автомагазин), база данных по стройматериалам (склад) и т.п. Синоним термина «база данных» - «банк данных».

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

Различают три основных типа моделей данных: иерархическую, сетевую и реляционную .

Иерархическая структура представляет собой совокупность элементов, в которой данные одного уровня подчинены данным другого уровня, а связи между элементами образуют древовидную структуру. В такой структуре исходные элементы порождают другие элементы, причем эти элементы в свою очередь порождают следующие элементы и т.д. Существенно то, что каждый порожденный элемент имеет только одного «родителя». Обратите внимание, что в иерархической структуре порождающим элементом может быть не объект сам по себе, а только конкретный экземпляр объекта. Примером иерархической базы данных может служить генеалогическое древо вашей семьи.

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

4.​ Основные определения реляционной модели данных

Реляционная модель данных – логическая модель данных. Впервые была предложена британским учёным сотрудником компании IBM Эдгаром Франком Коддом (E. F. Codd). В настоящее время эта модель является фактическим стандартом, на который ориентируются практически все современные коммерческие СУБД.

Кристофер Дейт определил три составные части реляционной модели данных:

§ структурная

§ манипуляционная

§ целостная

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

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

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

Структура реляционной модели данных

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

Основные компоненты реляционного отношения

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

В примере, показанном на рисунке, атрибуты "Оклад" и "Премия" определены на домене "Деньги". Поэтому, понятие домена имеет семантическую нагрузку: данные можно считать сравнимыми только тогда, когда они относятся к одному домену. Таким образом, в рассматриваемом нами примере сравнение атрибутов "Табельный номер" и "Оклад" является семантически некорректным, хотя они и содержат данные одного типа.

Именованное множество пар "имя атрибута – имя домена" называется схемой отношения . Мощность этого множества - называют степенью или "арностью" отношения. Набор именованных схем отношений представляет из себя схему базы данных .

Атрибут, значение которого однозначно идентифицирует кортежи, называется ключевым (или просто ключом ). В нашем случае ключом является атрибут "Табельный номер", поскольку его значение уникально для каждого работника предприятия. Если кортежи идентифицируются только сцеплением значений нескольких атрибутов, то говорят, что отношение имеет составной ключ. Отношение может содержать несколько ключей. Всегда один из ключей объявляется первичным, его значения не могут обновляться. Все остальные ключи отношения называются возможными ключами .

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

5.​ Жизненный цикл базы данных. Этапы ЖЦ БД.

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

1. Исследование и анализ проблемы, для решения которой создаётся база данных.
2. Построение Инфологической и Даталогической модели.
3. Нормализация полученных Инфологических и Даталогических моделей. По окончании этого этапа, как правило получают заготовки таблицы БД и набор связей между ними (первичные и вторичные ключи)
4. Проверка целостности БД (Целостность базы данных)
5. Выбор физического способа хранения и эксплуатации (тех. средства) базы данных.
6. Проектирование входных и выходных форм.
7. Разработка интерфейса приложения.
8. Функциональное наполнение приложения
9. Отладка: проверка на корректность работы функционального наполнения системы
10. Тестирование: тест на корректность ввода вывода данных, тест на максимальное количество активных сессий и т. д.
11. Ввод в эксплуатацию: отладка ИТ-инфраструктуры, обучение пользователей и ИТ-персонала.
12. При необходимости добавления выходных форм и дополнительной функциональности. В случае если необходимы более серьёзные изменения, следует повторить все шаги с первого.
13. Вывод из эксплуатации: перенос данных в новую СУБД.

6.​ Основные свойства единиц информации. Составная единица информации. Описание структуры СЕИ. Показатели

Составная единица информации (СЕИ) – это набор из атрибутов и, возможно других СЕИ. Определение СЕИ рекурсивно. База данных тоже ЕИ. Множество атрибутов объединяются в одну СЕИ по следующим признакам:

Соответствующие атрибуты описывают один и тот же факт или экономический процесс

Значения атрибутов, входящих в СЕИ, возникают одновременно, связаны арифметическими или логическими отношениями.

Простейшая характеристика СЕИ представлена именем, структурой и значением.

Имя – обозначение СЕИ в процессах обработки информации

Структура – вхождение одних единиц информации в состав других единиц

информации.

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

Описание структуры СЕИ

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

Показатель

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

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

В состав показателя должны входить один атрибут- основание и несколько атрибутов-признаков, однозначно характеризующих условия существования основания. Как единица информации показатель является разновидностью СЕИ.

Структура показателя:

П.(Р1, Р2,...,Рк, Q),

где Q - атрибут-основание, Р1, Р2,...,Рк - атрибуты- признаки. Таким образом, в показателях отражаются количественные свойства объектов и процессов.

Минимальный набор атрибутов показателя должен содержать:

1. Атрибуты отображающие идентификаторы объектов

2. Атрибуты, отображающие признак времени

3. Атрибут, отображающий некоторое количественное свойство объекта или взаимодействия.

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

1. Если значение атрибута является исходным данным для вычислений или результатом арифметической операции, то это основание

2. Если значение атрибута текстовое, то это признак

3. Если атрибут обозначает предмет, это признак

4. Если атрибут в некотором показателе является признаком, то он будет играть эту роль и в других показателях.

5. Если показатели описывают сходные процессы, то их призначные части совпадают.

6. Если основание показателя вычисляется по значениям других оснований, то набор признаков такого показателя есть объединение признаков, связанных с этими основаниями.

7.​ Операции над СЕИ: нормализация, свертка, декомпозиции, композиция, выборка, корректировка.

Нормализация – операция перехода от СЕИ с произвольной структурой к СЕИ с двухуровневой структурой. Одновременно происходит перекомпоновка значений СЕИ. Общее число значений в нормализованной СЕИ равно произведению размерностей всех СЕИ в исходном описании структуры.

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

Декомпозиция – это операция преобразования исходной СЕИ в несколько СЕИ с различными структурами. Множество атрибутов СЕИ до декомпозиции должно совпадать с множеством атрибутов после декомпозиции.

Композиция – это операция преобразования нескольких составных единиц информации с различными структурами в одну СЕИ. Операция композиции обратна декомпозиции и точно определяется только для нормализованных исходных составных единиц информации. Условие выполнения операции композиции двух СЕИ – это наличие атрибутов, по которым они связаны.

Выборка – это операция выделения подмножества значений составной единицы информации, которая удовлетворяет заранее поставленным условиям выборки.

Корректировка – это выполнение одной из следующих операций:

1. Добавление нового значения

2. Исключение существующего значения

3. Замена некоторого значения на новое

Возможны более сложные режимы корректировки, например, внесение изменений в

несколько СЕИ одновременно.

8.​ Два класса отношений: объектное и связное. Ключи отношений. Индексы.

Операции над отношениями:

1. Традиционные операции (объединение, пересечение, разность, декартово произведение, деление)

2. Специальные реляционные операции (проекция, соединение, выбор) Эти операции реализуются с помощью специальных языков, которые делятся на два класса:

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

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

Различают 2 класса отношений в зависимости от содержания:

1. Объектное отношение

2. Связное отношение

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

1. Запись должна однозначно определяться значением ключа

2. Никакое поле нельзя удалить из ключа, не нарушая при этом свойства однозначной идентификации

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

Ключи в связных отношениях называются внешними, т.к. они являются первичными ключами других отношений. Реляционная модель накладывает на внешние ключи ограничение для обеспечения целостности, называемые ссылочной целостностью. Это значит, что каждому внешнему ключу должна соответствовать строка какого-либо объектного отношения, иначе окажется, что внешний ключ ссылается на неизвестный объект. Ещё одно ограничение на отношения в реляционной БД говорит о том, что каждое отношение должно иметь простые атрибуты, т.е. содержать атомарные, неделимые значения.

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

9.​ Нормализация отношений. Требования при группировке атрибутов в отношения в реляционной БД.

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

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

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

· множество отношений должно обеспечивать минимальную избыточность представления информации,

· корректировка отношений не должна приводить к двусмысленности или потере информации,

· перестройка набора отношений при добавлении в базу данных новых атрибутов должна быть минимальной.

Удовлетворение этих требований достигается нормализацией отношений БД.

10.​ Функциональные зависимости. Нормальные формы.

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

Например, пусть в отношении R1 имеются 2 атрибута А и В. Атрибут В функционально зависит от атрибута А, если в любой момент времени каждое значение атрибута А соответствует единственному значению атрибута В. Обозначается А→В (если нет зависимости, то А В).

Если отношение находится в 1НФ, то все не ключевые атрибуты функционально зависят от ключа, но степень зависимости может быть различной.

Если не ключевой атрибут зависит только от части ключа, то говорят о частичной зависимости .

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

Каждая НФ ограничена определенным типом функциональной зависимости и устраняет аномалии при выполнении Оп при рассмотрении БД.

Такие частичные зависимости приводят, например, к следующим аномалиям :

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

2) проблема контроля избыточности данных, т.к. изменение, например, расценки влечет за собой

необходимость поиска и изменения значений расценки во всех кортежах;

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

Отношение находится в 2НФ, если оно находится в 1НФ, и каждый не ключевой атрибут функционально полно зависит от составного ключа. Чтобы устранить частичную зависимость и привести отношение ко 2НФ нужно разложить его на несколько отношений следующим образом:

1) построить проекцию без атрибутов, которые находятся в частичной зависимости от составного ключа;

2) построить проекцию на часть составного ключа и атрибуты, зависящие от этой части.

Если для атрибутов A, B,C выполняются условия A→B и B→C, но обратная зависимость отсутствует, то С зависит от А транзитивно, т.е. можно говорить о транзитивной зависимости. Наличие транзитивных зависимостей порождает неудобства и аномалии следующего характера:

1) Дублирование информации о телефоне для нескольких рабочих

2) Проблема поиска и контроля при изменении номера телефона.

Таким образом, 2НФ также может требовать дальнейших преобразований.

Отношение находится в 3НФ, если оно находится во 2НФ и нем отсутствуют транзитивные зависимости не ключевых атрибутов от ключа. БД находится в 3НФ, если все ее отношения имеют 3НФ.

Алгоритм получения 3НФ:

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

Алгоритм получения отношений в ЗНФ обладает следующими свойствами:

Сохраняет все первоначальные функциональные зависимости, т.е. зависимость, справедливая в R, справедлива и в одном из производных отношений. Это гарантирует получение осмысленных отношений с легко интерпретируемой структурой,

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

Результат декомпозиции в ЗНФ обычно содержит меньше значений атрибутов, чем исходное отношение R (происходит уменьшение избыточности

Алгоритм состоит из следующий шагов:

1) Получить исходное множество функциональных зависимостей для атрибутов рассмотренной БД.

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

3) Для каждой функциональной зависимости, полученной на 2 шаге создать проекцию исходных отношений, R[X], где X – объединение атрибутов из левой и правой частей функциональной зависимостей.

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

БКНФ (Бойса-Кодда)

Считается, что отношение находится в нормальной форме БК, если оно находится в 3НФ и в нем отсутствуют зависимости ключевых атрибутов от неключевых.

Отношение находится в 4НФ, если оно находится в НФБК и в нем отсутствуют многозначные зависимости не являющиеся функциональными.

5НФ . Отношение R находится в пятой нормальной форме (5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной .

Зависимость соединения называется нетривиальной зависимостью соединения , если выполняется два условия:

11.​ Операции над отношениями: объединение, пересечение, разность, декартово произведение.

Отношения

В реляционной алгебре в качестве операндов выступают отношения, а основными операциями, выполняемыми над отношениями, являются:

· объединение

· пересечение

· разность

· декартово произведение

· деление

· проекция

· соединение

Введем некоторые понятия.

Степенью отношения называется число входящих в него атрибутов.

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

ОБЪЕДИНЕНИЕ (R U S) отношений R и S представляет собой множество кортежей, которые принадлежат R или S, либо им обоим. Операция объединения выполняется над двумя совместимыми отношениями.

ПЕРЕСЕЧЕНИЕ. Результат пересечения R и S содержит только те кортежи первого отношения R, которое есть во втором S.

РАЗНОСТЬ. Результат вычитания (R-S) включает только те кортежи первого отношения R, которых нет во втором S.

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ (R x T). Здесь операнды-отношения R и T могут иметь разные схемы: Степень результирующего отношения (R x T) равна сумме степеней отношений операндов (R и T), а мощность - произведение их мощностей.

12.​ Операции над отношениями: деление.

ДЕЛЕНИЕ (R / T). Операция в некотором смысле обратна операции "декартово произведение". Отношение "делимое" (R) должно содержать подмножество атрибутов отношения "делитель" (T). Результирующее отношение (R / T) содержит только те атрибуты делимого, которых нет в делителе. В него включают только те кортежи, декартово произведение которых с делителем содержатся в делимом.

13.​ Операции над отношениями: проекция, выборка, соединение.

ПРОЕКЦИЯ. Эта операция в отличие от всех предыдущих является унарной, т.е. выполняется над одним отношением (R). Результирующее отношение П (R) включает часть атрибутов исходного, на которые выполняется проекция. Кортежи-дубликаты отсутствуют.

Где X – список атрибутов в схеме отношения.

СОЕДИНЕНИЕ. Операция соединения выполняется над двумя отношениями (R и S). В каждом отношении выделяется атрибут, по которому будет производиться соединение. В качестве атрибута для соединения выберем атрибут B. Результирующее отношение включает все атрибуты первого отношения (R) и второго отношения (S):

ВЫБОР. Операция выполняется над одним отношением (R). Результирующее отношение (OB=b(R)) содержит подмножества кортежей, выбранных по некоторому условию (B = b).

14.​ Проектирование БД (архитектура ANSI / SPARC)

Архитектура ANSI-SPARC (также 3х-уровневая архитектура ) определяет принцип, согласно которому рекомендуется строить системы управления базами данных(СУБД).

Проект архитектуры был выдвинут в 1975 году подкомитетом SPARC ANSI.

3 уровня СУБД:

1. внешний (пользовательский)
2. промежуточный (концептуальный )
3. внутренний (физический)

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

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

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

15.​ Инфологическое моделирование. Модель «сущность-связь» (ER-модель)

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

ER-модель (Entity-Relationship Model – модель «сущность-связь») - представление ИМ, основывающееся на структурных элементах «сущность», «свойство», «связь».

Сущности и свойства

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

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

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

Простое свойство - состоит из одного компонента с независимым существованием.

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

Единичное свойство - может содержать только одно значение определенного типа для любого экземпляра сущности.

Множественное свойство - может содержать несколько значений определенного типа для любого экземпляра сущности.

Связь - описание связанности двух сущностей и их экземпляров.

Множественность (кардинальность) указывает для каждой стороны количество экземпляров сущности, которое может быть одновременно связано с одним экземпляром другой сущности. Варианты связи по множественности: 1:1, 1:М, М:М.

1. отношение “один к одному” (1:1) означает, что каждая запись одной таблицы соответствует только одной записи в другой таблице;

2. отношение “один ко многим” (1:М) возникает, когда одна запись взаимосвязана со многими другими;

3. отношение “многие к одному” означает, что многие записи связаны с одной (М:1);

4. отношение “многие ко многим” (M:N) возникает между двумя таблицами в тех случаях, когда:

· одна запись из первой таблицы может быть связана более чем с одной записью из второй таблицы;

· одна запись из второй таблицы может быть связана более чем с одной записью из первой таблицы.

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

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

Ассоциация может использоваться для:

· Реализации связи М:М

· Связывания трех и более сущностей

· Хранения дополнительной информации о связи

· Последовательность инфологического проектирования:

· Определение сущностей

· Установление подчиненности сущностей и формирование сложных

объектов

· Установление связей и определение ассоциаций

· Определение свойств сущностей

· Определение идентификаторов

16.​ Критерии оценки качества логической модели данных. Переход к реляционной модели данных (6 правил)

Критерии оценки качества логической модели данных

Адекватность базы данных предметной области
База данных должна адекватно отражать предметную область. Это означает, что должны выполняться следующие условия:
1. Состояние базы данных в каждый момент времени должно соответствовать состоянию предметной области.
2. Изменение состояния предметной области должно приводить к соответствующему изменению состояния базы данных
3. Ограничения предметной области, отраженные в модели предметной области, должны некоторым образом отражаться и учитываться базе данных.
Легкость разработки и сопровождения базы данных
Практически любая база данных, за исключением совершенно элементарных, содержит некоторое количество программного кода в виде триггеров и хранимых процедур.
Хранимые процедуры - это процедуры и функции, хранящиеся непосредственно в базе данных в откомпилированном виде и которые могут запускаться пользователями или приложения-ми, работающими с базой данных.
Триггеры - это хранимые процедуры, связанные с некоторыми событиями, происходящими во время работы базы данных. В качестве таких событий выступают операции вставки, обновления и удаления строк таблиц. Если в базе данных определен некоторый триггер, то он запускается автоматически всегда при возникновении события, с которым этот триггер связан.
Скорость операций обновления данных (вставка, обновление, удаление)
На уровне логического моделирования мы определяем реляционные отношения и атрибуты этих отношений. На этом уровне мы не можем определять какие-либо физические структуры хранения (индексы, хеширование и т.п.). Единственное, чем мы можем управлять - это распределением атрибутов по различным отношениям. Можно описать мало отношений с большим количеством атрибутов, или много отношений, каждое из которых содержит мало атрибутов. Таким образом, необходимо попытаться ответить на вопрос - влияет ли количество отношений и количество атрибутов в отношениях на скорость выполнения операций обновления данных. Такой вопрос, конечно, не является достаточно корректным, т.к. скорость выполнения операций с базой данных сильно зависит от физической реализации базы данных. Тем не менее, попытаемся качественно оценить это влияние при одинаковых подходах к физическому моделированию.
Таким образом, можно принять допущение, что чем больше атрибутов имеют отношения, разработанные в ходе логического моделирования, тем медленнее будут выполняться операции обновления данных, за счет затраты времени на перестройку большего количества индексов.
Скорость операций выборки данных
Одно из назначений базы данных - предоставление информации пользователям. Информация извлекается из реляционной базы данных при помощи оператора SQL - SELECT. Одной из наиболее дорогостоящих операций при выполнении оператора SELECT является операция соединение таблиц. Таким образом, чем больше взаимосвязанных отношений было создано в ходе логического моделирования, тем больше вероятность того, что при выполнении запросов эти отношения будут соединяться, и, следовательно, тем медленнее будут выполняться запросы. Таким образом, увеличение количества отношений приводит к замедлению выполнения операций выборки данных, особенно, если запросы заранее неизвестны.

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

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

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

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

Правило 4 . Если степень бинарной связи 1:N, и класс принадлежности n-связной сущности является обязательным, то достаточно построить два отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения, а ключ 1-связной сущности добавляется в отношение для n -связной сущности в качестве атрибута.

Правило 5. Если степень бинарной связи 1:N и класс принадлежности n-связной сущности не является обязательным, то необходимо построить три отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи. Ключи сущностей должны быть атрибутами последнего отношения.

Отметим, что если степень бинарной связи 1:N, то фактором, определяющим выбор одного из правил (правила 4, 5), является класс принадлежности n-связной сущности. Класс принадлежности 1-связной сущности не влияет на конечный результат декомпозиции. В ситуации правила 4 имеет место проблема нуль-значений по атрибуту Предмет, в ситуации правила 5 имеет место проблема нуль-значений по атрибутам Предмет и Преподаватель. Поэтому во избежание дублирования и нуль-значений в ситуации правил 4 и 5 необходимо строить два и три результирующих отношения соответственно. Миграция ключа 1-связной сущности выполняется для восстановления исходного отношения при соединении.

Если степень бинарной связи N:M, то во избежание дублирования и нуль-значений необходимо всегда строить три отношения. Сформулируем шестое правило.

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

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

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

Поддержка целостности в реляционной модели данных в ее классическом понимании включает в себя 3 аспекта.

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

<имя атрибута>IS NULL и <имя атрибута> IS NOT NULL.

Если в данном кортеже (в данной строке) указанный атрибут имеет неопределенное значение, то предикат IS NULL принимает значение TRUE (Истина), а предикат IS NOT NULL - FALSE(Ложь), в противном случае предикат IS NULL принимает значение FALSE, а предикат IS NOT NULL принимает значение TRUE. Ведение Null значений вызвало необходимость модификации классической двузначной логики и превращения ее в трехзначную. Все логические операции, производимые с неопределенными значениями, подчиняются этой логике в соответствии с заданной таблицей истинности.

Таблица 8.1.Таблица истинности для логических операций с неопределенными значениями

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

Логическое выражение > IS {TRUE | FALSE | UNKNOWN}

18.​ Принципы поддержки целостности в реляционных моделях данных. Языковая целостность. Ссылочная целостность. (продолжение 17 вопроса)

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

В-третьих , это поддержка ссылочной целостности (Declarative Referential Integrity, DRI), означает обеспечение одного из заданных принципов взаимосвязи между экземплярами кортежей взаимосвязанных отношений:

• кортежи подчиненного отношения уничтожаются при удалении кортежа основного отношения, связанного с ними.
• кортежи основного отношения модифицируются при удалении кортежа основного отношения, связанного с ними, при этом на месте ключа родительского отношения ставится неопределенное Null значение.

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

19.​ Семантическая поддержка целостности. Виды декларативных ограничений целостности

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

1. В библиотеке должны быть записаны читатели не моложе 17 лет.
2. В библиотеке присутствуют книги, изданные начиная с 1960 по текущий год.
3. Каждый читатель может держать на руках не более 5 книг.
4. Каждый читатель при регистрации в библиотеке должен дать телефон для связи: он может быть рабочим или домашним.

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

Выделяются следующие виды декларативных ограничений целостности:

§ Ограничения целостности атрибута: значение по умолчанию, задание обязательности или необязательности значений (Null), задание условий на значения атрибутов.

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

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

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

Декларативные ограничения целостности относятся к ограничениям, которые являются немедленно проверяемыми. Есть ограничения целостности, которые являются откладываемыми. Эти ограничения целостности поддерживаются механизмом транзакций и триггеров.

20.​ Транзакции. Триггеры и хранимые процедуры.

Транзакция - это последовательность операторов манипулирования данными, выполняющаяся как единое целое (все или ничего) и переводящая базу данных из одного целостного состояния в другое целостное состояние.

Транзакция обладает четырьмя важными свойствами, известными как свойства А СИД:

(А) Атомарность. Транзакция выполняется как атомарная операция - либо выполняется вся транзакция целиком, либо она целиком не выполняется.

(С) Согласованность. Транзакция переводит базу данных из одного согласованного (целостного) состояния в другое согласованное (целостное) состояние. Внутри транзакции согласованность базы данных может нарушаться.

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

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

Набор примитивов

- BEGIN_TRANSACTION ; границы

- END_TRANSACTION ; транзакции

- ABORT_TRANSACTION;

- WRITE.

Транзакция обычно начинается автоматически с момента присоединения пользователя к СУБД и продолжается до тех пор, пока не произойдет одно из следующих событий:

Подана команда BEGIN TRANSACTION;

Подана команда ABORT_TRANSACTION (откатить транзакцию);

Произошло отсоединение пользователя от СУБД;

Произошел сбой системы.

Триггер - это отдельная хранимая в БД подпрограмма, связанная с таблицей или представлением, которая автоматически включается, когда в таблицу или представление вставляется (триггер добавления), модифицируется (триггер модификации) или удаляется (триггер удаления) строка.

Триггеры позволяют:

Контролировать входные данные, обеспечивая достоверность информации и ее логическую непротиворечивость.

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

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

Автоматически уведомлять об изменениях в БД, используя события, создаваемые триггерами.

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

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

SQL для триггеров и хранимых процедур содержит множество операторов императивного программирования:

Конкатенацию строк,

Арифметические операции,

Операции сравнения,

Логические (not, and, or),

Операторы структурного программирования (IF, FOR, WHILE),

Объявление переменных (DECLARE),

Эти операторы используются совместно с операторами декларативного программирования INSERT, UPDATE, DELETE и SELECT.

В современных СУБД код хранимых процедур и триггеров может писаться на смеси диалектов SQL и языков высокого уровня, например, в Oracle – на PL/SQL или Java. Фактически запросы, написанные на декларативном языке, вкладываются в процедуры, написанные на императивном языке

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

Структурной части.

Целостной части.

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

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

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

Манипуляционная часть описывает два эквивалентных способа манипулирования реляционными данными - реляционную алгебру и реляционное исчисление .

В данной главе рассматривается структурная часть реляционной модели.

Типы данных

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

Важно! Реляционная модель требует, чтобы типы используемых данных были простыми .

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

Простые типы данных.

Структурированные типы данных.

Ссылочные типы данных.

Простые типы данных

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

Логический.

Строковый.

Численный.

Различные языки программирования могут расширять и уточнять этот список, добавляя такие типы как:

• Вещественный.

• Денежный.

  Перечислимый.

  Интервальный.

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

Структурированные типы данных

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

• Записи (Структуры)

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

называемое множеством индексов. Отображение

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

Запись (или структура) представляет собой кортеж из некоторого декартового произведения множеств. Действительно, запись представляет собой именованный упорядоченный набор элементов , каждый из которых принадлежит типу . Таким образом, запись есть элемент множества . Объявляя новые типы записей на основе уже имеющихся типов, пользователь может конструировать сколь угодно сложные типы данных.

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

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

Работая же с простыми типами данных, например с числовыми, мы манипулируем ими как неделимыми целыми объектами. Чтобы "увидеть", что числовой тип данных на самом деле сложен (является набором битов), нужно перейти на более низкий уровень абстракции. На уровне программного кода это будет выглядеть как ассемблерные вставки в код на языке высокого уровня или использование специальных побитных операций.

Ссылочные типы данных

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

Типы данных, используемые в реляционной модели

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

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

Именно так в некоторых пост-реляционных СУБД реализована работа со сколь угодно сложными типами данных, создаваемых пользователями.

Домены

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

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

Домен имеет уникальное имя (в пределах базы данных).

Домен определен на некотором простом типе данных или на другом домене.

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

Домен несет определенную смысловую нагрузку .

Например, домен , имеющий смысл "возраст сотрудника" можно описать как следующее подмножество множества натуральных чисел:

Отличие домена от понятия подмножества состоит именно в том, что домен отражает семантику , определенную предметной областью. Может быть несколько доменов, совпадающих как подмножества, но несущие различный смысл. Например, домены "Вес детали" и "Имеющееся количество" можно одинаково описать как множество неотрицательных целых чисел, но смысл этих доменов будет различным, и это будут различные домены.

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

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

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

Замечание . Не всегда очевидно, как задать логическое условие, ограничивающее возможные значения домена. Я буду благодарен тому, кто приведет мне условие на строковый тип данных, задающий домен "Фамилия сотрудника". Ясно, что строки, являющиеся фамилиями не должны начинаться с цифр, служебных символов, с мягкого знака и т.д. Но вот является ли допустимой фамилия "Ггггггыыыыы"? Почему бы нет? Очевидно, нет! А может кто-то назло так себя назовет. Трудности такого рода возникают потому, что смысл реальных явлений далеко не всегда можно формально описать. Просто мы, как все люди, интуитивно понимаем, что такое фамилия, но никто не может дать такое формальное определение, которое отличало бы фамилии от строк, фамилиями не являющимися. Выход из этой ситуации простой - положиться на разум сотрудника, вводящего фамилии в компьютер.

Отношения, атрибуты, кортежи отношения

Определения и примеры

Фундаментальным понятием реляционной модели данных является понятие отношения . В определении понятия отношения будем следовать книге К. Дейта .

Определение 1. Атрибут отношения есть пара вида <Имя_атрибута: Имя_домена>.

Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

Определение 2 . Отношение , определенное на множестве доменов (не обязательно различных), содержит две части: заголовок и тело.

Заголовок отношения содержит фиксированное количество атрибутов отношения:

Тело отношения содержит множество кортежей отношения. Каждый кортеж отношения представляет собой множество пар вида <Имя_атрибута: Значение_атрибута>:

таких что значение атрибута принадлежит домену

Отношение обычно записывается в виде:

или короче

,

или просто

Число атрибутов в отношении называют степенью (или -арностью ) отношения.

Мощность множества кортежей отношения называют мощностью отношения.

Возвращаясь к математическому понятию отношения, введенному в предыдущей главе, можно сделать следующие выводы:

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

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

Пример 1 . Рассмотрим отношение "Сотрудники" заданное на доменах "Номер_сотрудника", "Фамилия", "Зарплата", "Номер_отдела". Т.к. все домены различны, то имена атрибутов отношения удобно назвать так же, как и соответствующие домены. Заголовок отношения имеет вид.

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

Элементы реляционной модели

Реляционная модель данных (РМД) некоторой предметной области представляет собой набор отношений, изменяющихся во времени. При создании информационной системы совокупность отношений позволяет хранить данные об объектах предметной области и моделировать связи между ними. Элементы РМД и формы их представления приведены в табл. 19.1.

Таблица 19.1

Элементы реляционной модели

Важнейшим является понятие отношения, которое представляет собой двумерную таблицу, содержащую некоторые данные.

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

Атрибуты представляют собой свойства, характеризующие сущность.

Математически отношение можно описать следующим образом. Пусть даны n множеств D1, D2, D3, ... Dn, тогда отношение R есть множество упорядоченных кортежей ,гдеdk ∈ Dk, a D1, D2, D3,... Dn - домены отношения R.

На рис. 19.2 приведен пример представления отношения СОТРУДНИК.

Множество всех значений каждого атрибута отношения образует домен. Отношение СОТРУДНИК включает 4 домена. Домен 1 содержит фамилии всех сотрудников,домен 2 - номера всех отделов фирмы,домен 3 - название всех должностей,домен 4 - даты рождения всех сотрудников. Каждый домен образует значения одного типа, например, числовые или символьные.

Отношение СОТРУДНИК содержит 3 кортежа. Кортеж рассматриваемого отношения состоит из 4-х элементов, каждый из которых выбирается из соответствующего домена. Каждому кортежу соответствует строка таблицы.

Схема отношения представляет собой список имен атрибутов. Например, для приведенного примера схема отношения имеет вид СОТРУДНИК(ФИО, Отдел, Должность, Д_Рождения).

Рис. 19.2. Представление отношения СОТРУДНИК

Ключом отношения, илипервичным ключом, называется атрибут отношения, однозначно идентифицирующий каждый из его кортежей. Например, в отношении СОТРУДНИК(ФИО, Отдел, Должность, Д_Рождения) ключевым является атрибут ФИО.Ключ может бытьсоставным, т.е. состоять из нескольких атрибутов.

Существует также понятие внешнего ключа. С помощью внешних ключей устанавливаются связи между отношениями. Например, имеются два отношения СТУДЕНТ (ФИО. Группа, Специальность) и ПРЕДМЕТ(Назв.Пр. Часы), которые связаны отношением СТУДЕНТ_ПРЕДМЕТ(ФИО. Назв.Пр. Оценка) (рис. 19.3). В связующем отношении атрибуты ФИО и Назв.пр образуют составной ключ. Эти атрибуты представляют собойвнешние ключи, являющиеся первичными ключами других отношений.

Рис. 19.3. Связь отношений

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

Наиболее часто таблица с отношением размещается в отдельном файле. В некоторых СУБД, например, Microsoft Access, в одном фарше размещается полностью база данных.

Ограничения и операции над отношениями

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

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

В таблице не должно быть столбцов с повторяющимися именами.

Все строки одной таблицы должны иметь одну структуру, соответствующую именам и типам столбцов.

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

Порядок размещения строк в таблице может быть произвольным.

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

Основной единицей обработки данных в реляционных БД является отношение, а не отдельные его кортежи (записи), как это принято в традиционных языках программирования.

Операции, выполняемые над отношениями, можно разделить на две группы.

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

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

В различных СУБД реализована некоторая часть этих операций, определяющая в какой-то мере возможности данной СУБД и сложность реализации запросов к БД.

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

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

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

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