Модели на основе инвертированных списков

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

• Организация доступа к данным на основе инвертированных списков используется практически во всех современных реляционных СУБД, но в этих системах пользователи не имеют непосредственного доступа к инвертированным спискам (индексам).

Структуры данных

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

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

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

Манипулирование данными

Поддерживаются два класса операторов:

1)Операторы, устанавливающие и возвращающие адрес записи, среди которых:

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

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

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

Ограничения целостности

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

 

Достоинства и недостатки ранних СУБД

Достоинства:

• Развитые средства управления данными во внешней памяти на низком уровне;

• Возможность построения вручную эффективных прикладных систем;

• Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

• Слишком сложно пользоваться;

• Необходимы знания о физической организации;

• Прикладные системы зависят от этой организации;

• Логика перегружена деталями организации доступа к БД.

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

 

Пример: расписание движения самолетов

Фундаментальные свойства отношений

1.Отсутствие кортежей-дубликатов.

 

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

 

2.Отсутствие упорядоченности кортежей.

 

3.Отсутствие упорядоченности атрибутов.

 

4.Атомарность значений атрибутов. Это существенно упрощают манипулирование данными.

Целостность данных в реляционной модели

 

 

Любая СУБД, поддерживающая реляционную модель, должна поддерживать:

 

целостность по сущностям (с помощью механизма первичных ключей)

 

ссылочную целостность (с помощью механизма внешних ключей)

 

Теперь мы можем дать определение реляционной базы данных в целом.

Реляционная БД:

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

 

Схема базы данных состоит из набора схем отношений (заголовков отношений). В схемах отношений заданы необходимые первичные и внешние ключи.

 

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

Для нашего примера – предприятия общественного питания -реляционная база данных будет иметь вид:

Объектно-ориентированная база данных (ООБД) (взял с вики.. в лекциях нету)

— база данных, в которой данные моделируются в виде объектов,их атрибутов, методов и классов

Характеристики

 

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

 

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

 

Обязательные характеристики

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

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

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

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

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

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

· Вычислительная полнота. Язык манипулирования данными должен быть языком программирования общего назначения.

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

 

Необязательные характеристики:

· Множественное наследование

· Проверка типов

· Распределение

· Проектные транзакции

 

Открытые характеристики:

· Парадигмы программирования (процедурное, декларативное)

· Система представления

· Система типов

· Однородность. Реализация — язык программирования — интерфейс.

ООБД и её СУБД

 

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

 

Некоторые объектно-ориентированные базы данных разработаны для плотного взаимодействия с такими объектно-ориентированными языками программирования как Python, Java, C#, Visual Basic.NET, C++, Objective-C и Smalltalk; другие имеют свои собственные языки программирования. ООСУБД используют точно такую же модель, что и объектно-ориентированные языки программирования.

 

СУБД должна обеспечивать:

· Долговременное хранение

· Использование внешней памяти

· Параллелизм

· Восстановление

· Нерегламентированные запросы

Вопрос 2

Строгое определение понятия "ключ"

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

Выбор первичного ключа:

Пример 1:

Студент (Номер зачетной книжки, Фамилия, Имя, Отчество, Группа, Пол, Дата рождения, Адрес, …)

 

Пример 2:

Блюдо (Номер блюда, Название, Вид, …)

 

Название = «Заяц в сметанном соусе с картофельными крокетами и салатом из красной капусты»

 

Целостность

Что понимают под целостностью данных в базах данных? Это не тоже самое, что безопасность или надежность хранения данных в БД.

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

 

Все правила целостности для удобства разбивают на виды или группы:

2. Целостность по ссылкам. Внешние ключи