OpenU.Ru
Указывает, можно ли эффективно проследить бинарную ассоциацию от одного объекта
таким образом, чтобы получить ассоциированный с ним другой объект или множество
объектов. Это понятие не применяется к n-арным ассоциациям. Эффективность навигации
связана с понятием навигации, однако.tie является его определяющим свойством.
См. navigability.
Семантика
Эффективность навигации можно определить с общей точки зрения, применимо к
абстрактному проектированию, а также к различным языкам программирования. Бинарная
ассоциация допускает эффективную навигацию в том случае, если средние затраты
на получение множества ассоциированных объектов пропорциональны действительному
числу объектов в этом множестве (но не верхней границе множественности, которая
может быть и неограниченной), плюс фиксированная константа. В терминах, определяющих
сложность вычислений, затраты должны составлять 0(п).
Если множественность равна единице или "нуль - единица", то затраты
на доступ должны быть постоянными, что исключает поиск в списке переменной длины.
При немного более свободном определении эффективности навигации допустимые затраты
могут составлять log(n).
Обычно допускающая навигацию ассоциация с множественностью, равной единице,
реализуется с помощью указателя, добавляемого в блок, где содержатся атрибуты
объекта. Однако возможен и другой внешний вариант реализации с использованием
кэш-таблиц, обеспечивающий постоянную среднюю стоимость доступа. То есть ассоциацию
можно реализовать в виде объекта-справочной таблицы, которая, хоть и находится
вне участвующих в ассоциации классов, обеспечивает возможность навигации между
объектами этих классов. (В некоторых ситуациях, при выполнении в реальном времени,
нужно ограничивать скорее не средние затраты, а максимально допустимые. Для
этого в базовое определение не требуется вносить других изменений, кроме как
замену среднего времени на максимально допустимое. Однако вероятностные алгоритмы,
такие как хэш-таблицы, придется исключить.)
Если ассоциация не допускает навигацию в нужном направлении, это не означает,
что ее вообще нельзя проследить - просто затраты на это могут оказаться слишком
значительны (например, в случае поиска в очень большом списке). Если доступ
в этом направлении осуществляется редко, то поиск будет вполне приемлемым решением.
Эффективность навигации представляет собой концепцию проектирования, которая
дает разработчику возможность задавать пути доступа к объектам, принимая во
внимание затраты на вычисления. Как правило, говоря о возможности навигации,
подразумевают се эффективность.
Ассоциация, которая не допускает эффективной навигации ни в одном из направлений,
также возможна (хотя встречается она нечасто). Такую ассоциацию можно реализовать
в виде списка связей, в котором осуществляется поиск нужной связи для прослеживания
навигации в нужном направлении. Такое прослеживание возможно, однако не эффективно.
При моделировании такая ассоциация едва ли может оказаться полезной.
Обсуждение
Эффективность навигации указывает на эффективность, с которой определенный
объект может получить доступ к множеству связанных с ним других объектов. Когда
множественность представляет
собой 0..1 или 1, то реализацией будет указатель в исходном объекте. При множественности
"много" реализацией станет класс-контейнер, в котором содержится множество
указателей. Сам класс-контейнер может постоянно присутствовать в виде записи
данных объекта этого класса. В любом случае доступ к нему должен осуществляться
с постоянными затратами (что является обычной ситуацией при использовании для
доступа указателя). Сам класс-контейнер должен обладать эффективной навигацией.
Например, простой список всех связей ассоциации не будет эффективным, так как
связи для отдельного объекта будут перемешаны с другими, не относящимися к делу
связями, и придется делать поиск. А вот список связей объекта, хранящийся с
самим объектом, будет эффективным, так как дополнительный поиск в этом случае
не нужен.
Если навигация в квалифицированной ассоциации установлена в направлении от кодификатора,
это означает, что она эффективна для получения объекта или множества объектов
на основе исходного объекта и значения квалификатора. Это соответствует реализации
и виде хэш-таблицы или поиска по бинарному дереву, индексированному значением
квалификатора (поэтому квалификаторы используются в качестве обычной концепции
моделирования).