Верес Д. С. СУЧАСНІ СХОВИЩА RDF ДАНИХ

Категорія: Простір і час сучасної науки (18-20.04.2016), Сучасні інформаційні технології

УДК: 004.42

 

СУЧАСНІ СХОВИЩА RDF ДАНИХ

Верес Д. С.

Національний технічний університет України “Київський політехнічний інститут”, Україна, Київ

 

Resource Description Framework – модель представлення даних, розроблена World Wide Web Consortium (W3C) у 1999 році, стала наріжним каменем технологій семантичної павутини та мережі даних. Через зростаючу популярність даної моделі, з’являється більша кількість наборів даних описаних за допомогою її засобів. Із зростаючою популярністю, з’явилась необхідність в ефективних засобах зберігання та звернення до великих наборів RDF даних.

У статті розглянуті основні види баз даних, які використовуються для зберігання RDF графів, проведено їх порівняльний аналіз та визначено ключові переваги та недоліки.

Ключові слова: сховища даних, бази даних, RDF, SPARQL, реляційні СУБД, NoSql, індексування даних.

 

Верес Д. С. Современные хранилища RDF данных / Национальный технический университет Украины “Киевский политехнический институт”

Resource Description Framework – это модель представления данных, разработанная World Wide Web Consortium (W3C) в 1999 году, что стала краеугольным камнем технологий семантической паутины и сети данных. Благодаря возрастающей популярности данной модели, возрастает количество наборов данных описанных её средствами. Вместе с популярностью, появляется необходимость в эффективных средствах хранения и обращения к большим наборам RDF данных.

В статье рассмотрены основные виды баз данных, что используются для хранения RDF графов, проведен их сравнительный анализ и определены их основные достоинства и недостатки.

Ключевые слова: хранилища данных, базы данных. RDF, SPARQL, реляционные СУБД, NoSql, индексирование данных.

 

Veres D. S. RDF data storages / National Technical University of Ukraine “Kyiv Polytechnic Institute”

Resource Description Framework – is a model of data representation that was designed by World Wide Web Consortium (W3C) in 1999 and became a cornerstone of the Semantic Web and the Web of Data technologies. It’s growing popularity, caused an increasing number of data sets, that were represented by this model. With this popularity came the need to efficiently store, query and reason over large amounts of RDF data.

This article is a review of basic database types, that are used for RDF graphs storage. These types were analyzed and compared, verified their most important benefits and drawbacks.

Keywords: data stores, databases, RDF, SPARQL, relational DBMS, NoSql, data indexing.

 

Вступ. Вибір фізичної організації зберігання та індексування RDF даних має великий вплив не тільки на загальний можливий розмір набору даних, цей вибір безпосередньо впливає на продуктивність основних операцій RDF сховища таких як обробка запитів та виведення логічних висновків. Зважаючи на порівняно коротку історію (в порівнянні з традиційними системами управління реляційними базами даних, що вперше з’явились на початку 80х) модель даних RDF (перші рекомендації W3C датуються 1999) та появу перших RDF сховищ, розробка та дослідження ефективних систем для зберігання все ще лишається відкритою проблемою. Це підтверджує зростаюче число доповідей, присвячених семантичним базам даних, на наукових конференціях. Більш того, свій інтерес в даній сфері показали такі гіганти індустрії програмного забезпечення як Oracle, IBM та Microsoft, що свідчить про важливість проблеми та життєздатність ринку семантичних рішень.

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

Під native підходом можна розуміти шляхи та методи зберігання RDF даних ближче до її моделі даних уникаючи необхідності додаткових перетворень даних у сутності СУБД. Native сховища даних використовують стандартну для RDF модель триплетів, що дозволяє залучити підходи теорії графів для роботи з моделлю даних. Дані системи можна класифікувати як постійні (використовують записи на диск) та непостійні (використовують лише оперативну пам’ять).

Постійні сховища дають можливість зберігати дані в файловій системі. Такі реалізації використовують такі широковідомі індексуючі структури як B+-дерева, що також використовуються у реляційних СУБД. Вважається, що вузьким місцем даних сховищ є необхідність постійного читання та запису в зовнішню пам’ять, які є досить повільними та “важкими” операціями. Зважаючи на це, з’явились рішення, що намагаються зберігати як най більше інформації (RDF триплети, словники, таблиці онтологій) в оперативній пам’яті. Для зберігання RDF даних такі бази виділяють певний об’єм пам’яті, достатній для зберігання повної графової структури.

Non-native підхід означає зберігання RDF даних у СУБД, які для цієї задачі не призначені. Оскільки такі СУБД (особливо реляційні) досліджуються та розробляються багато років, їх перевагою є більша зрілість та досконалість технологій. Зокрема, переважна більшість реляційних СУБД мають підтримку транзакцій та політик безпеки, яких бракує сучасним native RDF сховищам.

Реляційні СУБД можна розділити на схемо-залежні та схемо-незалежні підходи. Схемо-незалежний підхід означає, що всі триплети зберігаються в одній таблиці, що зветься таблицею триплетів. На відміну від такого підходу, який є досить прямолінійним, схемо-залежних СУБД весь набір триплетів розподіляється по різним таблицям базуючись на визначеній схемі бази даних. Таке розділення можна організувати використовуючи властиву триплетам структуру (суб’єкт, об’єкт, предикат), або базуючись на OWL класах.

Порівняння native і non-native підходів. Розробка СУБД з native типом зберігання даних зазвичай починається з нуля, через це подібні розробки вимагають велику кількість зусиль на дизайн та розробку системи. В порівнянні з цим, non-native підхід дозволяє зменшити кількість необхідних дизайнерських рішень за допомогою використання готових продуктів з необхідною функціональністю. Так, використовуючи цей підхід, можна використати готові та перевірені часом реалізації індексування, підтримки ACID та оптимізацію виконання SQL запитів. Проте, для досягнення задовільної ефективності роботи, необхідно взяти до уваги обов’язкові перетворення в моделі даних (з графової в реляційну) та транслювання мовних конструкцій SPARQL в SQL.

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

Такі системи використовують багато індексний підхід. Це зумовлено двома чинниками: структурою RDF даних та необхідністю ефективного оперування всіма формами триплетних шаблонів в ході обробки запитів [2]. Очевидно, індексування триплетів що містять IRI або літерал, підвищує ефективність обробки запитів. Наприклад, при пошуку значення змінної ?x триплету “?x p s”, де змінна є суб’єктом, а об’єкт та предикат – літерали, буде на багато ефективнішим використовувати зв’язку “pos” чи “ops”, а ніж “spo” “sop”.

Високостиснені сховища. З появою феномену великих даних та зростаючим об’ємом RDF даних, почалась розробка систем, що використовують підходи стиснення даних. Розрізняють дві основні групи таких підходів: мультиіндекусування і самоіндексуючі структури даних.

Мультиіндексування. Сховища, що базуються на підході мультиіндексування, в своїй основі мають матричні бітові структури. Такі структури зберігаються в оперативній пам’яті і мають на меті збільшити компактність представлення RDF триплетів. Кожен триплет характеризується тривимірною сутністю, а граф є тривимірним бітовим кубом, кожна комірка якого відповідає за унікальний триплет та визначає його присутність чи відсутність у графі [3]. Для представлення тривимірного бітового куба в пам’яті, його перетворюють у двовимірну бітову матрицю. Головною ідеєю методу мультиіндексування є використання компактного представлення великих наборів RDF триплетів в оперативній пам’яті. Даний підхід дозовляє використовувати одну універсальну таблицю для збереження всіх триплетів. При цьому таблиця може бути горизонтально легко розділена на певну кількість фрагментів.

Само індексування. Нещодавно такі системи як HDT та WaterFowl почали використовувати високостиснені структури даних SDS (succinct data structures). Система HDT в основному фокусується на обміні даними, її основною метою була підтримка передачі великих наборів стиснених даних за допомогою SDS [4]. Згодом була розроблена система HDT FoQ, яка по суті є доповненням HDT, що пропонує набір простих операцій вибірки даних. Не зважаючи на це, дана система не все ще не дозволяла виконувати складні запити. Підхід запропонований HDT FoQ був розвинений і вдосконалейний у WaterFowl, де замість списку суміжності на об’єктному рівні використовувались вейвлет дерева та було введено повноцінну підтримку запитів. Архітектура самоіндексуючих сховищ базується на використання SDS і довзволяє використовувати самоіндексуюче компактне представлення триплетів, що не вимагає декомпресії в процесі обробки запитів. Під само індексуванням мається на увазі можливість відтворення оригінального документу за допомогою єдиного індексу [5]. Високий рівень стиснення, отриманий завдяки використанню SDS дозволяє системі зберігати всі дані в оперативній пам’яті і мінімізує затримки пов’язані з операціями вводу та виводу за допомогою оптимізованих алгоритмів серіалізації/десеріалізації.

Системи, що базуються на РСУБД. Використання таблиці триплетів є, мабуть, найбільш прямолінійним рішенням для зберігання RDF даних в реляційних СУБД. Кожне RDF твердження у формі [суб’єкт, предикат, об’єкт] зберігається як триплет в єдиній великій таблиці з три колонковою схемою (по одній колонці для суб’єкта, предиката та об’єкта відповідно). Для підвищення швидкості пошуку записів, створюється певна кількість індексів для кожного стовпця. Цей підхід дозволяє зменшити кількість операцій необхідних для об’єднання записів. Проте, з ростом набору даних, швидкість виконання запитів стрімко спадає. Причиною цьому є неможливість тримати всю таблицю в оперативній пам’яті, яка породжує необхідність використовувати повільні операції запису та читання з / на диск. Зважаючи на це, варто зазначити, що дані системи показують задовільні показники ефективності лише при виконанні простих запитів на наборах малого чи середнього розміру (до 10 мільйонів триплетів).

Висновки. В статті описані основні види баз даних, що використовуються для зберігання RDF графів. Всі існуючі на даний момент рішення можна розділити на native, тобто ті, в основі яких лежить модель представлення RDF, та non-native, до яких відносять інші реляційні або NoSql бази даних. Був проведений порівняльний аналіз обох підходів та визначені переваги та недоліки кожного з них. Особливу увагу було приділено методам індексування native RDF сховищ та описані методи мультиіндексування та само індексування. Метод мультиіндексування лежить в основі більшості популярних RDF сховищ, проте не забезпечує найвищу швидкість опрацювання запитів до графу. В свою чергу само індексування мінімізує затримки при виконанні запитів, але при цьому може використовуватись лише у режимі читання, оскільки додавання нових даних спричиняє виконання досить повільного процесу пере індексації.

З рештою, native та non-native сховища RDF даних мають свої переваги та недоліки, які потрібно враховувати при розробці архітектури інформаційних систем.

 

References:

1. Kolas D., Emmons I., Dean M. Efficient linked-list RDF indexing in parliament // Proceedings of the 5th International Workshop on Scalable Semantic Web Knowledge Base Systems. Washington, DC: IEEE Computer Society. – 2009. – P. 17–32.

2. Neumann, T., Weikum, G. Scalable join processing on very large RDF graphs // SIGMOD Conference, Indianapolis, Indiana, USA. – 2009. – P. 627–640.

3. Atre J. S., Hendler J. A. Bitmat: a main memory RDF triple store. Technical report // Tetherless World Constellation, Rensselar Plytehcnic Institute, Troy NY. – 2009 – P. 1-10.

4. Fernandez J. D., Martinez-Prieto M. A., Gutierrez C. Compact representation of large RDF data sets for publishing and exchange // International Semantic Web Conference. – 2010. – Vol. 1. – P. 193–208.

5. Martinez-Prieto M. A., Gallego M. A., Fernandez J. D. Exchange and consumption of huge RDF data // ESWC. – 2012. – P. 437 – 452.

 

 

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Коментар:
Введите код: *

Карта сайту

^