Запросы более высокого уровня
Запросы, выражаемые на реляционно полном языке, выбирают из базы данных элементы отношения (или множества элементов), которые могут быть описаны предикатом реляционного исчисления. Хотя это метод достаточен для большинства бизнес-приложений, ориентированных на транзакции, для некоторых других приложений могут требоваться более сложные объекты данных и более мощные предикаты запросов. Эти требования могут характеризоваться как расширения языков, которые приводят к языкам, более мощным, чем реляционно полные языки. В этом разделе мы обращаемся к методам оптимизации для таких расширений.
В системах иерархических и сетевых баз данных поддерживаются объекты данных, которые являются более сложными, чем плоские записи, и поэтому в них содержатся пути доступа, несущие информацию (information-bearing) [Astrahan and Ghosh 1974]. Поэтому для реляционных интерфейсов к таким системам требуется эффективная трансляция реляционных запросов в навигационные программы доступа. (Также изучается и обратная проблема - преобразование программ из сетевого кода к реляционным запросам [Katz and Wong 1982].) Описано несколько подходов: интерпретационный, трансляционный и обрабатывающий представления.
Интерпретационные модели (например, [Zaniolo 1979]) прямо интерпретируют реляционные запросы как последовательность покортежных операций в серевой базе данных. Аналогично, прямые трансляционные методы (например, [Vassiliou and Lochovsky 1980]) часто не обращаются к оптимизации; такие методы могут приводить к весьма неэффективному коду. Даял со своими сотрудниками [Dayal et al. 1981; Dayal and Goodman 1982] и Грей [Gray 1981, 1984] разработали стратегии оптимизации запросов для сетевых баз данных. В качестве альтернативы, можно представлять сетевые структуры как реляционные представления с особыми ограничениями целостности [Rosenthal and Reiner 1984]. Таким образом, для компиляции эффективных навигационных программ, работающих над сетевой базой данных, можно использовать существующие средства оптимизации представлений.
Приложения из областей CAD/CAM и обработки текстов обычно работают с даже более сложнымиобъектами, составленными их элементов разных отношений. С исользованием нескольких представления данных можно определить структуры поверх традиционной реляционной (или сетевой) базы данных, которые позволяют обращаться к объекту целиком или к его части [Johnston et al. 1983]. Другой подход заключается в расширении реляционной модели отношениями, не находящимися в первой нормальной форме [Lamersdorf 1984; Schek and Pistor 1982]. В таких расширениях доступ к подструктурам поддерживается специальными индексными схемами или использованием механизмов поиска по шаблону, аналогичных тем, которые используются в информационном поиске [Davis and Kunii 1982]. В [Dayal 1983b] исследуется родственная проблема ответа на запросы в обобщенной иерархии, в которой учитывается тот факт, что объекты данных наследуют свойства от более общих объектов.
Запросы реляционного исчисления выбирают наборы данных в том виде, как они поступают из базы данных, в них не поддерживаются генерация и абстрагирование от хранимых данных к более сложным объектам данных языка запросов. К области обработки статистических запросов относятся группировка и суммаризация элементов одного отношения по некоторым так называемым категорийным атрибутам. Для поддержки таких приложений в некоторых языках запросов предлагается ограниченный набор встроенных агрегатных функций. Агрегатные функции могут быть определены как расширения как реляционного исчисления [Klug 1982a], так и реляционной алгебры [Ozsoyoglu and Ozsoyoglu 1983] и могут вычисляться с использованием вложенной итерации с использованием индексов, описанной в разд. 4 [Klug 1982b]. Однако многие статистические базы данных характеризуются высокой избыточностью и большим числом неопределенных значений. Поэтому данные должны сжиматься и храниться способом, отличным от стандартных реляционных баз данных. Обзор этих вопросов можно найти в [Shoshani 1982]. Для обработки запросов в таких базах данных изобретаются специальное программное обеспечение [Eggers and Shoshani 1980] и аппаратура [Bancilhon et al. 1982; Hawthorn 1982].
В [ Walker 1980] обсуждается использование небольших абстрактных баз данных в системах поддержки решений.
Для приложения баз данных искусственного интеллекта , в особенности экспертных систем [Nau1983] и пользовательских интерфейсов на естественных языках [Marburger and Nebel 1983; Sagalowicz 1977] требуются интерфейсы, выполняемые над "сырыми" данными, поступающими из базы данных [Buneman 1979; Chang 1979; Minker 1975, 1978]. Хотя части такого механизма вывода могут обеспечиваться традиционными механизмами представлений с некоторой дополнительной оптимизацией [Jarke et al. 1984; Ott 1977; Ott and Horlaender 1982; Paige 1982], более сложные запросы - например, использование рекурсии - должны обрабатываться другим образом.
Ряд возможных архитектур для сопряжения экспертных систем с СУБД представлен в [Jarke and Vassiliou 1984]. Обращение к экспертной системе обычно транслируется в последовательность связанных вызовов базы данных. В число методов оптимизации входит объединение нескольких покортежных вызовов базы данных в операции, ориентированные на множества [Kunifuji and Yokota 1982; Vassiliou et al. 1984], упрощение таких запросов на выборку [Grishman 1978; Jarke et al. 1984; Reiter 1978], переупорядочивание условий, которые требуется проверять [Warren 1981] и разделение промежуточных результатов [Grant and Minker 1981], что особенно полезно при выполнении рекурсивных вызовов базы данных [Chang 1978; Henschen and Naqvi 1984; Kellogg 1982; Minker and Nicolas 1983]. Средством, часто предлагаемым в этом контексте, является язык логического програмирования Prolog [Kowalski 1981]. В [Parsaye 1983] предлагаются расширения к Prolog, специально разработанные для управдения базами данных и знаний.
Языковые расширения, представленные в этом разделе, теоретически можно различать по их выразительной мощности и трудности вычислений. В [Chandra and Harel 1982a, 1982b] анализируется несколько классов языков запросов более высокого уровня, такие как (в порядке возрастания мощности языков и вычислительной сложности) запросы с использованием реляционного исчисления первого порядка, запросы с использованием дизъюнктов Хорна, запросы с фиксированной точкой, запросы второго порядка и общие вычисляемые запросы.Пользователь традиционного языка запрсов может достичь мощности этих языков высокого уровня путем использования конструкций универсального языка программирования в языке программирования баз данных [Schmidt 1984]. Недостаток этого решения, в дополнение к возрастающим усилиям по программированию, сосотоит в том, что ответственность за эффективную реализацию переходит от системы управления данными к пользователю.
