Навигационная база данных — это тип базы данных , в которой записи или объекты находятся в основном по ссылкам из других объектов. Этот термин стал популяризирован благодаря названию статьи Чарльза Бахмана «Программист как навигатор» на премию Тьюринга 1973 года . [1] В этой статье подчеркивается тот факт, что новые системы баз данных на основе дисков позволяют программисту выбирать произвольные навигационные маршруты, следуя связям от записи к записи, в отличие от ограничений более ранних систем с магнитной лентой и перфокартами, где доступ к данным был строго ограничен. последовательный.
Одной из первых навигационных баз данных было Integrated Data Store (IDS), разработанное Бахманом для General Electric в 1960-х годах. IDS стала основой модели базы данных CODASYL в 1969 году.
Хотя Бахман описал концепцию навигации в абстрактных терминах, идея навигационного доступа стала тесно связана с процедурным дизайном языка манипулирования данными CODASYL . Например, в 1982 году Цихрицис и Лоховский [2] заявляют, что «понятие валюты занимает центральное место в концепции навигации». Под понятием валюты они подразумевают идею о том, что программа поддерживает (явно или неявно) текущую позицию в любой последовательности записей, которые она обрабатывает, и что такие операции, как GET NEXTи GET PRIORизвлечение записей относительно этой текущей позиции, одновременно изменяя текущая позиция в извлекаемой записи.
Таким образом, программирование навигационных баз данных стало рассматриваться как процессуальное по своей сути ; и, более того, зависеть от поддержания неявного набора глобальных переменных ( индикаторов валюты ), поддерживающих текущее состояние. Таким образом, этот подход рассматривался как диаметрально противоположный стилю декларативного программирования , используемому в реляционной модели . Декларативная природа реляционных языков, таких как SQL, обеспечивала лучшую производительность программистов и более высокий уровень независимости данных (то есть способность программ продолжать работу по мере развития структуры базы данных). 1980-е годы с помощью декларативных языков запросов.
В 1990-е годы стало ясно, что для некоторых приложений, работающих со сложными данными (например, пространственных и инженерных баз данных), реляционное исчисление имеет ограничения. В то время началась переоценка всего рынка баз данных: несколько компаний описывали новые системы, используя маркетинговый термин NoSQL . Многие из этих систем представили языки манипулирования данными, которые, хотя и далеки от CODASYL DML с его валютными индикаторами, можно рассматривать как реализацию «навигационного» видения Бахмана. Некоторые из этих языков являются процедурными; другие (например, XPath ) полностью декларативны. Ответвления навигационной концепции, такие как графовая база данных , нашли новое применение в современных рабочих нагрузках по обработке транзакций .
Навигационный доступ традиционно связан с сетевой моделью и иерархической моделью базы данных и обычно описывает API-интерфейсы манипулирования данными, в которых записи (или объекты) обрабатываются по одной итеративно. Однако важной характеристикой, описанной Бахманом, является поиск записей на основании их отношений с другими записями: поэтому интерфейс все еще может быть навигационным, если он имеет функции, ориентированные на наборы. [3] С этой точки зрения, ключевое различие между языками манипулирования навигационными данными и реляционными языками заключается в использовании явных именованных отношений, а не соединений на основе значений : for department with name="Sales", find all employees in set department-employeesvs.find employees, departments where employee.department-code = department.code and department.name="Sales"
Однако на практике большинство навигационных API были процедурными: приведенный выше запрос будет выполняться с использованием процедурной логики в соответствии со следующим псевдокодом:
получить отдел с именем = 'Продажи'получить первого сотрудника в наборе сотрудников отделадо конца сета do { получить следующего сотрудника в наборе сотрудников отдела сотрудник процесса}С этой точки зрения ключевое различие между навигационными API и реляционной моделью (реализованной в реляционных базах данных ) заключается в том, что реляционные API используют методы «декларативного» или логического программирования , которые запрашивают систему, что именно получать, в то время как навигационные API инструктируют систему в последовательности действий. шаги , как добраться до необходимых записей.
Большинство критических замечаний в отношении навигационных API можно отнести к одной из двух категорий:
В течение многих лет основной защитой навигационных API была производительность. Системы баз данных, поддерживающие навигационные API, часто используют внутренние структуры хранения, содержащие физические ссылки или указатели от одной записи к другой. Хотя такие структуры могут обеспечивать очень эффективную навигацию, у них есть недостатки, поскольку становится сложно реорганизовать физическое размещение данных. Вполне возможно реализовать навигационные API без низкоуровневой погони за указателями (в статье Бахмана предусматривалась реализация логических отношений так же, как в реляционных системах, с использованием первичных и внешних ключей), поэтому эти две идеи не следует объединять. Но без преимуществ в производительности низкоуровневых указателей навигационные API становится все труднее оправдать.
Иерархические модели часто создают первичные ключи для записей путем объединения ключей, которые появляются на каждом уровне иерархии. Такие составные идентификаторы встречаются в именах компьютерных файлов ( /usr/david/docs/index.txt), в URI, в десятичной системе Дьюи и, если уж на то пошло, в почтовых адресах. Такой составной ключ можно рассматривать как представляющий путь навигации к записи; но в равной степени его можно рассматривать как простой первичный ключ, обеспечивающий ассоциативный доступ.
Когда в 1980-х годах реляционные системы приобрели известность, навигационные API (и, в частности, процедурные API) подверглись критике и потеряли популярность. Однако 1990-е годы принесли новую волну объектно-ориентированных баз данных , которые часто предоставляли как декларативные, так и процедурные интерфейсы. Одним из объяснений этого является то, что они часто использовались для представления информации в виде графа (например, пространственных данных и инженерных данных), где доступ по своей сути рекурсивен: математика, лежащая в основе SQL (в частности, исчисление предикатов первого порядка ), не обладает достаточной мощью для поддерживать рекурсивные запросы, даже такие простые, как транзитивное замыкание .
Текущий пример популярного навигационного API можно найти в объектной модели документа (DOM), которая часто используется в веб-браузерах и тесно связана с JavaScript . DOM — это, по сути, иерархическая база данных в памяти с API, который является одновременно процедурным и навигационным. Напротив, к тем же данным ( XML или HTML ) можно получить доступ с помощью XPath , который можно разделить на декларативный и навигационный: доступ к данным осуществляется посредством следующих отношений, но вызывающая программа не выдает последовательность инструкций, которым необходимо следовать по порядку. Такие языки, как SPARQL, используемые для получения связанных данных из семантической сети, также являются одновременно декларативными и навигационными.