Навигационный доступ к данным¶

Навигационный доступ к данным — это способ организации доступа к информации в базах данных, файловых системах или иерархических структурах, при котором пользователь или программа перемещается по заранее определённым связям между элементами данных, используя указатели, ссылки или индексы. В отличие от реляционного доступа, основанного на запросах к таблицам по условиям, навигационный доступ предполагает последовательное или ветвящееся перемещение по структуре, напоминающей граф или дерево. Этот метод широко применяется в системах управления базами данных (СУБД), файловых системах операционных систем, а также в объектно-ориентированных и графовых базах данных.

¶История

Навигационный доступ к данным возник на ранних этапах развития вычислительной техники, когда данные хранились на магнитных лентах и барабанах, а доступ к ним требовал физического перемещения считывающей головки. Первые системы управления базами данных, такие как IMS (Information Management System) компании IBM, разработанная в 1966 году, использовали иерархическую модель, где записи связывались в древовидные структуры. Пользователь мог перемещаться от корневой записи к дочерним, следуя по указателям.

В 1969 году появилась сетевая модель данных, предложенная Чарльзом Бахманом и реализованная в СУБД IDMS. В этой модели записи могли иметь несколько родителей и потомков, образуя граф. Доступ к данным осуществлялся через навигационные операции, такие как «найти первую запись», «найти следующую запись» или «перейти по связи». Бахман получил премию Тьюринга в 1973 году за эту работу.

С развитием реляционной модели в 1970-х годах, предложенной Эдгаром Коддом, навигационный доступ уступил место декларативным запросам на языке SQL. Однако навигационные методы не исчезли полностью: они сохранились в файловых системах (например, перемещение по каталогам), в объектных базах данных (Object DBMS) и в современных графовых базах данных (Neo4j, Amazon Neptune). В 1980-х годах появились гибридные системы, сочетающие реляционные и навигационные подходы, такие как PostgreSQL с поддержкой рекурсивных запросов.

¶Принципы работы

Навигационный доступ основан на явном задании путей перемещения между элементами данных. Основные компоненты:

Указатели (pointers) — ссылки на физические адреса или логические идентификаторы записей. Например, в файловой системе указателем может быть inode, указывающий на блоки данных файла.
Связи (links) — отношения между записями, определённые в схеме данных. В иерархической модели это отношения «родитель-потомок», в сетевой — произвольные связи.
Индексы — структуры, ускоряющие поиск начальной точки навигации (например, B-деревья в файловых системах).

Процесс доступа включает следующие шаги:

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

В отличие от реляционного доступа, где запрос формулируется в терминах условий (например, SELECT * FROM employees WHERE salary > 50000), навигационный доступ требует знания структуры данных и последовательности шагов.

¶Виды навигационного доступа

¶Иерархический доступ

Применяется в системах с древовидной структурой, где каждая запись имеет ровно одного родителя. Пример — файловые системы (каталоги и файлы) или СУБД IMS. Пользователь перемещается от корня к листьям, используя пути (например, /home/user/docs/file.txt).

¶Сетевой доступ

Используется в графовых структурах, где записи могут быть связаны произвольно. Пример — СУБД IDMS или современные графовые базы данных. Навигация осуществляется по рёбрам графа, например, «найти всех друзей друга».

¶Объектный доступ

Характерен для объектно-ориентированных баз данных (ObjectStore, Versant). Доступ к данным происходит через ссылки на объекты в памяти, подобно указателям в языках программирования (C++, Java). Навигация может быть как последовательной, так и по связям между объектами.

¶Файловый доступ

В операционных системах навигационный доступ реализован через API, такие как opendir, readdir в POSIX-системах или Directory.GetFiles в Windows. Пользователь перемещается по дереву каталогов, используя относительные или абсолютные пути.

¶Применение

¶Системы управления базами данных

Навигационный доступ используется в:

Иерархических СУБД — IMS, IBM Db2 for z/OS (режим иерархического доступа).
Сетевых СУБД — IDMS, Raima Database Manager.
Графовых СУБД — Neo4j, ArangoDB, OrientDB. В них навигация выполняется с помощью языка запросов Cypher (например, MATCH (a)-[:KNOWS]->(b)).
Объектных СУБД — ObjectDB, db4o.

¶Файловые системы

Все современные операционные системы (Windows, Linux, macOS) используют навигационный доступ для работы с файлами и каталогами. Команды cd, ls (Unix) или dir, cd (Windows) являются примерами навигационных операций.

¶Веб-технологии

Навигационный доступ применяется в:

XML-документах — с помощью языков XPath и XQuery, где навигация по дереву элементов осуществляется через пути (например, /bookstore/book/author).
JSON-структурах — через точечную нотацию (например, data.users[0].name) или библиотеки вроде JSONPath.

¶Встроенные системы

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

¶Преимущества и недостатки

¶Преимущества

Высокая скорость при работе с предопределёнными связями, особенно в графовых структурах, где навигация по рёбрам может быть быстрее реляционных JOIN-ов.
Эффективность для иерархических данных — например, для файловых систем или XML-документов.
Интуитивность для программистов, привыкших к работе с указателями и ссылками.

¶Недостатки

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

¶Примеры

¶Файловая система Linux

Пользователь хочет прочитать файл /home/user/docs/report.txt. Навигационный доступ включает:

Переход в корневой каталог (/).
Поиск каталога home.
Переход в home.
Поиск каталога user.
Переход в user.
Поиск каталога docs.
Переход в docs.
Поиск файла report.txt.
Чтение данных.

¶Графовая база данных Neo4j

Запрос на поиск друзей друга: `` MATCH (a:Person {name: 'Иван'})-[:KNOWS]->(b)-[:KNOWS]->(c) RETURN c.name `` Здесь навигация происходит по рёбрам KNOWS от узла «Иван» к узлам b, затем к узлам c.

¶XML-документ

XPath-выражение для получения авторов книг: `` /bookstore/book/author `` Навигация идёт от корневого элемента bookstore к book, затем к author.

¶Интересные факты

Термин «навигационный доступ» популяризировал Чарльз Бахман в своей статье 1973 года «The Programmer as Navigator».
В 1970-х годах навигационные системы доминировали, но с появлением SQL в 1974 году (System R от IBM) реляционные системы начали вытеснять их.
В современных системах навигационный доступ часто сочетается с реляционным: например, PostgreSQL поддерживает рекурсивные CTE (Common Table Expressions), позволяющие выполнять навигационные запросы.
Графовые базы данных, такие как Neo4j, вновь сделали навигационный доступ популярным в эпоху Big Data и социальных сетей.

¶Критика

Навигационный доступ критикуется за:

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

Тем не менее, в определённых областях (графовые данные, файловые системы, XML) навигационный доступ остаётся незаменимым инструментом.

¶Источники

Бахман Ч. «The Programmer as Navigator». Communications of the ACM, 1973.
Кодд Э. «A Relational Model of Data for Large Shared Data Banks». Communications of the ACM, 1970.
Дейт К. «Введение в системы баз данных». 8-е издание, 2004.
Документация Neo4j: «Cypher Query Language Reference».
Стандарт POSIX.1-2017: «File System Interface».
Рекомендации W3C: «XML Path Language (XPath) 3.1».

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →