2014-02-12
1481
Для отражения последних достижений в области новых методов вычисления логических программ, вычислительной алгебры, теории объектно-ориентированных структурированных типов данных, представления знаний в последние десятилетия производится интенсивный поиск новых языков логического программирования.
Интеграция ЛП и БД позволяет образовывать системы нового типа, расширяющие границы информатики как науки, и позволяющие удовлетворять требованиям новых применений. Для таких систем используются следующие названия:
· дедуктивная БД (отражает использование стиля ЛП для реализации дедукции на основе содержимого БД);
· СУБЗ (отражает управление сложными знанинями, а не простыми данными);
· ЭС БД (отражает использование опыта экспертов в определенной прикладной области для решения класса задач при сохранении доступа к большой БД).
Слияние логических программ и баз данных происходит в соответствии с общей тенденцией в информатике – совместное исследование нескольких областей с целью генерации новых идей и использование новых концепций.
|
|
|
Изучение ЛП и управления БД позволяет обнаружить следующие их общие черты:
· Базы данных. Системы ЛП управляют небольшими однопользовательскими БД, располагаемыми в оперативной памяти и содержащими правила вывода и фактическую информацию. Системы БД, напротив, управляют большими, находящимися в коллективном пользовании совокупностями данных в массовой памяти и обеспечивают технологию поддержки эффективного поиска и надежного изменения долговременно хранимых данных.
· Запросы. Запрос означает процесс, с помощью которого релевантная информация извлекается из БД. В ЛП запрос (или цель) реализуется построением цепочек логических выводов, комбинирующих правила и фактическую информацию для доказательства истинности или отрицания справедливости первоначального утверждения. В системах БД запрос (выражаемый с помощью специализированного языка манипулирования данными) обрабатывается при использовании наиболее объективных путей доступа в массовой памяти к большим совокупностям данных для извлечения релевантной информации.
· Ограничения. Ограничения задают условия правильности БД. Проверка ограничения – процесс, с помощью которого обеспечивается правильность БД и предотвращается помещение неправильных данных в БД. В ЛП ограничения выражаются с помощью универсальных правил, активизируемых при модификации БД. В системах БД лишь небольшое число типовых ограничений обычно выражается на языке определения данных.
· ЛП обладает большей выразительной способностью задания запросов и ограничений в сравнении с языками определения данных и манипулирования данными систем БД (в однородном формализме). Вместе с тем, системы ЛП не обеспечивают технологии управления большими, надежными, долговременно хранимыми совокупностями данных с коллективным доступом.
|
|
|
Дейталог возник как альтернатива Прологу в контексте дедуктивных БД, поскольку Пролог в качестве БД имеет рад недостатков, в том числе следующие:
1. Покортежная обработка (Пролог в качестве ответа на вопрос возвращает отдельные кортежи, а не множество кортежей).
2. Процедурность и чувствительность к порядку записи правил или фактов в БД и к порядку предикатов в теле правил (такие языки как SQL или реляционная алгебра, являются непроцедурными; выполнение запросов к БД не зависит от порядка поисковых предикатов или кортежей БД).
3. Специальные предикаты, используемые для ввода-вывода, отладки, воздействия на бэктрекинг, что ведет к потери декларативности языка.
4. Функциональные символы, используемые обычно для построения рекурсивных функций и сложных структур данных – не требуются для манипулирования плоской реляционной БД.
Дейталог сконструирован для использования в качестве языка БД. Он является непроцедурным, множественным, нечувствительным к порядку языком и не имеет специальных предикатов.
Если прологовские программы имеют операционную семантику, программы на Дейталоге – чисто декларативные (денотативную семантику).
При интерпретации на Прологе используется нисходящая схема, основанная на резолюционной стратегии, поиске сначала внутрь и бэктрекинге для конструирования деревьев доказательства.
Базовая схема интерпретации Дейталога – восходящая. В ее основе лежат методы вычисления неподвижной точки программы и реляционная алгебра.
Синтаксически Дейталог напоминает «чистый» Пролог: «:-» есть «<=», «,» есть «AND», «;» есть «OR».
Различают экстенсиональную БД – факты из БД, интенсиональную БД – дополнительные факты + дедуктивные аксиомы и ограничения целостности (правила).
EDB+IDB = дедуктивная БД.
Для превращения Дейталога и Пролога в языки БД требуется разработка новых систем, интегрирующих функции ЛП и систем БД. Рассмотрим ряд альтернативных архитектур.
1. Интеграция – разработка един(ственн)ой системы, реализующей ЛП над БД с массовой памятью. Подход требует разработки совершенно нового класса структур данных и специально сконструированных алгоритмов.
2. Связывание - разработка интерфейса между двумя различными подсистемами ЛП и БД. Обес системы сохраняют свою индивидуальность. Интерфейс обеспечивает процедуры для переноса данных из долговременной среды хранения СБД в основную память исполнительной среды ЛП. Подход проще в реализации, но менее эффективен. Различают 2 альтернативы, различающиеся сложностью, селективностью, требуемой памятью и производительностью:
- Слабое (статическое) связывание: взаимодействие между системами ЛП и БД возникает независимо от фактического процесса вывода – обычно во время компиляции или загрузки программы интерпретатором, с помощью извлечения из БД всех фактов, которые могли бы понадобиться программе, или по отношению к каждому правилу перед его активизацией.
- Сильное (динамическое) связывание – осуществляется, когда системе ЛП требуются дополнительные данные от СБД для продолжения вывода.
Сравнение слабого и сильного связывания:
| СЛАБОЕ СВЯЗЫВАНИЕ | СИЛЬНОЕ СВЯЗЫВАНИЕ |
| Меньше запросов | Больше запросов |
| Менее означенные запросы | Более означенные запросы |
| Реализуются все запросы | Реализуются только релевантные запросы |
| Требуется больше памяти | Требуется меньше памяти |
Реляционная модель данных
В РМД данные организованы в отношения, определяющиеся следующим образом.
|
|
|
Пусть D1, …, Dn – множества, называемые доменами, D – их декартовое произведение.
Тогда отношением R, определенным на D1, …, Dn, является любое подмножество D (n представляет собой арность R).
Ключом отношения R называется подмножество k £ n атрибутов R, значения которых являются уникальными в отношении. Т.о., с помощью ключа можно идентифицировать кортежи отношения.
Пример. Схемы отношений OFFERING и EXAM:
OFFERING(PROFESSOR, COURSE, YEAR, DEPARTMENT),
EXAM(STUDENT, COURSE, YEAR, GRADE).
| OFFERING | |||
| PROFESSOR | COURSE | YEAR | DEPARTMENT |
| Date | Databases | Computer Science | |
| Saunders | Geometry | Mathematics | |
| Floyd | Automata Theory | Computer Science | |
| Brill | Chemistry | Chemistry | |
| Brill | Chemistry | Chemistry |
| EXAM | |||
| STUDENT | COURSE | YEAR | GRADE |
| Jones | Automata Theory | A | |
| Smith | Databases | B | |
| Delsey | Chemistry | A | |
| Carey | Chemistry | B | |
| Jones | Geometry | C |
Ключом отношения OFFERING является { COURSE, YEAR }, отношения EXAM – {STUDENT, COURSE}.
Реляционные языки.
Для выражения запросов над отношениями существуют 2 основных формальных аппарата.
Реляционная алгебра. Определяется с помощью нескольких операторов, применяемых к отношениям и дающих в результате другие отношения. Этот формальный аппарат ориентирован на множества, поскольку каждый оператор применяется к отношению в целом. Порядок, в котором операции реляционной алгебры указаны в запросах, определяет также порядок применения этих операций к БД. В действительности многие процедуры оптимизации запросов основаны на эквивалентных преобразованиях, позволяющих одни выражения PA заменять другими, выполняемыми СУБД более эффективно.
Реляционное исчисление. Запросы выражаются с помощью запросов логики предикатов 1 порядка над кортежами БД. Результатом запроса является множество кортежей, удовлетворяющих формуле. Этот формальный аппарат ориентирован на покортежную обработку, так как каждая формула определяет свойства, характеризующие кортеж результата. Это непроцедурный язык запросов.
Простейшими (базовыми) операциями РА являются: выборка (селекция), проекция, декартово произведение, объединение и разность. Набор реляционных операторов является реляционно полным в том смысле, что его выразительная мощность эквивалентна мощности реляционного исчисления.
|
|
|
Если исключить из операторов разность, то получим подъязык, называемый Положительной реляционной алгеброй (RA+).
Выборка. Пусть F – допустимая формула, выражающая предикат выборки. При выборке допустимые формулы представляются комбинациями простых предикатов, каждый из которых есть сравнение либо двух атрибутов, либо атрибута и константы. Т.о., результатом выборки из R будет множество кортежей R, для которых формула F истинна.
Проекция. Пусть R имеет n атрибутов. Предположим, что i1, …, ik, k<= n – имена (или порядковые номера) атрибутов R. Пусть Di – домен i- го атрибута. Тогда результатом проекции П i1,…in R будет отношение, имеющее r атрибутов i1, …, ik. Кортежи результирующего отношения получаются из кортежей отношения операнда с помощью исключения значений атрибутов, не принадлежащих указанному списку. При этом кардинальность результата проекции может измениться, поскольку одинаковые кортежи выбрасываются.
Декартово произведение. Пусть R имеет r атрибутов и S имеет s атрибутов. Тогда RxS будет отношением с r+s атрибутами со схемой, полученной с помощью конкатенации схем R и S, и кортежами, образованными конкатенацией кортежей R и S всеми возможными способами.
Объединение. Данная операция применяется к двум отношениям с одинаковой схемой. RÈS представляет собой множество кортежей, принадлежащих объединению (в теоретико-множественном смысле) R и S.
Разность. Данная операция применяется к двум отношениям с одинаковой схемой. R-S представляет собой множество кортежей, принадлежащих разности (в теоретико-множественном смысле) R и S.
Следующие операции являются производными от определенных выше.
Соединение. Пусть F – формула, представляющая собой логическую комбинацию сравнений атрибутов из двух отношений-операндов. Соединение определяется на основе декартова произведения и выборки: R 
F S = sF(RxS)
Полусоединение. Пусть F – предикат соединения. Полусоединение определяется как
R 
F S = П schema(R) R F S.
Примеры применения каждой из операций:
| Исходные отношения | ||||||||||||||
| R | S | T | ||||||||||||
| A1 | A2 | A3 | B1 | B2 | B1 | B2 | ||||||||
| A | B | C | D | E | B | E | ||||||||
| F | D | H | G | H | D | C | ||||||||
| F | E | H | F | M | G | M | ||||||||
| Базовые операции | ||||||||||||||
| sA1=F R | П A1,A3 R | S È T | S - T | |||||||||||
| A1 | A2 | A3 | A1 | A3 | B1 | B2 | B1 | B2 | ||||||
| F | D | H | A | C | D | E | B | E | ||||||
| F | E | H | F | H | G | H | G | M | ||||||
| F | M | |||||||||||||
| B | E | |||||||||||||
| G | M | |||||||||||||
| R x S | ||||||||||||||
| A1 | A2 | A3 | B1 | B2 | ||||||||||
| A | B | C | D | E | ||||||||||
| A | B | C | G | H | ||||||||||
| A | B | C | F | M | ||||||||||
| F | D | H | D | E | ||||||||||
| F | D | H | G | H | ||||||||||
| F | D | H | F | M | ||||||||||
| F | E | H | D | E | ||||||||||
| F | E | H | G | H | ||||||||||
| F | E | H | F | M | ||||||||||
| Производные операции | ||||||||||||||
| R A2=B2 S
| R A3=B2 S
| |||||||||||||
| A1 | A2 | A3 | B1 | B2 | A1 | A2 | A3 | |||||||
| F | E | H | D | E | F | D | H | |||||||
| F | E | H |
Пример. Рассмотрим следующие запросы к БД.
А) Мы хотим знать всех студентов, получивших оценку А в 1987 г.:
П STUDENT (s GRADE=A L YEAR=1987 EXAM)
Ответ:
| STUDENT |
| Jones |
Б) Мы хотим знать имена и оценки всех студентов, которые сдали экзамены по одному из предметов, преподаваемых на факультете Computer Science:
П STUDENT, GRADE (EXAM (s DEPARTMENT = Computer Science OFFERING))
Ответ:
| STUDENT | GRADE |
| Jones | A |
| Smith | B |
В) Мы хотим знать всех студентов, занимающихся с профессором Бриллом:
П STUDENT s PROFESSOR = Brill (EXAM (OFFERING).
Это выражение эквивалентно следующему:
П STUDENT (EXAM (s PROFESSOR = Brill OFFERING).
Ответ:
| STUDENT |
| Delsey |
| Carey |
РА не является «дружественым языком». Наиболее популярным языком запросов является SQL:
А) SELECT STUDENT FROM EXAM
WHERE GRADE=A AND YEAR=1987.
Б) SELECT STUDENT, GRADE FROM EXAM
WHERE <COURSE, YEAR> = SELECT COURSE, YEAR FROM OFFERING
WHERE DEPARTMENT = ‘Computer Science’.
Взглядом называется отношение, которое не хранится в БД непосредственно, а определяется с помощью некоторого отношения языка запросов.
Базовая конъюнкция – некоторая последовательность предикатов БД и арифметических предикатов сравнения.
Каждая базовая конъюнкция соответствует запросу-соединению (конъюнктивному запросу) к БД, формулируемому в терминах реляционной алгебры. Большинство систем отображают их на SQL.
Оптимизация запросов-соединений - характерная черта всех реляционных СУБД: композиция правил, перестановка предикатов в теле правил, отсечение, дизъюнкция, отрицание и обработка рекурсии.
