Технічні науки

УДК 004.418

Дудкін Юрій Миколайович

студент

Національного технічного університету України

«Київський політехнічний інститут імені Ігоря Сікорського»

Дудкин Юрий Николаевич

студент

Национального технического университета Украины

«Киевский политехнический институт имени Игоря Сикорского»

Dudkin Yuriy

Student of the

National Technical University of Ukraine

«Igor Sikorsky Kyiv Polytechnic Institute»

РОЗРОБКА АЛГОРИТМУ ТРАНЗИТИВНОГО ЗАМИКАННЯ ДЛЯ ОНТОЛОГІЧНО-ОРІЄНТОВАНОЇ СИСТЕМИ

РАЗРАБОТКА АЛГОРИТМА ТРАНЗИТИВНОГО ЗАМЫКАНИЯ ДЛЯ ОНТОЛОГИЧЕСКИ-ОРИЕНТИРОВАННОЙ СИСТЕМЫ

DEVELOPMENT OF ALGORITHM OF TRANSIT PROTECTION FOR ONTOLOGICAL ORIENTED SYSTEM

Анотація. Дана робота містить вирішення проблеми побудови транзитивного замикання для онтологічно-орієнтованої системи.

Ключові слова: онтологічна система, транзитивне замикання, алгоритм, топологічне сортування.

Аннотация. Данная работа содержит решение проблемы построения транзитивного замыкания для онтологически-ориентированной системы.

Ключевые слова: онтологическая система, транзитивное замыкание, алгоритм, топологическое сортировки. 

Summary. This work contains the solution to the problem of constructing a transient closure for an ontology-oriented system.

Key words: ontological system, transitive closure, algorithm, topological sorting. 

Розвиток галузей діяльності людини, що оперують великою кількістю наукової інформації створює необхідність пошуку нових способів зберігання, представлення та обробки великих масивів даних. Одними із можливих підходів роботи з великою кількістю інформації певних предметних областей надають отологічні системи.

Онтологічні системи дуже сильно пов’язані з такою структурою даних, як граф. Така структура даних вимагає ретельного підбору логіки для обробки, оскільки більшість нетривіальних алгоритмів для обробки графу мають велику складність. Також важливим є той факт, що зазвичай такі системи містять високий об’єм даних. Отже оптимізація роботи системи, є однією з самих пріоритетних задач при створення та підтримці такої системи. Серед багатьох можливостей оптимізації є використання транзитивного замикання графу.

Транзитивне замикання графа G (ТЗГ) – це граф G*, що складається з тих же вершин, що і граф G, тобто G* = (V, E*), множиною ребер якого є  [2]. Іншими словами це копія графу G, що також містить ребра для будь-яких вершин, між якими існує шлях у графі G.

Побудова транзитивних зв’язків між поняттями і формування транзитивного замикання графу онтології ґрунтується на правилі [3]:

Отже, для послідовного об’єднання ребер використовується операція множення. На рисунку 1.2 можливо побачити приклад. Для обчислення відстані між вершинами  та , необхідно помножити відстань від вершини  до . З цього можливо вивести формулу для даного випадку: .

Рис. 1. Послідовне розташування вершин

У відповідності до логіки Бьюкенона для обчислення паралельних зв’язків використовується формула попарного об’єднання  [3]. Згідно з формули обчислення паралельних зв’язків кінцева для знаходження відстані від  до  буде

Рис. 2. Паралельне розташування вершин

Розроблений алгоритм пошуку транзитивного замикання використовує ідею топологічного сортування. Алгоритм складається з трьох циклів (рисунок 3). Цикли з лічильником i та лічильником j проходять по топологічно відсортованому списку вершин графу. При цьому цикл j стартує з вершини i + 1.

Рис. 3. Візуалізація роботи алгоритму

Третій цикл – це прохід по батьківським вершинам вершини j. Під час проходу перевіряється чи існує зв’язок між вершиною i та батьківською вершиною p вершини j.

Якщо такий зв’язок існує, тобто існує ребро між вершиною i та вершиною p викликається функція setCohesion(), що зберігає транзитивний зв’язок між вершинами i та j. Сама функція використовує властивість послідовного множення фактору впевненості транзитивного замикання (рисунок 4). Для цього відбувається множення фактору впевненості від вершини i до p на фактор впевненості від p до j. Фактор впевненості i та p уже обчислений і має очікуване значення, це гарантує топологічний порядок циклів.

Рис. 4. Функція збереження зв’язку

У разі, якщо уже існує зв’язок між вершинами i та j, кінцевий коефіцієнт впевненості знаходиться за формулою паралельного множення. Тобто для випадку коли від i до j існує певне значення фактору впевненості , то буде використано формулу для паралельного множення нового шляху від i до j –  . Після отриманного значення функція записує фактор впевненості у структуру Closure, що зберігає транзитивні звязки для вершин. Після збереження зв’язку функція закінчує свою роботу.

Висновки. Отже для побудови транзитивного замикання графа для онтологічно-орієнтованої системи було розроблено алгоритм. Основна ідея розробленого алгоритму – використання топологічного сортування. Аналітичним шляхом можливо знайти знайти вартість – , де V- це кількість вершин графу. Така вартість є задовільною для роботи системи. 

Література

1. Мельников Онтологии как системы хранения знаний [Електронний ресурс]. – Режим доступу: http://www.ict.edu.ru/ft/005706/68352e2-st08.pdf.
2. Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall) [Електронний ресурс]. – Режим доступу: http://www.niss.gov.ua/articles/252.
3. Tytenko, S. (2010). Construction of didactic ontology based on the analysis of the elements of the conceptual-thesaurus model. Naukovi Visti NTUU KPI, 1(69), pp.82-87. (in Ukrainian).P
4. Novak. Concept mapping: A useful tool for science education. Journal of Research in Science Teaching, 27:937-949, 199.