Декларативные способы преобразования исходных данных в онтологии Воробьев Владимир Иванович Перминов Сергей Владимирович Санкт-Петербургский институт Информатики и Автоматизации РАН [ СПб, 14-я линия ВО, т Симпозиум «Онтологическое моделирование: состояние и направления исследований и применения» Звенигород, 20 – 21 мая 2008 года
Содержание Введение Постановка задачи преобразования Декларативный подход к преобразованию, построение конвейера Пример функционального преобразования Преобразования из различных форматов данных Web как источник данных Примеры программных систем
Актуальность петабайтные наборы данных требуют новый стиль работы. данные должны быть самоописываемыми (метаданные) непроцедурные языки манипулирования данными играют основную роль в обеспечении поиска и анализа данных. данные эволюционизируют. эволюцию данных без затрагивания программ высокопроизводительные процессоры онтологий общего назначения. метрики
Метрики независимые от данных Необходимы инварианты для контроля трансформации данных: Симметрия (контроль невозможности некоторых преобразований) Простота Порядок Энтропия Сохранение Информация Неоднозначность
Контексты д анны х, подлежащие преобразованию Любые, зависят от постановки задачи – Базы данных (реляционные, объектные…) – Форматы данных (текстовые, бинарные…) – XML-данные – Программы на различных языках… Размещение данных – Локально (обращение к файловой системе) – В локальной сети (сетевая ФС, SQL) – В Интернет (многообразие сервисов доступа) Web (HTTP/HTML)
Императивный подход Постоянная смена «состояния» программы Строки – команды ОС и процессору int i = 0; Int k = 5; Int j = k - i; k = 4; i = j – k; регистры
Задача преобразования Исходные контексты данных Таблица Excel XML-файл Др. язык описания Онтология на CycL или KIF… Выходные контексты данных RDF/OWL KIF CycL… Возможные сложности: негибкость, сложность автоматизации оценка (качества) преобразования два программиста решат по-разному (высокая степень свободы) зависят от программиста ?
Постановка задачи преобразования Необходимо снизить степень свободы в реализации преобразования Автоматизация построения преобразования (повторное использование компонентов) Компоненты = функции преобразования Упрощение (возможное построение интерфейса) Выполнение в параллельных процессах
Компоненты преобразования Преобразование = функция λ-выражения как способ представления функций (λ 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)
Преобразования без промежуточных состояний Композиция функций : Каналы в командной оболочке 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)
Конвейер Выходные данные Входные данные F2F1 F3F3 G H in out
Пример преобразования IDEF0 UML (диаграмма классов)
Пример преобразования: описание диаграммы IDEF0 ArrowEnd Arrow_ID Block_ID Mechanism_ID Input_ID Control_ID Output_ID hasArrowEnd atBlock rdfs:subClass
Пример преобразования: описание диаграммы классов UML Type Attribute_ID Method_ID Parameter_ID Class_ID PrimitiveType_ID rdfs:subPropertyOf composesinherits method parameter type attribute
Пример преобразования: Фрагмент RDF- описания диаграммы IDEF0 Together
Пример преобразования: правило 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
Примеры запросов на языке 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. } только для чтения
Альтернатива представлению RDF: N-Triples "Dave Beckett". "Art Barstow".. RDF-эквивалент: Art Barstow Dave Beckett
Пример преобразования: правило 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
Формализация преобразования (1) RDF/OWL N-Triple RDF/OWL шаблон SPARQL N-Triples
Формализация преобразования (2) Haskell: f = makeRDF. delDuplicates. concat. map templates templates = map (uncurry makeTemplate) zip (sparqls,tripless) makeTemplate sparql triples = = \rdf -> makeTriples (request sparql rdf) triples
Функциональный подход 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]
Haskell – чисто функциональный подход нет императивных конструкций интерференция типов (type classes) «ленивые» вычисления main = print. sum. take 100 $ [1..] полигон для разработки чисто функциональных (являющихся декларативными) программ Уникальное свойство: декларативная реализация ввода-вывода main = writeFile output. process =
Формализация преобразования (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)))
RDF/OWL N-Triple Формализация преобразования (4) ? шаблон запрос? N-Triples
Форматы данных: данные + метаданные Таблица, RDB ИмяОтч.Фам. Иван ПетрПетровичПетров ИвановИванович XML Кленовые Кленовые Семейство растений CSV Иван,Иванович,Иванов¶ Петр,Петрович,Петров¶
Исходные данные: CSV parse = split,. lines Регулярные выражения (regex) Утилиты UNIX (awk, sed) Библиотеки (API) языков программирования Иван,Иванович,Иванов¶ Петр,Петрович,Петров¶
Исходные данные: RDB, ODB SQL SELECT * FROM books WHERE price > ORDER BY title; OQL SELECT pc.cpuspeed FROM PCs pc WHERE pc.ram > 64 ИмяОтч.Фам. Иван ПетрПетровичПетров ИвановИванович
Исходные данные: 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 Кленовые Кленовые Семейство растений
Язык трансформаций XSLT язык запросов язык шаблонов функциональный язык
Web как источник данных Web уже сейчас – большая (слабоструктурированная) БД – Интерфейсы к БД – Тексты – Словари – Каталоги… HTTP/HTML Потенциал Web в плане интеграции ресурсов
Преобразование контекста данных в Web (1) XPath: //td class=first]/a article]/b article]
Преобразование контекста данных в Web (2) Страница Малый энциклопедический… словарь статья Кленовые название Кленовые, (Aceraceae), сем. растений из класса… текст меню Везде Новости 1 2 …
Исходные данные: разные форматы Собственные языки запросов, программные интерфейсы языков программирования Синтаксические анализаторы (парсеры) – 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;} ;
Особый вид парсера: 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
Исходные данные: текстовые (1)
Исходные данные: текстовые (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% вес
Исходные данные: текстовые (3) 0.6% % % 2 0.6% % % 5 0.6% 8 0.6% % A 0.6% Acer % цветами 0.6% чашелистиков 0.6% экипажном 0.6% энциклопедический 0.6% явор семантические классы знания литература книга трактат повесть корресп. Тузов В.А. ФО неодуш. вещь техника транспорт сухопутный без двигателя природа растения деревья травы Обозначение: - подкласс
Исходные данные: текстовые (4) Страница Яндекс.Словари… Малый энциклопедический… словарь статья Кленовые название Кленовые, (Aceraceae),... текст заголовок меню Везде Новости 1 2 … трактат знания книга ФО природа растения деревья … сем. классы Обозначение: - подкласс 0.2% вес 1.4% вес Возможности для семантического поиска
Примеры: Поиск на основе семантических классов (1)
Традиционный поиск: (эффективный) поисковый запрос ограничен 3-10 ключевыми словами Поиск на основе семантических классов: эффективный поисковый запрос неограничен Примеры: Поиск на основе семантических классов (2)
Примеры: ЕНИП СПбНЦ РАН [spbrc.nw.ru] Cовместный проект с ВЦ РАН им. А.А.Дородницына
Примеры: ЕНИП предоставление данных /ras/view/person/general. html ?id=14287/ras/view/person/general. rdf ?id=
Примеры: ЕНИП преобразование данных
Примеры: ЕНИП интеграция [enip.ras.ru]
Выводы Со смещением центра внимания при создании ПО с проектирования алгоритмов на проектирование структур данных требуются новые, декларативные подходы к преобразованию данных Необходимо снижение степени свободы при разработке преобразователей данных Рассмотрено использование функционального подхода без внутренних состояний, с шаблон ами и декларативных язык ами запросов
Список литературы: [dcmi] DCMI [enip] ENIP [esa] ResearchChannel - Enhancing Text Representation Through Knowledge-Based Feature Generation [foaf] FOAF [rss] RDF RSS [protege] Protégé Ontology Editor
[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.
[vcard] RDF vCard [w3c] World Wide Web Consortium (W3C)