iv_an_ru (iv_an_ru) wrote,
iv_an_ru
iv_an_ru

Category:

Облако и куб: RDF в аналитической базе данных. Часть 2/2

(Это продолжение предыдущей записи, ещё более занудное. В нём даже формулы начинаются, хоть и совсем коротенькие.)

== Старые задачи, новый масштаб ==

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

=== Дедукция в стиле Sherlock by Everett Kaser ===

Онтологии практически бесполезны уже на задаче Эйнштейна для пяти домов. Хочется как-то обрабатывать масштабы на 9--12--15 порядков больше.

=== Очистка данных от ошибок ===

Для этого кажется практичным выполнять цикл из нескольких процедур: поиск противоречий между массивом хранящихся утверждений и предполагаемой семантикой предметной области, некоторая интегральная оценка "плохости" этих противоречий, обнаружение в массиве таких утверждений, что их "исправление" быстрее всего уменьшает "плохость" противоречий. Первым же практическим использованием такого алгоритма станет автоматическая генерация подсказок редакторам Википедии. Сейчас RDF-хранилища проекта DBpedia [ 12 ] непрерывно пополняются формальными данными из Википедии, но "обратная связь" отсутствует --- выделенные данные хранятся "как есть", без попыток их уточнить и импортировать поправки назад в Википедию. Естественно, другие участники Linking Open Data Project тоже могут стать тестовыми пользователями, способствуя превращению базового алгоритма в продукт индустриального качества.

=== Автоматическое распознавание групп "похожих" субъектов ===

Назовём N субъектов "похожими с точностью k", если про них известно M фактов, и есть такие k*M/N пар предикат-значение, что для каждой данной пары k*N субъектов имеют данное значение данного предиката. Человек достаточно хорошо задачи обнаружения таких групп, скажем, он легко обращает внимание на стаю голубей или группу людей в одинаковой униформе. Тренированный человек решает те же задачи с намного большим числом объектов, скажем, сортируя жемчужины для ожерелий. Стало быть, велики шансы сделать хороший решатель и для масштабных баз данных. Такая процедура могла бы использоваться во множестве случаев: для классического кластерного анализа, для обнаружения кандидатов в новые классы, которые могут быть добавлены в онтологию, для поиска и "перепроверки" уников, которые похожи на все экземпляры некоторого класса, но не принадлежат ему, или наоборот. Кроме того, даже необработанный список таких групп был бы ценной подсказкой для алгоритмов визуализации данных.

=== "Смотри также" ===

Это вариант предыдущей задачи. Для данного субъекта найти некоторое заданное число групп объектов, похожих на него с наибольшей точностью.

=== Автоматическое распознавание семантики данных в электронных таблицах ===

Электронные таблицы до сих пор являются самыми многочисленными источниками структурированных данных, даже если их суммарный объём уступает объёмам "настоящих" СУБД. Если бы удалось автоматически определять, субъекты каких классов описываются в документе, то можно было бы пытаться уточнять эти данные по открытым публичным источникам, сверять данные из разных документов одной группы (скажем, одной организации), сравнивать разные версии документа в удобном для человека виде.

=== Автоматическое создание интерфейса ===

Зная историю изменений, которые люди вносили в некоторые данные, попробовать создать пользовательский интерфейс, который облегчил бы эту работу. Например, текстовый редактор или процессор электронной таблицы мог бы предложить скрыть ненужные для текущей работы части документа, показав взамен справочные данные, которые пользователь регулярно "подсматривает" в других местах, и настроив автодополнение при вводе на основании этих данных. Редактор RDF мог бы представить часть данных в виде связанных таблиц.

=== Коллаборативная фильтрация с учётом семантики предметной области ===

Если есть библиотека из Ni книг и сведения о том, какие из Nc читателей прочитали какие из этих книг и какие оценки они им дали, то для каждого читателя можно найти подмножество читателей со схожими вкусами и на основании их оценок построить прогноз, насколько читателю понравится та или иная ещё не прочитанная книга. Этот метод называется коллаборативной фильтрацией, и для достаточно качественных и многочисленных данных результаты его работы выглядят просто чудом. Тем не менее его работу можно попробовать улучшить, построив статистики не только собственно по книгам, но и по авторам, темам, жанрам и.т.п. Я не люблю фильмы по американским комиксам, но люблю читать Брэдбери, понравится ли мне фильм "Семейка Аддамс" по комиксам, с сценаристом которых сотрудничал Брэдбери? Сорт пшеницы X устойчив к характерным для этой области вредителям, но нуждается в лучшем орошении, стоит ли переходить на него? Такие точные, основанные на семантике предметной области формулировки вопросов могут быть использованы для дополнительной коллаборативной фильтрации по субъектам онтологии, либо для привлечения экспертов-людей. Варианты монетизации этой технологии самоочевидны.

=== Задачи Diff, Patch и Merge ===

Представим ресурсы RDF орграфами с частично перенумерованными вершинами и цветными рёбрами (номера вершин берутся из допустимых значений целочисленного типа IRI_ID). Пусть есть два орграфа, один изначально сформирован у контрагента, а другой у нас, и таблица перевода имён, биекция Nsake: IRI_ID "существующий там" -> IRI -> IRI_ID "существующий здесь". Вершины орграфов могут быть bNode-ами, для которых нет понятия IRI и нет хорошо определённой Nsake.

==== Задача вычисления Diff ====

Построить функцию Diff такую, что для двух орграфов Base и Cut вызов Diff (Base, Cut, Nsake) возвращает тройку { Match, Ins, Del }, такую, что

1. Match явялется биекцией и доопределяет Nsake
2. Map (Cut, Match) = { {Sb,P,Ob} | Sb = Match(Sc), Ob = Match(Oc), {Sc,P,Oc} in Cut }
3. Ins = Map (Cut, Match) MINUS Base
4. Del = Base MINUS Map (Cut, Match)

Качество процедуры определяется просто: чем больше область определения Match (и cледовательно, чем меньше мощность Ins и Del), тем лучше.

Часто встречаются три хороших частных случая для Diff:

1. Match = Nsake, потому что bNode отсутствуют и все вершины именованы, либо bNode одинаково нумерованы "тут" и "там"
2. Именованы все те вершины орграфов, в которые входят какие-нибудь дуги: Dom (Nsake) >= Ends (Cut) & Range(Nsake) >= Ends (Base)
3. Именованы все коечные вершины всех путей в орграфах: Dom (Nsake) >= (Ends (Cut) MINUS Begins (Cut)) & Range(Nsake) >= (Ends (Base) MINUS Begins (Base))

==== Задача вычисления Patch ====

В пару к Diff из прошлой задачи построить "обратную" процедуру Patch такую, что Patch (Base, Diff (Base, Cut, Nsake), Nsake) = Cut

==== Задача вычисления Merge ====

Merge (Base, Cut1, Cut2, Nsake) определяется через
Mix1 = Patch (Cut1, Diff (Base, Cut2, Nsake), Nsake) и
Mix2 = Patch (Cut2, Diff (Base, Cut1, Nsake), Nsake) .

Если Mix1 = Mix2 то Merge вернёт Mix1 ("каты успешно смержились"), иначе в качестве диагностики ошибки вернёт Mix1 и значение Diff (Mix1, Mix2, Nsake)

=== Дифференциальная реляционная алгебра ===

Пусть в дополнение к орграфу Base c цветными ребрами и биекции Nsake дана функция T, которая переводит орграф в "трёхколоночную" таблицу его ребер, и порядок строк в этой таблице не важен.
Пусть дана формула реляционной алгебры Qry, с единственным аргументом в виде трехколоночной таблицы.

==== Полная задача ====

Дан кортеж P = Diff (Base, Cut, Nsake), Base и Nsake нам известны, Cut --- нет.
Результат Rset = Qry (T(Base)) вычислен заранее.
Найти Rset1 = Qry (Patch (Base, P, Nsake)) .

==== Задача проверки изменения ====

Дан кортеж P = Diff (Base, Cut, Nsake), Base и Nsake нам известны, Cut --- нет.
Результат Rset = Qry (T(Base)) вычислен заранее.
Проверить равенство Qry (T(Base)) = Qry (Patch (Base, P, Nsake)) .

===== Задача проверки возможного изменения ====

Дан кортеж P = Diff (Base, Cut, Nsake), Base и Nsake нам известны, Cut --- нет.
Результат Rset = Qry (T(Base)) вычислен заранее.
Пообещать, что Qry (T(Base)) = Qry (Patch (Base, P, Nsake)) либо сказать "я не знаю".

=== Задача разбиения diff-а на хорошую и плохую части ===

Даны кортеж P вида { Match, Del, Ins } и орграф Base.
Дана формула реляционной алгебры Inconsistencies.
Известно так же, что Inconsistencies (T (Base)) = {}.
Представить P в виде { Match, DelOK UNION DelF, InsOK UNION InsF } таком, что
Inconsistencies (T (Patch (Base, { Match, DelOK, InsOK }))) = {} и
сумма |DelF| + |InsF| минимальна.


== Заключение ==

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

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

Чтобы обосновать важность объединения усилий специалистов по СУБД и семантическим методам, двух этих "меркантильных" доводов вполне достаточно. Но есть и третий довод --- это же интересно! Очень!

== Литература ==

1 Hellerstein, Joseph M. The Declarative Imperative: Experiences and Conjectures in Distributed Logic. PODS-2010, keynote. UCB/EECS-2010-90. http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-90.html
2 Abadi, Daniel J. Query Execution in Column-Oriented Database Systems. MIT PhD Dissertation, February, 2008. http://cs-www.cs.yale.edu/homes/dna/papers/abadiphd.pdf
3 Erling, O., Mikhailov, I. Faceted Views over Large-Scale Linked Data. Linked Data on the Web (LDOW2009). http://events.linkeddata.org/ldow2009/papers/ldow2009_paper3.pdf
4 Ontotext AD. OWLIM --- OWL Semantic Repository. http://www.ontotext.com/owlim/index.html
5 SYSTAP, LLC. Bigdata. http://www.systap.com/bigdata.htm
6 Harris, S., Lamb, N., Shadbolt, N. 4store: The Design and Implementation of a Clustered RDF Store. SSWS2009. http://4store.org/publications/harris-ssws09.pdf
7 Transaction Processing Performance Council. TPC Benchmark(TM) H (Decision Support) Standard Specification Revision 2.11.0. http://www.tpc.org/tpch/spec/tpch2.11.0.pdf
8 Hellerstein J. M., Stonebraker M. (eds). Readings in Database Systems, Third Edition. Morgan Kaufmann, Mar. 1998.
9 BOOM --- Berkeley Orders of Magnitude - Declarative Languages And Systems. http://boom.cs.berkeley.edu/
10 Sidirourgos, L., Goncalves, R., Kersten, M., Nes, N., Manegold, S. Column-Store Support for RDF Data Management: not all swans are white. VLDB 2008. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.6138&rep=rep1&type=pdf
11 Tummarello, G., Morbidoni, C., Bachmann-Gmur, R., Erling, O. RDFSync: Efficient Remote Synchronization of RDF Models. ISWC / ASWC 2007. pp. 537-551.
12 Auer, S., Lehmann, J. What have Innsbruck and Leipzig in common? Extracting Semantics from Wiki Content. In Franconi et al. (eds), Proceedings of European Semantic Web Conference (ESWC 2007), LNCS 4519, pp. 503–517, Springer, 2007.
13 Bizer, C., Schultz, A. Berlin SPARQL Benchmark (BSBM). http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/
14 Guo, Y., Pan, Z., Heflin, J. LUBM: A Benchmark for OWL Knowledge Base Systems. Journal of Web Semantics 3(2), 2005, pp. 158-182.
Tags: rdbms, конспекты
Subscribe

  • Небольшая перестраховка.

    (Забавна причина ремонта газонокосилки: у неё отвинтился двигатель. Кчер-тям. Неведомый гений прикрутил его на гайки с полиэтиленовыми…

  • Стакан с ежом

    Вы никогда про это не задумывались. Вам никогда это не требовалось. Вы никогда про это не спрашивали. Но теперь вы все равно знаете, как правильно…

  • Полундра!

    Снимал с верхотуры один старинный электронный гробик, и получил по башке лежавшей на нём коробкой. А в ней... Кликабельно. Это был первый раз в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 3 comments