tikhobaev/db_lab1

Laboratory work №1

Course: databases

Отчёт

1. Задачи

Необходимо на выбранном языке (C/C++,Java, Python, другие) реализовать файловую базу данных (однотабличная, число полей не менее 4, из них как минимум 1 ключевое). Работа с БД осуществляется через GUI.

Функции к реализации:

• создание, удаление, сохранение БД,
• добавление новой записи в БД (с проверкой уникальности по ключевым полям),
• удаление записи из БД по значению некоторого поля (желательно не ключевого, в таком случае удалить все записи, совпадающие по значению),
• редактирование записи БД,
• создание backup-файла БД,
• восстановление БД из backup-файла,
• импорт БД в файл стороннего формата (например, *.xlsx).

2. Ход работы

• В лабораторной работе была реализована файловая база данных рейтингов фильмов

• база данных содержит 4 поля:

  • Название фильма, текстовый тип данных - длина до 30 символов
  • Год в котором был снят фильм, тип int - 4 цифры
  • Рейтинг фильма(от 0 до 10), тип float,1 знак до запятой, 1 знак после запятой
  • Id - уникальный идентификатор фильма, тип int, 7 знаков

• ключевое поле - id

• база данных работает с файлами с собственным расширением .hdb, файлы хранятся в директории Data

• база данных содержит 2 контейнера - список списков, где хранятся все записи и словарь пар id - индекс в списке списков

Описание реализованных функций

• Функция добавления в базу данных (в дальнейшем - бд): Сложность алгоритма О(1), после проверки на уникальность id каждая новая запись добавляется в главный список, пара id - индекс добавляется в словарь и запись дописывается в файл последней строкой
• Функция поиска в бд. Сложность поиска по id - О(1), по остальным полям - О(n). Для поиска используется словарь для получения индекса элемента в главном списке (если это id существует)
• Функция удаления из бд. Сложность с удалением по id- О(1), c удалением по другим полям - О(n) (в классе бд удаление производится по id, но возможность удаления по другим полям реализована в модуле с GUI - это комбинация поиска и удаления всех найденных записей по найденным id). Функция удаления работает следующим образом: на вход она получает id записи, затем используя словарь получает индекс записи в главном списке, записывает в файле с бд последнюю запись на место той, которую нужно удалить, затем удаляет последнюю строчку в файле, далее в главном списке на место записи, которую нужно удалить записывается последняя запись.

Доказательство эффективности алгоритмов

• Таблица результатов тестирования.
• График роста времени от числа операций.
• Вывод: теоретическая временая сложность операций добавления, поиска по id и удаления доказана тестированием.