Как представить неявные отношения?

Question

Я разрабатываю приложение, в котором мне приходится иметь дело с сущностью с именем «Умение». Теперь дело в том, что «Навык А» может иметь определенную релевантность с «Навыком В» (релевантность используется в целях поиска). Точно так же «Навык B» также может относиться к «Умению C». В настоящее время у нас есть следующая модель данных для представления этого сценария

Skill {SkillId, SkillName}

RelevantSkill {SkillId, RelevantSkillId, RelevanceLevel}

Теперь, учитывая приведенный выше сценарий, мы имеем неявную связь между «Умением А» и «Умением С». Какой будет оптимальная модель данных для этого сценария? Мы также должны были бы пересечь эту иерархию при выполнении поиска.

Answer 1

То, что вы запрашиваете, - это, по сути, алгоритм расстояния на графике (структура данных с косой чертой), вычисляемый из набора парных расстояний. Разумная (и хорошо вычисляемая) метрика: время в пути .

Можно думать так: построить граф, в котором каждый узел является навыком, а каждое ребро представляет релевантность узлов, которые он соединяет друг с другом. Теперь представьте, что вы начинаете с какого-то узла на графике (с некоторого навыка) и случайно перепрыгиваете на другие узлы вдоль определенных ребер. Скажем, вероятность перехода от навыка A к навыку B пропорциональна релевантности этих навыков друг другу (нормализуется по релевантности этих навыков другим навыкам ...). Теперь время коммутирования представляет собой среднее количество шагов, необходимых для перехода от навыка A к навыку C.

Это имеет очень приятное свойство, заключающееся в том, что добавление большего количества путей между двумя узлами сокращает время коммутирования: если навыки A и B, B и C, C и D, а также D и A связаны, то время коммутирования между A и С будет еще короче. Более того, время коммутирования может быть легко вычислено с использованием разложения по собственным значениям вашего редко связанного графа умений (я думаю, что ссылка, которую я дал вам, показывает это, но если нет, то их много).

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

Удачи, и я надеюсь, что это помогло!

Answer 2

Что-то осталось открытым в вашем объяснении, как сочетания уровней релевантности в случае косвенных («неявных») отношений. Например. если навык A относится к B с уровнем 3, а навык B относится к навыку C с уровнем 5, каков уровень (как число) косвенного отношения навыка A к навыку C?

Надлежащая модель данных зависит от двух вещей: сколько у вас навыков, и насколько плотной является структура отношений (плотная = много навыков имеют отношение к другим). Если структура отношений плотная и у вас мало навыков (<1000), лучше всего представлять все как матрицу. </p>

Но если у вас много навыков, но скудная структура отношений, вы можете представить ее в виде трех таблиц:

Skill {SkillId, SkillName}

RelevantSkill {SkillId, RelevantSkillId, RelevanceLevel}

IndirectRelevance { SkillId, RelevantSkillId, RelevanceLevel}

Третья таблица (IndirectRelevance) рассчитывается на основе двух основных таблиц; каждый раз, когда вы меняете таблицы Skill или RelevantSkill, вам необходимо обновлять таблицу IndirectRelevance.

Я думаю, что лучше иметь три стола, чем два; это делает реализацию более чистой и простой. RelevantSkill содержит явно установленные отношения; Косвенная релевантность всех производных фактов.

Answer 3

Ваш лучший выбор:

1. увеличить RelevantSkill с помощью логического столбца ImplicitRelevance:

   RelevantSkill {SkillId, RelevantSkillId, RelevanceLevel, ImplicitRelevance}

2. вставка (в таблицу RelevantSkill) строк, соответствующих всем неявным (косвенным) отношениям релевантности (например, «Умение A» -> «Умение C») с их соответствующими вычисленными RelevanceLevel s, тогда и только тогда, когда вычисленное значение RelevanceLevel превышает установленный порог . В этих строках ImplicitRelevance должно быть установлено true

   skill_a_id, skill_b_id, computed_level, 'T'

Если в явные уровни релевантности (метрики) были внесены какие-либо изменения, удалите все строки с ImplicitRelevance = true и заново пересчитайте (заново вставьте) их.

Answer 4

Есть несколько факторов, которые необходимо учитывать, прежде чем вы сможете выбрать лучшие варианты:

• сколько там умений?
• Являются ли отношения разреженными или плотными (т. Е. Связаны ли навыки со многими другими навыками)?
• как часто они меняются?
• есть ли порог релевантности (минимальная релевантность, которая вас интересует)?
• как рассчитывается релевантность нескольких путей?

Структура, очевидно, будет похожа на предложенную antti.huima. Разница в том, как IndirectRelevance будет реализован. Если есть много изменений, много отношений и отношений плотные, то лучшим способом может быть хранимая процедура (возможно, доступная через представление). Если отношения редки и порог существует, лучшим вариантом может быть материализованное представление или таблица, обновляемая с помощью триггеров.