ЛИСП-реализация основных операций над базами данных

Содержание

Введение 2

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

2 Математические и алгоритмические основы решения задачи 7

2.1 Выполнение основных операций над базами данных 7

2.2 Скорость операций обновления данных 7

3 Функциональные модели и блок-схемы решения задачи 10

4 Программная реализация решения задачи 13

5 Пример выполнения программы 19

Заключение 23

Список использованных источников и литературы 24

Введение

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

В основе решения многих задач лежит обработка информации. Для облегчения обработки информации создаются информационные системы (ИС). Автоматизированными называют ИС, в которых применяют технические средства, в частности ЭВМ. Большинство существующих ИС являются автоматизированными.

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

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

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

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

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

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

Целью данной курсовой работы является ЛИСП - реализация основных операций над базами данных.

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

Требуется разработать программу, реализующую основные операции над базами данных: выбор, добавление, модификация и удаление данных.

Пример 1.

В таблицу сотрудники (Таблица 1) необходимо добавить данные о новых сотрудниках (Таблица 2):

Таблица 1. Сотрудники

Сотрудники	Зарплата
Петров	5700
Иванов	8200
Сидоров	16100
Николенко	7650
Сотрудники	Зарплата
Сидоренко	12000
Владимиров	8200
Сергиенко	6540

Таблица 2. Новые сотрудники

Решение:

Добавляются данные о новых сотрудниках в начало таблицы 1. В результате получим:

Таблица 3. Результат выполнения операции добавления

Сотрудники	Зарплата
Сидоренко	12000
Владимиров	8200
Сергиенко	6540
Петров	5700
Иванов	8200
Сидоров	16100
Николенко	7650

Пример 2.

Из таблицы сотрудники (Таблица 1) необходимо выбрать всех сотрудников с зарплатой 8200.

Решение:

Просматриваем все записи, и выводим только тех сотрудников, у которых зарплата равна 8200:

Таблица 4. Результат выполнения операции выбора

Сотрудники	Зарплата
Владимиров	8200
Иванов	8200

Пример 3.

Из таблицы сотрудники (Таблица 1) необходимо поменять зарплату Сидоренко на 13000.

Решение:

Просматриваем все записи, находим фамилию Сидоренко и изменяем зарплату 12000 на 13000. В результате получим:

Таблица 5. Результат выполнения операции модификации

Сотрудники	Зарплата
Сидоренко	13000
Владимиров	8200
Сергиенко	6540
Петров	5700
Иванов	8200
Сидоров	16100
Николенко	7650

Пример 4.

Из таблицы сотрудники (Таблица 1) необходимо удалить сотрудников Сидоренко и Владимирова.

Решение:

Просматриваем все записи, находим фамилию Сидоренко - удаляем запись, аналогично удаляем Владимирова.

Таблица 6. Результат выполнения операции удаления

Сотрудники	Зарплата
Сергиенко	6540
Петров	5700
Иванов	8200
Сидоров	16100
Николенко	7650

2 Математические и алгоритмические основы решения задачи

2.1 Выполнение основных операций над базами данных

Опишем, каким образом выполняется запрос пользователя на вставку, удаление и операцию модификации.

В случае операции вставки сначала считываются с файла новые данные для добавления к базе данных. Устанавливается позиция добавления данных. Выполняется операция вставки.

Для выполнения операции удаления данных, нужно сначала найти эти данные, затем удалить.

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

2.2 Скорость операций обновления

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

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

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

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

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

3 Функциональные модели и блок-схемы решения задачи

Функциональные модели и блок-схемы решения задачи представлены на рисунках 1, 2, 3, 4, 5.

Условные обозначения:

POS - позиция вставки;

LST - список сотрудников;

AT - добавляемый элемент;

FM - фамилия сотрудника;

PAYM - оклад сотрудника.

Рисунок 1 - Блок-схема решения задачи для функции INSERT

Рисунок 2 - Блок-схема решения задачи для функции DELETE

Рисунок 3 - Блок-схема решения задачи для функции GET_PEOPLE_PAYMANT

Рисунок 4 - Блок-схема решения задачи для функции CHANGE_DATA

Рисунок 5 - Блок-схема решения задачи для функции GET_PEOPLE

4 Программная реализация решения задачи

;ПОЛУЧАЕМ ИЗ ФАЙЛА СПИСОК СОТРУДНИКОВ

(SETF EMPLOYEE 0)

(SETQ INPUT_STREAM (OPEN " D:\\EMPLOYEE.TXT" :DIRECTION :INPUT))

(SETQ EMPLOYEE (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

;ОСНОВНЫЕ ОПЕРАЦИИ: ВСТАВКА, УДАЛЕНИЕ, ВЫБОРКА, ИЗМЕНЕНИЕ

;ВСТАВКА

(DEFUN INSERT (POS LST AT)

(COND

((NULL LST) (CONS AT NIL))

((EQL POS 0) (CONS AT LST))

(T (CONS (CAR LST) (INSERT (- POS 1) (CDR LST) AT)))

)

)

;ВСТАВКА ЭЛЕМЕНТА AT В ПОЗИЦИЮ POS СПИСКА LST

;УДАЛЕНИЕ

(DEFUN DELETE (FM LST)

(COND

((NULL LST) NIL)

((EQL FM (CAR (CAR LST))) (CDR LST))

(T (CONS (CAR LST) (DELETE FM (CDR LST))))

)

)

;УДАЛЕНИЕ ПО ФАМИЛИИ ЗАПИСИ ИЗ СПИСКА

;ВЫБОРКА ЗАРПЛАТЫ СОТРУДНИКА ПО ЕГО ФАМИЛИИ

(DEFUN GET_PEOPLE_PAYMANT (FM LST)

(COND

((NULL LST) NIL)

((EQUAL FM (CAR (CAR LST))) (CADR (CAR LST)))

(T (GET_PEOPLE_PAYMANT FM (CDR LST)))

)

)

;ВЫБОРКА ЛЮДЕЙ С ЗАРПЛАТОЙ PAYM

(DEFUN GET_PEOPLE (PAYM LST OUTPUT_STREAM)

(COND

((NULL LST) NIL)

((EQUAL PAYM (CADR (CAR LST)))

(PROGN

(PRINT (CAR (CAR LST)) OUTPUT_STREAM)

(GET_PEOPLE PAYM (CDR LST) OUTPUT_STREAM)

)

)

(T (GET_PEOPLE PAYM (CDR LST) OUTPUT_STREAM))

)

)

;ИЗМЕНИЕ ЗАРПЛАТЫ СОТРУДНИКА

;ИЩЕМ СОТРУДНИКА ПО ЕГО ФАМИЛИИ

;МЕНЯЕМ ДАННЫЕ

(DEFUN CHANGE_DATA (FM PAYM LST)

(COND

((NULL LST) NIL)

((EQUAL FM (CAR (CAR LST))) (SETF (CADR (CAR LST)) PAYM))

(T (CHANGE_DATA FM PAYM (CDR LST)))

)

)

;----------------------------------------------------------------------

;ДОБАВЛЯЕМ СОТРУДНИКОВ

;ПОЛУЧАЕМ ИЗ ФАЙЛА НОВЫХ СОТРУДНИКОВ

(SETF NEW_EMPLOYEE 0)

(SETQ INPUT_STREAM (OPEN " D:\\ADD EMPLOYEE.TXT" :DIRECTION :INPUT))

(SETQ NEW_EMPLOYEE (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

;ДОБАВЛЯЕМ

(DO

((I 0))

((>= I (LENGTH NEW_EMPLOYEE)) EMPLOYEE)

(SETQ EMPLOYEE (INSERT 0 EMPLOYEE (NTH I NEW_EMPLOYEE)))

(SETQ I (+ I 1))

)

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ ДОБАВЛЕНИЯ СОТРУДНИКОВ

(SETQ OUTPUT_STREAM (OPEN " D:\ADD_RESULT.TXT" :DIRECTION :OUTPUT))

(PRINT EMPLOYEE OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

;----------------------------------------------------------------------

;УДАЛЯЕМ СОТРУДНИКОВ

ПОЛУЧАЕМ ФАМИЛИИ СОТРУДНИКОВ КОТОРЫХ НАДО УДАЛИТЬ

(SETF FM 0)

(SETQ INPUT_STREAM (OPEN " D:\\DEL_EMPLOYEE.TXT" :DIRECTION :INPUT))

(SETQ FM (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

;УДАЛЯЕМ

(DO

((I 0))

((>= I (LENGTH NUM)) EMPLOYEE)

(SETQ EMPLOYEE (DELETE (NTH I FM) EMPLOYEE ))

(SETQ I (+ I 1))

)

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ УДАЛЕНИЯ СОТРУДНИКОВ

(SETQ OUTPUT_STREAM (OPEN " D:\DEL_RESULT.TXT" :DIRECTION :OUTPUT))

(PRINT EMPLOYEE OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

;----------------------------------------------------------------------

;ВЫБОРКА ЗАРПЛАТЫ СОТРУДНИКА ПО ЕГО ФАМИЛИИ

(SETF FM 0)

(SETQ INPUT_STREAM (OPEN " D:\\FM.TXT" :DIRECTION :INPUT))

(SETQ FM (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

(SETQ RES NIL)

;ВЫБИРАЕМ ЗАРПЛАТУ

(DO

((I 0))

((>= I (LENGTH FM)) EMPLOYEE)

(SETQ RES (INSERT I RES (GET_PEOPLE_PAYMANT (NTH I FM) EMPLOYEE) ))

(SETQ I (+ I 1))

)

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ ВЫБОРКИ ЗАРПЛАТЫ СОТРУДНИКОВ

(SETQ OUTPUT_STREAM (OPEN " D:\PAYMANT.TXT" :DIRECTION :OUTPUT))

(PRINT RES OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

;----------------------------------------------------------------------

;ВЫБОРКА ЛЮДЕЙ С ЗАРПЛАТОЙ PAYM

(SETF PAYM 0)

(SETQ INPUT_STREAM (OPEN " D:\\PAYM.TXT" :DIRECTION :INPUT))

(SETQ PAYM (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ ВЫБОРКИ СОТРУДНИКОВ ПО ЗАРПЛАТЕ

(SETQ OUTPUT_STREAM (OPEN " D:\\PEOPLE.TXT" :DIRECTION :OUTPUT))

;ВЫБИРАЕМ ЛЮДЕЙ

(GET_PEOPLE PAYM EMPLOYEE OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

;----------------------------------------------------------------------

;ИЗМЕНИЕ ЗАРПЛАТЫ СОТРУДНИКА

;ИЩЕМ СОТРУДНИКА ПО ЕГО ФАМИЛИИ

;МЕНЯЕМ ДАННЫЕ

(SETF FM 0)

(SETQ INPUT_STREAM (OPEN " D:\\CHANGE.TXT" :DIRECTION :INPUT))

(SETQ FM (READ INPUT_STREAM))

(CLOSE INPUT_STREAM)

(CHANGE_DATA (CAR FM) (CADR FM) EMPLOYEE)

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ ИЗМЕНЕНИЯ ЗАРПЛАТЫ

(SETQ OUTPUT_STREAM (OPEN " D:\\NEW_EMPLOYEE.TXT" :DIRECTION :OUTPUT))

(PRINT EMPLOYEE OUTPUT_STREAM)

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

;----------------------------------------------------------------------

5 Пример выполнения программы

Пример 1.

Рисунок 6 - Список сотрудников

Рисунок 7 - Список сотрудников, которых нужно добавить

Рисунок 8 - Результат операции добавления

Пример 2.

Рисунок 9 - Список сотрудников

Рисунок 10 - Список сотрудников, которых нужно удалить

Рисунок 11 - Результат операции удаления

Пример 3.

Рисунок 12 - Список сотрудников

Рисунок 13 - Список сотрудников, оклад которых нужно узнать

Рисунок 14 - Результат операции выбора зарплаты по заданной фамилии

Пример 4.

Рисунок 15 - Список сотрудников

Рисунок 16 - Оклад

Рисунок 17 - Результат операции выбора сотрудника по заданному окладу

Пример 5.

Рисунок 18 - Список сотрудников

Рисунок 19 - Новый оклад сотрудника

Рисунок 20 - Результат операции модификации

Заключение

Хранение и использование информации с использованием баз данных имеет решающее значение в настоящее время в большинстве предметных областей. Одно из назначений базы данных - предоставление информации пользователям.

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

Список использованных источников и литературы

1. База данных - Википедия [Электронный ресурс] - Режим доступа: http://ru.wikipedia.org/wiki/База_данных

2. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.

3. Дейт, К.Д. Введение в системы базы данных [Текст] / К.Д. Дейт - М.: Вильямс, 2006. С.1328.

4. Конноли Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. [Электронный ресурс] / Т. Конноли, Б.Каролин - М.: Вильямс, 2003. С. 1436.

5. Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.

6. .Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В.Бржезовский. - М.: ГУАП, 2003. С. 79.

7. Хомоненко, А.Д. Базы данных. Учебник для высших учебных заведений [Текст] / А.Д. Хомоненко, В.М. Цыганков, М.Г. Мальцев. - М.: Корона, 2004. С.736.

8. Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. - М.: Мир, 1990. - 460 с.