Декларативные способы преобразования исходных данных в онтологии Воробьев Владимир Иванович Перминов Сергей Владимирович Санкт-Петербургский институт Информатики. - презентация

1 Декларативные способы преобразования исходных данных в онтологии Воробьев Владимир Иванович Перминов Сергей Владимирович Санкт-Петербургский институт Информатики и Автоматизации РАН [ СПб, 14-я линия ВО, т Симпозиум «Онтологическое моделирование: состояние и направления исследований и применения» Звенигород, 20 – 21 мая 2008 года

2 Содержание Введение Постановка задачи преобразования Декларативный подход к преобразованию, построение конвейера Пример функционального преобразования Преобразования из различных форматов данных Web как источник данных Примеры программных систем

3 Актуальность петабайтные наборы данных требуют новый стиль работы. данные должны быть самоописываемыми (метаданные) непроцедурные языки манипулирования данными играют основную роль в обеспечении поиска и анализа данных. данные эволюционизируют. эволюцию данных без затрагивания программ высокопроизводительные процессоры онтологий общего назначения. метрики

4 Метрики независимые от данных Необходимы инварианты для контроля трансформации данных: Симметрия (контроль невозможности некоторых преобразований) Простота Порядок Энтропия Сохранение Информация Неоднозначность

5 Контексты д анны х, подлежащие преобразованию Любые, зависят от постановки задачи – Базы данных (реляционные, объектные…) – Форматы данных (текстовые, бинарные…) – XML-данные – Программы на различных языках… Размещение данных – Локально (обращение к файловой системе) – В локальной сети (сетевая ФС, SQL) – В Интернет (многообразие сервисов доступа) Web (HTTP/HTML)

6 Императивный подход Постоянная смена «состояния» программы Строки – команды ОС и процессору int i = 0; Int k = 5; Int j = k - i; k = 4; i = j – k; регистры

7 Задача преобразования Исходные контексты данных Таблица Excel XML-файл Др. язык описания Онтология на CycL или KIF… Выходные контексты данных RDF/OWL KIF CycL… Возможные сложности: негибкость, сложность автоматизации оценка (качества) преобразования два программиста решат по-разному (высокая степень свободы) зависят от программиста ?

8 Постановка задачи преобразования Необходимо снизить степень свободы в реализации преобразования Автоматизация построения преобразования (повторное использование компонентов) Компоненты = функции преобразования Упрощение (возможное построение интерфейса) Выполнение в параллельных процессах

9 Компоненты преобразования Преобразование = функция λ-выражения как способ представления функций (λ x. x + 2) 3 (λ f. f 3) (λ x. x + 2) 0 := λ f x. x 1 := λ f x. f x 2 := λ f x. f (f x) 3 := λ f x. f (f (f x)) SUCC := λ n f x. f (n f x) PLUS := λ m n f x. n f (m f x) MULT := λ m n f. m (n f)

10 Преобразования без промежуточных состояний Композиция функций : Каналы в командной оболочке UNIX: ls | grep test | cat > out.txt Преобразования строк в языке Java: string.trim().replace(:,;).toLowerCase().substring(2) Программа на языке Haskell: main = interact $ show. apply length id. map toLower where apply fnA fnB x = (fnA x, fnB x)

11 Конвейер Выходные данные Входные данные F2F1 F3F3 G H in out

12 Пример преобразования IDEF0 UML (диаграмма классов)

13 Пример преобразования: описание диаграммы IDEF0 ArrowEnd Arrow_ID Block_ID Mechanism_ID Input_ID Control_ID Output_ID hasArrowEnd atBlock rdfs:subClass

14 Пример преобразования: описание диаграммы классов UML Type Attribute_ID Method_ID Parameter_ID Class_ID PrimitiveType_ID rdfs:subPropertyOf composesinherits method parameter type attribute

15 Пример преобразования: Фрагмент RDF- описания диаграммы IDEF0 Together

16 Пример преобразования: правило 1 дуги механизмов являются объектами класса, для которых блок это их метод. Запрос: SELECT ?class ?name WHERE { %class. _:class tf:name ?name } Выходные логические тройки: ?class a tf:Class. ?class tf:name ?name где: %class = ?class a tf:Mechanism. _:class a tf:Arrow. _:class tf:hasArrowEnd ?class

17 Примеры запросов на языке SPARQL SELECT ?obj WHERE { ?subj rdf:type tf:Arrow. ?subj tf:name ?obj. } SELECT ?obj WHERE { ?subj a tf:Arrow. ?subj tf:name ?obj. } SELECT DISTINCT ?arrow ?s WHERE { ?arrow a tf:Arrow. ?mechanism a tf:Mechanism. ?arrow tf:hasArrowEnd ?mechanism. ?arrow tf:name ?name. } только для чтения

18 Альтернатива представлению RDF: N-Triples "Dave Beckett". "Art Barstow".. RDF-эквивалент: Art Barstow Dave Beckett

19 Пример преобразования: правило 2 дуги механизмов являются объектами класса, для которых блок это их метод. Запрос: SELECT ?class ?method ?name WHERE { %method. ?method tf:name ?name } Выходные логические тройки: ?class a tf:Class. ?method a tf:Method. ?class tf:method ?method. ?method tf:name ?name где: %method = %class. ?method a tf:Block. ?class tf:atBlock ?method

20 Формализация преобразования (1) RDF/OWL N-Triple RDF/OWL шаблон SPARQL N-Triples

21 Формализация преобразования (2) Haskell: f = makeRDF. delDuplicates. concat. map templates templates = map (uncurry makeTemplate) zip (sparqls,tripless) makeTemplate sparql triples = = \rdf -> makeTriples (request sparql rdf) triples

22 Функциональный подход map (*2) [1,2..100] = [2,4..200] int[] is = new int[1000] for (int i = 0; i < is.length; i++) { is[i] = i*2; } return is; reduce (+) [1..100] = 5050 int[] is = new int[100] int sum = 0; for (int i = 0; i < is.length; i++) { sum += is[i]; } return sum; [Google MapReduce]

23 Haskell – чисто функциональный подход нет императивных конструкций интерференция типов (type classes) «ленивые» вычисления main = print. sum. take 100 $ [1..] полигон для разработки чисто функциональных (являющихся декларативными) программ Уникальное свойство: декларативная реализация ввода-вывода main = writeFile output. process =

24 Формализация преобразования (3) Schema/Lisp: (define (f rdf) (make-rdf (del-duplicates (concat (map templates rdf))))) (define templates (user-map (make-template sparqls tripless))) (define (make-template sparql triples) (lambda rdf (make-triples (request sparql rdf) triples)))

25 RDF/OWL N-Triple Формализация преобразования (4) ? шаблон запрос? N-Triples

26 Форматы данных: данные + метаданные Таблица, RDB ИмяОтч.Фам. Иван ПетрПетровичПетров ИвановИванович XML Кленовые Кленовые Семейство растений CSV Иван,Иванович,Иванов¶ Петр,Петрович,Петров¶

27 Исходные данные: CSV parse = split,. lines Регулярные выражения (regex) Утилиты UNIX (awk, sed) Библиотеки (API) языков программирования Иван,Иванович,Иванов¶ Петр,Петрович,Петров¶

28 Исходные данные: RDB, ODB SQL SELECT * FROM books WHERE price > ORDER BY title; OQL SELECT pc.cpuspeed FROM PCs pc WHERE pc.ram > 64 ИмяОтч.Фам. Иван ПетрПетровичПетров ИвановИванович

29 Исходные данные: XML xPath 1.//head/title/string(.) 2.//dict/key[string(.)='Comments']/.[following-sibling::string[1]/ contains(string(.),'>')]/ following-sibling:: key[string(.)='Location']/ following-sibling::string[1]/string(.) xQuery XSLT XML Кленовые Кленовые Семейство растений

30 Язык трансформаций XSLT язык запросов язык шаблонов функциональный язык

31 Web как источник данных Web уже сейчас – большая (слабоструктурированная) БД – Интерфейсы к БД – Тексты – Словари – Каталоги… HTTP/HTML Потенциал Web в плане интеграции ресурсов

32 Преобразование контекста данных в Web (1) XPath: //td class=first]/a article]/b article]

33 Преобразование контекста данных в Web (2) Страница Малый энциклопедический… словарь статья Кленовые название Кленовые, (Aceraceae), сем. растений из класса… текст меню Везде Новости 1 2 …

34 Исходные данные: разные форматы Собственные языки запросов, программные интерфейсы языков программирования Синтаксические анализаторы (парсеры) – ANTLR – JavaCC – … grammar T; def : modifier+ 'int' ID '=' INT '; | modifier+ 'int' ID '; ; modifier : 'public' | 'static' ; INT : '0'..'9'+ ; ID : 'a'..'z'+ ; WS : (' '|'\r'|'\n')+ {$channel = HIDDEN;} ;

35 Особый вид парсера: Parsec expr = buildExpressionParser table factor "expression table = [[op "*" (*) AsscocLeft, op "/" div AssocLeft], [op "+" (+) AssocLeft, op "-" (-) AssocLeft]] where op s f assoc = Infix (do{ string s; return f}) assoc factor = do char '( x 36 Исходные данные: текстовые (1)

37 Исходные данные: текстовые (2) 0.6% % % 2 0.6% % % 5 0.6% 8 0.6% % A 0.6% Acer % цветами 0.6% чашелистиков 0.6% экипажном 0.6% энциклопедический 0.6% явор Страница явор слово … 0.6% вес

38 Исходные данные: текстовые (3) 0.6% % % 2 0.6% % % 5 0.6% 8 0.6% % A 0.6% Acer % цветами 0.6% чашелистиков 0.6% экипажном 0.6% энциклопедический 0.6% явор семантические классы знания литература книга трактат повесть корресп. Тузов В.А. ФО неодуш. вещь техника транспорт сухопутный без двигателя природа растения деревья травы Обозначение: - подкласс

39 Исходные данные: текстовые (4) Страница Яндекс.Словари… Малый энциклопедический… словарь статья Кленовые название Кленовые, (Aceraceae),... текст заголовок меню Везде Новости 1 2 … трактат знания книга ФО природа растения деревья … сем. классы Обозначение: - подкласс 0.2% вес 1.4% вес Возможности для семантического поиска

40 Примеры: Поиск на основе семантических классов (1)

41 Традиционный поиск: (эффективный) поисковый запрос ограничен 3-10 ключевыми словами Поиск на основе семантических классов: эффективный поисковый запрос неограничен Примеры: Поиск на основе семантических классов (2)

42 Примеры: ЕНИП СПбНЦ РАН [spbrc.nw.ru] Cовместный проект с ВЦ РАН им. А.А.Дородницына

43 Примеры: ЕНИП предоставление данных /ras/view/person/general. html ?id=14287/ras/view/person/general. rdf ?id=

44 Примеры: ЕНИП преобразование данных

45 Примеры: ЕНИП интеграция [enip.ras.ru]

46 Выводы Со смещением центра внимания при создании ПО с проектирования алгоритмов на проектирование структур данных требуются новые, декларативные подходы к преобразованию данных Необходимо снижение степени свободы при разработке преобразователей данных Рассмотрено использование функционального подхода без внутренних состояний, с шаблон ами и декларативных язык ами запросов

47 Список литературы: [dcmi] DCMI [enip] ENIP [esa] ResearchChannel - Enhancing Text Representation Through Knowledge-Based Feature Generation [foaf] FOAF [rss] RDF RSS [protege] Protégé Ontology Editor

48 [sparql] SPARQL [sw] Berners-Lee T., Hendler J., Lassila O. The Semantic Web Scientific American No. 5. P [sw-intro] Henry Story RDF - Connecting Software and People [sw-primer] Grigoris Antoniou, Frank van Harmelen. A Semantic Web Primer - MIT Press: 2004 [swoogle] Swoogle [tuzov] Tuzov V. A. Computer Semantics of Russian Language SPb.: SPbSU, 2003.

49 [vcard] RDF vCard [w3c] World Wide Web Consortium (W3C)