22

Логический подход. Представление простых фактов в логических системах

В основе представлений знаний в UU лежит математическая логика (логика предикатов). Синтаксис логики предикатов. Допуск. U типа выражений:

1)константы – служат именами индивидуалов Ваня – 2

2)переменные – обозначают имена совокупностей (человек, книга…)

3)предикатные имена – задают правила соединения констант и переменных.

4)функциональные имена – представляют такие же значения, что и предикаты. Пишут маленькими буквами.

Пример: Посылка(макс_2, мари_4, книга_22) – Макс посылает книгу Марине

X (человек (X) прогуливается (X) ) - каждый человек прогуливается

Типовая организация СУБД. Внутренняя организация реляционной СУБД

Основные функции СУБД:

1)управление данными во внешней памяти

2)управление буферами ОП

3)управление транзакциями

4)журнализация и восстановление БД после сбоев

5)поддержка языков БД

Ядро – отвечает за внешнюю память, буферы, журналы, транзакции. Ядро обладает собственным интерфейсом и недоступно напрямую для воздействия пользователя. Компилятор отвечает за формиррование объектного и испольнимого кодов программы. Утилиты – включают загрузку/выгрузку БД, сбор статистики, проверку целостности.

Внутренняя организация реляционной СУБД.

Особенности:

1) наличие двухуровневой системы а) уровень непосредственного управления данными.

б) языковой уровень – реализованный язык SQL.

2)поддержание отношения каталогов.

3)регулярность структур данных (простота таблиц).

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

23

Хранение отношений.

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

2)хранение отношения по столбцам – единицей хранения является столбец с исключёнными дубликатами.

Типовой способ хранения. Организация страницы памяти:

Область описателей

i-описатель

……..

i-кортеж

Основные характеристики такой организации.

1)Каждый кортеж обладает уникальными типами tidне изменяется во время жизни кортежа.

2)Обычный кортеж хранится целиком в странице. Длина любого отношения ограничивается размерами страницы памяти. Если кортеж не вмещается на страницу, то наиболее простой способ хранить данные в отдельном файле, вне БД. Чаще используется другое решение – длинные данные хранятся в виде binary-дерева. Как правило, на одной странице хранятся кортежи одного отношения. Но существует возможность хранить разные кортежи на одной странице. При этом необходимо на странице хранить, какому отношению принадлежит данный кортеж. При добавлении нового столбца не происходит реорганизация отношений – достаточно внести только изменения в описатель и добавлять по мере поступления столбцов.

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

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

Есть возможность параллельного доступа к ВЗУ за счёт использования декларированной схемы хранения отношений. Кортежи с общим значением столбца располагают на разных дисковых устройствах. Индекс - для обеспечения наиболее быстрого доступа к кортежам.

В-деревья.

С точки зрения физической организации В-дерево – это мультисписочная структура страниц внешней памяти – каждому узлу дерева соответствует страница во внешней памяти. Внутренние и листовые страницы имеют разную структуру. В общем виде внутренняя страница имеет следующую структуру: N1 ключ (1), N2 ключ (2), …, Nn ключ (n).

Свойства:

24

1)ключ (1) Å ключ (2) ÅÅ ключ (n).

2)Nn, k, ключ (n) Å k Å ключ(n+1)

Листовая страница выглядит:

Ключ (1) СП (1) ключ (2) СП (2) …..

Свойства:

1)ключ (1) < ключ(2) < ключ(p). 2)СП (r), ключ (r).

3)упорядоченный список кортежей tid, включающий ключ f. Листовые страницы связаны в 1-ю/2-x упорядоченный список.

Основное свойство В-деревьев – свойство сбалансированности.

Алгоритм вкл /удал записи: 1)при добавлении новой записи:

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

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

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

При удалении записи в таблице:

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

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