ВЫСОКОУРОВНЕВЫЙ ИНТЕРФЕЙС ДОСТУПА К ДАННЫМ НА ОСНОВЕ ПЕРЕПИСЫВАНИЯ ЗАПРОСОВ

В ноябре прошлого года я писала об OWL и синтаксисе описаний онтологий. В этой статье рассказывается о теоретических основах представления знаний в виде онтологий, о проблеме хранения данных и задаче ODBA.
* * *

Задача ODBA

С развитием концептуального моделирования (ООП, UML) и усложнения систем возникает необходимость обеспечения информационной системы высокоуровневым интерфейсом для работы с большими объемами данных. Такой интерфейс можно обеспечить за счет представления знаний о предметной области в форме онтологического описания (базы знаний). Задача доступа к данным через высокоуровневый интерфейс онтологии называется ontology-based data access (ODBA). Решение должно удовлетворять следующим требованиям: 1) эффективное выполнение запросов, которые в идеале должны выполняться с той же скоростью, что и SQL-запросы над существующими РБД, и 2) обработка запросов должна использовать все преимущества реляционных технологий, уже используемых для хранения данных.

База знаний и задачи логического вывода

База знаний (knowledge base, KB) – описание предметной области в виде онтологии – позволяет извлекать данные (ABox), хранящиеся в БД, с учетом ограничений, накладываемых на более высоком концептуальном уровне (TBox):
KB = ABox+TBox,
Где ABox – assertional box – Множество данных, хранящихся в БД;
TBox – terminological box – Концептуальная модель данных, например, Entity-Relationship.
В качестве языка представления знаний используется дискриптивная логика (ДЛ) определенного уровня выразительности. Уровень выразительности определяется как набор аксиом, разрешенных в TBox и ABox. С одной стороны, язык должен быть как можно более выразительным, чтобы полностью описать предметную область; с другой стороны, задачи логического вывода над KB должны иметь приемлемую вычислительную сложность.
Пусть дана KB K=(T,A). Фундаментальными задачами логического вывода (reasoning) являются:

  • Выполнимость (satisfiability). Требуется проверить, существует ли модель K.
  • Проверка экземпляра (instance checking). Пусть даны объект a и класс C. Требуется определить, что K⊨C(a), или является ли a^I∈C^I для каждой модели I KB K.
  • Ответ на запрос (query answering). Пусть дан запрос q(x ⃗ ) и кортеж a ⃗ объектов из A. Требуется определить, что K⊨q(a ⃗), или a ⃗ является ответом на запрос q(x ⃗ ) относительно K.
  • Вычислительная сложность задач зависит от переменного и некоторого фиксированного числа входных параметров. Входными параметрами являются: размер TBox, |T|,размер ABox, |A|, размер K=(T,A), размер запроса – число параметров запроса q(x ⃗ ), |x ⃗ |=N.
    Для задач логического вывода различают комбинированную сложность (combined complexity) и сложность по объему данных (data complexity). В контексте задачи ODBA рассматривают сложность по объему данных, считая размер TBox фиксированным и размер запроса пренебрежимо малым, по сравнению с объемом данных ABox.

    Представление знаний в DL-Lite

    Для концептуального моделирования наряду с UML и ER предложены языки семейства DL-Lite. Общими чертами логик семейства DL-Lite являются следующие – 1) нет возможности привязки ролей к конкретным концептам, все роли могут быть применены ко всем концептам (∃R.C),C=⊺; 2) нет возможности определения покрытия предметной области в виде дизъюнкции концептов.
    Максимально выразительным языком для концептуального моделирования, для которого вычислительная сложность query answering не будет превосходить P, является 〖DL-Lite〗_horn^HF. Если ввести дополнительное ограничение UNA (unique name assumption): a_i^I≠a_j^I,i≠j, то query answering в 〖DL-Lite〗_horn^((HF)|(HN)) будет иметь наименьшую вычислительную сложность по объему данных – AC^0 . Следствием этого является важное свойство:

  • Пусть дана база знаний K=(T,A), удовлетворяющая 〖DL-Lite〗_horn^((HF)) с UNA, конъюнктивный (не содержащий дизъюнкций) запрос q(x ⃗ ). Тогда q(x ⃗ ) и TBox могут быть переписаны в виде объединения конъюнктивных запросов SQL(q(x ⃗ )) только над ABox, и ответ на этот запрос будет непротиворечивым (sound) и полным (complete).
  • На этом свойстве основано переписывание запросов (query rewriting), которое позволяет получить базу знаний на основе традиционной БД, работать с данными на концептуальном уровне независимо от конкретной схемы БД, эффективно используя все преимущества современных реляционных СУБД.
    Для систем, работающих с большими объемами данных, для которых основной задачей является query answering, консорциумом W3C предложен стандарт OWL 2 QL, который основан на еще менее выразительном, чем 〖DL-Lite〗_horn^((HF)), подмножестве аксиом 〖DL-Lite〗_core^H (другое обозначение – 〖DL-Lite〗_R^ ). Сложность всех задач логического вывода над онтологиями 〖DL-Lite〗_core^H не превосходит полиномиальной. Такое существенное ограничение было введено потому, что в OWL вместо UNA используется прямое обозначение равенства либо неравенства имен. Чтобы сложность задач логического вывода на онтологиях по стандарту OWL 2 QL оставалась постоянной, было решено не включать возможности определения функциональных зависимостей и числовых ограничений между концептами, при которых вычислительная сложность зависит от принятия/непринятия UNA.

    Переписывание запросов для высокоуровневого интерфейса доступа к данным

    Для OWL 2 QL активно разрабатываются алгоритмы переписывания запросов (query rewriting), которые позволят выполнять концептуальный query answering над имеющимися БД.
    В настоящий момент известно 2 алгоритма переписывания запросов. Алгоритм CGLLR для DL-Lite реализован в нескольких системах QuOnto, Owlgres, ROWLKit, алгоритм RQR для DL-Lite+ был представлен в 2009-м году и реализован в REQUIEM. Алгоритмы CGLLR и RQR возвращают одинаковые результаты переписывания запросов. В процессе переписывания каждый алгоритм порождает большое количество – порядка нескольких тысяч – UCQ (unique conjunctive query). Это приводит к формированию сложных SQL-запросов с большим количеством объединений (UNION), которые могут быть практически невыполнимы для СУБД.
    Ведется активная работа по оптимизации этих алгоритмов в следующих направлениях:

  • Упрощение первичного запроса q(x ⃗ ) с помощью резолюций;
  • Исключение UCQ, для которых не задано отображение (OWL->RDB mapping).
  • Оптимизированный RQR генерирует меньше UCQ, чем CGLLR, его можно использовать для более выразительных языков ДЛ, чем DL-Lite. Однако RQR все еще демонстрирует низкую эффективность на больших реальных объемах данных, не защищен от зацикливания и требует дополнительной информации для повышения скорости переписывания запросов.

    Ссылки

  • Franconi. Propositional logic.
    http://www.inf.unibz.it/~franconi/dl/course/slides/logic/propositional/prop-logic-1.pdf
  • The DL-Lite Family and Relations
    http://www.dcs.bbk.ac.uk/~michael/DL-LiteFamily.pdf
  • OWL 2 Web Ontology Language
    Profiles – W3C Recommendation, actual October 27, 2009
    http://www.w3.org/TR/owl2-profiles/#OWL_2_QL
  • H.ector P.erez-Urbina, Ian Horrocks, and Boris Motik. Practical Aspects of Query Rewriting for OWL 2
    http://www.webont.org/owled/2009/papers/owled2009_submission_17.pdf
  • Leave a comment

    Filed under Uncategorized

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s