БД на инвертированных списках

14.2. Распределённые БД.

БД, основанные на правилах.

14.1. Основные особенности систем, основанных на инвертированных списках

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

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

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

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

б) Физическая упорядоченность строк всех таблиц может определяться и для всей БД (так делается, например, в Datacom/DB);

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

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

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

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

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

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

2) Операторы над адресуемыми записями.

Типичный набор операторов:

· LOCATE FIRST - найти первую запись таблицы в физическом порядке; возвращает адрес записи;

· LOCATE FIRST WITH SEARCH KEY EQUAL - найти первую запись таблицы с заданным значением ключа поиска; возвращает адрес записи;

· LOCATE NEXT - найти первую запись, следующую за записью с заданным адресом в заданном пути доступа; возвращает адрес записи;

· LOCATE NEXT WITH SEARCH KEY EQUAL - найти следующую запись таблицы (в порядке пути поиска) с заданным значением К; должно быть соответствие между используемым способом сканирования и ключом K; возвращает адрес записи;

· LOCATE FIRST WITH SEARCH KEY GREATER - найти первую запись таблицы в порядке пути поиска со значением ключевого поля, большим заданного значения K; возвращает адрес записи;

· RETRIVE - выбрать запись с указанным адресом;

· UPDATE - обновить запись с указанным адресом;

· DELETE - удалить запись с указанным адресом;

· STORE - включить запись в указанную таблицу; операция генерирует адрес записи.

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

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

14.2. Распределённые БД

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

При этом должны обеспечиваться:

- простота использования системы;

- возможности автономного функционирования при нарушениях связности сети или при административных потребностях;

- высокая степень эффективности.

14.2.1. Разновидности распределённых систем

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

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

Примером однородных распределенных СУБД может служить System R.

14.2.3. Интегрированные или федеративные системы и мультибазы данных

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

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

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

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

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

14.3. Системы баз данных, основанные на правилах

14.3.1. Экстенсиональная и интенсиональная части базы данных

Если внимательно присмотреться к тому, что реально хранится в базе данных, то можно заметить наличие трёх различных видов информации:

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

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

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

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

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

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

14.3.2. Активные базы данных

БД называется активной, если СУБД по отношению к ней выполняет не только те действия, которые явно указывает пользователь, но и дополнительные действия в соответствии с правилами, заложенными в саму БД.

14.3.3. Дедуктивные базы данных

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

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

Лекция 15. Объектно-ориентированные СУБД. Часть 1.