1

Тема: Вопросы по хранению онтологий в СУБД

Всем привет! Это мой первый пост. Я сравнительно недавно изучаю вопросы семантической сети (как сказать изучаю - читаю что под руку попадется, в основном онлайн публикации). По ходу занимаюсь небольшим проектом, который каким-то боком связан с семантической сетью.

Так что знаю я не очень много, поэтому заранее прошу снизойти к моей неинформированности во многих вопросах.

Появилось несколько вопросов по этой теме.

1. Как можно более эффективно хранить онтологии? Я понимаю, что есть языки типа OWL, основанные на XML, который в свою очередь сложнее обрабатывать (мне кажется), чем данные, хранимые в СУБД.

2. Можно ли использовать такую схему хранения онтологии в СУБД?

Таблица 1: классы (понятия)
понятие, отношение (к родителю), родитель (понятие)

Таблица 2: атрибуты
атрибут, возможные значения

Таблица 3: пары понятий-атрибутов
понятие, атрибут

2

Re: Вопросы по хранению онтологий в СУБД

Вы не уточнили тип используемой СУБД.

Если есть RDF-хранилище, то просто загрузите онтологию в хранилище.

Если нет RDF-хранилища, но есть разумный оптимизатор SQL, то сделайте простейшее хранилище RDF сами:
--- таблица целочисленных идентификаторов для всех используемых URL;
--- таблица квадов (Graph int not null, Subject int not null, Predicate int not null, Object any not null), с индексами GSPO, PGOS, OGPS, SPGS;
--- вид, связывающий таблицу квадов с таблицей идентификаторов URL и возвращающий квады в читабельном виде.
(а перед тем подумайте, не поменять ли СУБД smile

Если СУБД ещё и тупая, то укажите, какая --- придётся приспосабливаться под данную конкретную тупизну. Или, если проект большой и дорогой --- оставить её в покое и поставить OpenLink Virtuoso рядышком (но это уже пошла реклама wink

3

Re: Вопросы по хранению онтологий в СУБД

Я бы все же посоветовал еще раз подумать над насущной необходимостью хранить онтологию в БД. Это сильно зависит от а) выразительности языка (для краткого введения см. профили OWL), б) сценариев использования онтологии.
В частности, если язык выразительный и планируется использование reasoner'a, то все равно все будет полностью загружаться в память. Множество *реально* использующихся, крупных онтологий прекрасно живут в текстовых файлах.
Мысль насчет (не)удобства работы с OWL/XML тоже не до конца ясна, т.к. это все равно Вы будете делать не непосредственно, а через OWL API (например),
Другое дело, если у Вас будет работа с крупными RDF-графами (или другими крупными наборами данных, представленными на низковыразительном фрагменте OWL), тогда есть смысл использования хранилища.

4

Re: Вопросы по хранению онтологий в СУБД

крупная онтология и текстовый файл это как то странно. я не могу даже такое себе представить как даже маленькую 100мб-онтологию в текстовом файле можно прикрутить к какому то сайту и ее использовать.     тут накануне пытался открыть 54 mb  онтологию сайта Dmoz  в текстовом редакторе и мало не показалось - минут 10 ждал, а про  подсветку вообще не хочу говорить - отрисовка не заставила себя долго ждать - по секунд 10 на каждый экран. как же тогда можно *реально* использовать эти онтологии, если просмотреть их так трудно?

Отредактировано Ganimede (2010-04-19 16:26:23)

5

Re: Вопросы по хранению онтологий в СУБД

А реальное использование отнюдь не заключается в просмотре. Например, приложениям, работающим с SNOMED CT (одна из самых крупных медицинских онтологий), как правило, не требуются *все* классы из онтологии. Поэтому они работают с тем фрагментом (модулем), который им нужен. И хранится все при этом в одном из синтаксисов OWL.
Я не зря упомянул про выразительность и сценарии использования. Даже если вы запихнете OWL DL онтологию в БД в виде RDF-графа, то reasoner'у (или module extractor'у) все равно придется в общем случае вытянуть ее всю, чтобы что-то сделать.
Если выразительный reasoning не нужен (например, там все в RDFS), тогда да - triple store, индексация, SPARQL и вперед.

6

Re: Вопросы по хранению онтологий в СУБД

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

7

Re: Вопросы по хранению онтологий в СУБД

PavelK пишет:

В частности, если язык выразительный и планируется использование reasoner'a, то все равно все будет полностью загружаться в память. Множество *реально* использующихся, крупных онтологий прекрасно живут в текстовых файлах.

Это пока детство технологии. Файлы DNS тоже были текстовыми, благо грузились полностью в память. Когда время непрерывной работы сервиса стало на порядки превышать срок жизни единичной версии данных --- начались заморочки с базами данных о доменах и хостах.

Когда утрясутся стандарты diff+atom и pubsubhubbup, отдельно стоящий ризонер будет однократно грузить себе нужные онтологии при первом обращении к ним, а при редактировании онтологий во внешнем хранилище --- получать короткий diff и "накатывать" его на свою память. А встроенный в хранилище ризонер и того делать не будет smile

8

Re: Вопросы по хранению онтологий в СУБД

А для электронного магазина посмотрите на BSBM, там как раз он и эмулируется. И почти все платформы разработки в отчётах, на выбор.

9

Re: Вопросы по хранению онтологий в СУБД

iv_an_ru пишет:

Это пока детство технологии. Файлы DNS тоже были текстовыми, благо грузились полностью в память. Когда время непрерывной работы сервиса стало на порядки превышать срок жизни единичной версии данных --- начались заморочки с базами данных о доменах и хостах.

Когда утрясутся стандарты diff+atom и pubsubhubbup, отдельно стоящий ризонер будет однократно грузить себе нужные онтологии при первом обращении к ним, а при редактировании онтологий во внешнем хранилище --- получать короткий diff и "накатывать" его на свою память. А встроенный в хранилище ризонер и того делать не будет smile

Не, я о другом. Обновление отредактированных фрагментов онтологии - это не более чем инженерная проблема.
Я имел в виду, что если онтология сложная, то для ответа на логический запрос ризонеру может потребоваться анализ *всей* онтологии целиком. Те модули, которые в оффлайне выделяются из онтологии, чтобы клиенты могли работать с ограниченными фрагментами, не являются минимальными (и в плохом случае можно опять-таки получить всю онтологию целиком). Еще более неприятным является тот факт, что *минимальные* модули (т.е. те, в которых нет *ничего* лишнего для ответа на конкретные запрос(ы)) выделить в общем случае нельзя. Для выразительных языков conservative extensions - это вычислительно неразрешимая задача.
Положительным является тот факт, что аппроксимаций при подсчете модулей в большинстве случаев достаточно. Но анализировать *всю* онтологию при этом все равно надо.
Это, разумеется, нисколько не говорит о том, что ризонер не может анализировать всю онтологию *внутри* БД. Только вот будет ли это сильно быстрее, чем в виртуальной памяти - неизвестно. Особенно, учитывая что в процессе ризонинга размер онтологии - это не главная проблема расхода памяти. Гораздо хуже размер completion graph'ов, которые строят современные таблоризонеры и которые могут быть дважды экспоненциальны от размера самой онтологии.

10

Re: Вопросы по хранению онтологий в СУБД

Хорошо, рассмотрим самый плохой случай: сложный запрос и сложная онтология.

Как-то так получается, что с размером онтологии объём фактов обычно растёт быстрее объёма метаданных. Укладывание онтологии в БД позволяет хотя бы не держать в памяти все факты. Сначала разобрались на уровне классов, потом средствами БД нашли экземпляры нужных классов с нужными свойствами, при необходимости повторили эти два шага нужное число раз.

Метки и комменты, кстати, тоже "факты"; отдельно стоящиему ризонеру приходится выбирать --- то ли иметь возможность использовать их в человекопонятной диагностике, то ли сэкономить память, встраивание в БД снимает проблему.

Таблоризонерам в обозримом будущем станет выгодно и графы складывать во временные таблицы. Это связано с ростом размеров кэшей процессоров. При проектировании быстрых вычислителей память уже сейчас нельзя считать однородно быстрой, и скоро разрыв станет таким, что будет выгодно расходовать CPU на укладку графовых структур в упакованные страницы ради 1) экономии памяти, чтобы максимизировать отношение кэш/озу и 2) улучшения локальности, чтобы минимизировать вредный эффект случайного вытеснения строк обращениями к памяти с совпадающими младшими разрядами адреса.

P.S. У меня есть свой личный субъективный критерий, определяющий, насколько процессор отличается от его упрощённой модели, преподаваемой "в школе". Это размер случайно заполненного целочисленного массива, на котором скорость сортировки пузырьком совпадает со скоростью квиксорта smile

11

Re: Вопросы по хранению онтологий в СУБД

iv_an_ru пишет:

Хорошо, рассмотрим самый плохой случай: сложный запрос и сложная онтология.

Ну давай. Хватит онтологии в, скажем, SHOIN и обыкновенного entailment'a типа A \subclassof B. Пока мы даже не вышли за пределы OWL DL 1.0.

iv_an_ru пишет:

Как-то так получается, что с размером онтологии объём фактов обычно растёт быстрее объёма метаданных.

Часто да. Однако, при наличии номиналов ты не можешь отделять классы от объектов. Т.е. фактически нет границы между TBox и ABox. Более того, на этом уровне выразительности я могу *все* факты выразить только лишь при помощи выражений классов. Грубо говоря ABox не нужен *вообще*. Я понимаю, что это клинический случай, но я же не зря оговорился про "худший случай", не так ли?
Поэтому, кстати, SHER не поддерживает номиналы (он как раз хранит ABox'ы в БД, разбивая ее на локальные фрагмены). А номиналы есть даже в OWL DL 1.0. Так что опять упираемся в выразительность.

iv_an_ru пишет:

Укладывание онтологии в БД позволяет хотя бы не держать в памяти все факты.

Увы, не позволяет, из-за номиналов и QCR.

iv_an_ru пишет:

Сначала разобрались на уровне классов, потом средствами БД нашли экземпляры нужных классов с нужными свойствами, при необходимости повторили эти два шага нужное число раз.

Неа, средств БД для реализации экземпляров не хватит.

iv_an_ru пишет:

Метки и комменты, кстати, тоже "факты"; отдельно стоящиему ризонеру приходится выбирать --- то ли иметь возможность использовать их в человекопонятной диагностике, то ли сэкономить память, встраивание в БД снимает проблему.

Ризонеру метки и комменты глубоко неинтересны. Элементы, не имеющие формальной семантики (например, аннотации), не создают никаких проблем при ризонинге, так что храни их где угодно.

iv_an_ru пишет:

Таблоризонерам в обозримом будущем станет выгодно и графы складывать во временные таблицы. Это связано с ростом размеров кэшей процессоров. При проектировании быстрых вычислителей память уже сейчас нельзя считать однородно быстрой, и скоро разрыв станет таким, что будет выгодно расходовать CPU на укладку графовых структур в упакованные страницы ради 1) экономии памяти, чтобы максимизировать отношение кэш/озу и 2) улучшения локальности, чтобы минимизировать вредный эффект случайного вытеснения строк обращениями к памяти с совпадающими младшими разрядами адреса.

Я не буду спорить. Я не специалист в том, что касается низкоуровневой оптимизации. Я просто представляю себе внутренности ризонеров. Дима может лучше прокомментировать трудоемкость реализации persistent reasoner'a.

12

Re: Вопросы по хранению онтологий в СУБД

iv_an_ru пишет:

Как-то так получается, что с размером онтологии объём фактов обычно растёт быстрее объёма метаданных.

Часто да. Однако, при наличии номиналов ты не можешь отделять классы от объектов. Т.е. фактически нет границы между TBox и ABox. Более того, на этом уровне выразительности я могу *все* факты выразить только лишь при помощи выражений классов.

Ну на то она и оптимизация, чтобы кому-то помогать, а кому-то наоборот настроение портить neutral

13

Re: Вопросы по хранению онтологий в СУБД

Привет,
Я только увидел ответы (думал, что мне на имейл будут приходить сообщения о новых постах).
Уточню по некоторым вопросам. Иметь дело со сложной онтологией (отнологиями) может быть и не придется - вряд ли они будут настролько детальные, как скажем какие-то медицинские онтологии.
Тип БД - тут может быть как MS SQL / MySQL так и key-value store или хранилища документов типа CouchDB или Cassandra (no-SQL).
И да, главный вопрос - скорость выборки, поэтому хранить в текстовых форматах типа XML / JSON неприемлимо.

14

Re: Вопросы по хранению онтологий в СУБД

Думаю, вам не стоит изобретать очередной велосипед. Воспользуйтесь готовым алгоритмом.
Mapping Objects to Relational Databases: O/R Mapping In Detail
Transforming ontology representation from owl to relational database.
Благо за рамки owl-lite вы не вылазите.

Thumbs up +1 Thumbs down