Лабораторная работа

Prolog. B+ ДЕРЕВЬЯ

Категория:

Лабораторная работа

Дисциплина:

Функциональное и логическое программирование

Город:

Беларусь, Минск

Учебное заведение:

БНТУ, ФИТР

Тег:

#PROLOG

Стоимость работы:

8 руб.

Оценка: 10
Объем страниц: 7
Год сдачи: 2021
Дата публикации: 02.01.2022

Фрагменты для ознакомления

Лабораторная работа № 13

 

B+ ДЕРЕВЬЯ

Цель работы: приобретение практических навыков составления и отладки программ, работающих с B+деревьями.

Постановка задачи:

Создать внешнюю базу данных на диске следующего формата:

student( Номер_зачетки, Фамилия, Средний_балл).

В этой БД по каждому из полей сформировать В+ дерево. Требуется: 

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

б) вывести фамилии студентов в алфавитном порядке;

в) вывести фамилии студентов в порядке убывания среднего балла.

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

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

 

Код программы:

%Выбрать из базы данных фамилии (вывод каждой в отдельной строке), длина которых меньше длины номера зачетки.
global domains
        db_selector = mydba
domains
        surname, number, bal = string
        student = student(surname, bal, number)
 
predicates
        nondeterm show_up(bt_selector)
        nondeterm show_down(bt_selector)
        nondeterm repeat           
        nondeterm menu
        nondeterm process(integer)
        nondeterm error
        nondeterm result   
        nondeterm sumChar(string, integer)   
        nondeterm proverka(string, string, integer)
 
clauses
  result :- 
  existfile("bmydb"),
  db_open(mydba,"bmydb",in_file),
  write("Внешняя БД открыта"), nl, !;
  db_create(mydba,"bmydb",in_file),
  bt_create(mydba, "surname", _, 20, 4),
  bt_create(mydba, "bal", _, 20, 4),
  bt_create(mydba, "number", _, 20, 4),   
  write("Внешняя БД создана"),nl.
       repeat.
 repeat:-repeat. 

 

Результаты работы программы:

Результаты работы программы

 

Результаты работы программы

 

Контрольные вопросы:

1. Что такое В+ деревья, где и для чего они используются?

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

2. Отличие В+ дерева от двоичного (бинарного) дерева.

В+ дерево отличается от двоичного дерева тем, что оно содержит эффективные методы сортировки.

3. Механизм упорядочивания данных в двоичном дереве.

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

4. Что представляет собой ключ В+ дерева ?

Ключ - информационное поле записи, по которому построено В+ дерево. При вводе новой записи во внешнюю БД Пролог включает ключ и указатель, соответствующие этой записи, в В+ дерево.

5. Страница, длина и порядок В+ дерева.

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

Длина В+ дерева - длина ключа, в пределах которой будет производиться упорядочивание ключей при построении дерева.

Порядок В+ дерева - порядок дерева, определяющий, сколько ключей запоминается в каждом узле В+ дерева. Для баз данных среднего размера рекомендуется Пор=4.

6) Как в программе создаётся В+ дерево ?

7) Какие стандартные предикаты используются для открытия, закрытия и удаления В+ дерева ?

8) Как можно вставить новый ключ в В+ дерево ?

9) Как можно удалить ключ из В+ дерева?

10)  Какие стандартные предикаты используются для установки указателя ключа В+ дерева на первый, последний, текущий ключ?

11)  Какие стандартные предикаты используются для перемещения указателя на ключ В+ дерева вперёд и назад?

12)  Какой тип данных должны иметь ключи В+ дерева?

13) Как можно определить имена В+ деревьев внешней базы данных?

14)  Как можно получить статистическую информацию о В+ дереве ?

15)  В каком порядке разместятся в В+ дереве следующие значения ключа: 1, 2, 5, 12,43?

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

33