Базы данных. 
Интеллектуальные системы

База данных (БД) — формализованное представление информации, удобное для хранения и поиска данных в нем. Понятие БД возникло в 60-е годы 20 века и связано с развитием вычислительной техники и информатики. Тематика теории БД связана с поиском удобного представления, компактного хранения, быстрого поиска, защищенности и других свойств данных. Развитию этого направления способствовали как производственныё и творческие коллективы: IBM (иерархическая модель данных), Рабочая группа по БД Ассоциации по языкам систем обработки данных — CODASYL (сетевая модель данных), исследовательская группа по системам управления БД Американского национального института стандартов — ANSI/SPARC Study Group on DataBase Management Systems (принципы проектирования БД), так и отдельные исследователи: Кодд (E.F.Codd) (реляционная модель данных), Галлейр (H.Gallaire), Минкер (J.Minker) (дедуктивные БД), Тальхайм (B.Thalheim) (моделирование семантики в БД, теория ограничений целостности), Аткинсон (M.Atkinson), Бири (C.Beeri) и др. (объектноориентированные БД), В. Н. Решетников (алгебраическая модель информационного поиска), Думи (A.Dumey), А. П. Ершов (методы хеширования), Бентли (J.L.Bentley), Кнут (D.E.Knuth), Ли (D.T.Lee), Маурер (W.D.Maurer), Ульман (J.D.Ullman), Шеймос (M.I.Shamos) и др. (сложность алгоритмов обработки данпых), Э. Э. Гасанов (информационно-графовая модель данных, сложность алгоритмов поиска) и многие другие.

Тематика теории БД связана со следующими основными направлениями.

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

Специальное направление в теории БД составляет защищенность данных от случайного или преднамеренного доступа к ним несанкционированных пользователей [54]. Интенсивное развитие всемирной компьютерной сети Internet делает это направление особенно актуальным.

Третье основное направление тематики теории БД связано с вопросами сложности алгоритмов обработки данных.

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

Критерии, определяющие выбор физической организации, отличаются от тех, которые определяют выбор логической организации данных. При выборе физической организации решающим фактором является эффективность, причем согласно Дж. Мартину [40] на первом месте стоит обеспечение эффективности поиска, далее идут эффективность операций занесения и удаления и затем обеспечение компактности данных.

Методы физической организации данных хорошо изложены в классических книгах Д. Кнута [23], Дж. Мартина [40], А. Ахо, Дж. Хопкрофта, Дж. Ульмана [7].

Основную рекомендуемую литературу к данной главе составляют [11, 41].