Направления исследований в области принципов управления данными (Дагштульский отчет)

Серж Абитебул, Марсело Аренас, Пабло Барсело, Мегын Бьенвеню, Диего Кальванезе, Клэр Дэвид, Ричард Халл, Эйке Хюллермайер, Бенни Кимельфельд, Леонил Либкин, Вим Мартенс, Това Мило, Филип Мурлак, Фрэнк Невен, Магдалена Ортис, Томас Швентик, Юлия Стоянович, Цзянвэнь Су, Дэн Сучиу, Виктор Виану, Кэ Йи

Research Directions for Principles of Data Management

Serge Abiteboul (ENS – Cachan, FR), Marcelo Arenas (Pontificia Universidad Catolica de Chile, CL, marenas@ing.puc.cl), Pablo Barceló (DCC, University of Chile – Santiago de Chile, CL), Meghyn Bienvenu (University of Montpellier, FR), Diego Calvanese (Free Univ. of Bozen-Bolzano, IT), Claire David (University Paris-Est – Marne-la-Vallée, FR), Richard Hull (IBM TJ Watson Research Center – Yorktown Heights, US, hull@us.ibm.com), Eyke Hüllermeier (Universität Paderborn, DE), Benny Kimelfeld (Technion – Haifa, IL), Leonid Libkin (University of Edinburgh, GB), Wim Martens (Universität Bayreuth, DE, wim.martens@uni-bayreuth.de), Tova Milo (Tel Aviv University, IL, milo@cs.tau.ac.il), Filip Murlak (University of Warsaw, PL), Frank Neven (Hasselt Univ. – Diepenbeek, BE), Magdalena Ortiz (TU Wien, AT), Thomas Schwentick (TU Dortmund, DE, thomas.schwentick@udo.edu), Julia Stoyanovich (Drexel University — Philadelphia, US), Jianwen Su (University of California – Santa Barbara, US), Dan Suciu (University of Washington – Seattle, US), Victor Vianu (University of California – San Diego, US), and Ke Yi (HKUST – Kowloon, HK)

Dagstuhl Manifestos, vol. 7, issue 1, 2018, pp. 1–29

Вступление от переводчика

В замке Дагштуль (Schloss Dagstuhl), который находится в деревне Керпен Иллинген немецкой земли Саар, располагается германский исследовательский центр компьютерной науки (немцы, как иногда и русские, называют эту науку информатикой), называемый с 2008 г. Лейбниц-центром (Leibniz-Zentrum für Informatik). Основным родом деятельности Лейбниц-центра является проведение национальных и международных семинаров и симпозиумов. На основе проводимых мероприятий в замке Дагштуль подготавливаются и публикуются несколько периодических изданий, в число которых входит издание Dagstuhl Manifestos, содержащие материалы симпозиумов.

Материал, перевод которого предлагается вашему вниманию, был опубликован в Дагшульских манифестах в 2018 г. и представляет собой отчет о симпозиуме, посвященном актуальной и перспективной тематике исследований в области принципов управления данными. В симпозиуме принял участие 21 исследователь из Германии, Франции, Великобритании, Италии, Австрии, Польши, Израиля, Китая (Гонконг), Чили и США. Симпозиум был организован исполнительными комитетами двух основных международных конференций, посвященных теоретическим вопросам баз данных и управления данными. Насколько мне известно, подобных симпозиумов еще не было в истории управления данными, и отчет, по моему мнению, представляет несомненный интерес для всех людей, интересующихся актуальными проблемами и решениями в области управления данными.

Вместе с тем, в сообществе систем управления данными подобные встречи проводятся уже больше 30 лет (первая встреча состоялась в 1988 г.) По мотивам каждой встречи издавался отчет, и отчеты сообщества систем управления данными принесли большую пользу как исследовательскому сообществу, так и практике баз данных. О первых восьми встречах можно прочитать в моей статье «Управление данными: 25 лет прогнозов». Перевод отчета о девятой, Сиэтлской встрече, состоявшейся в 2018 г., опубликован в 2020 г. («Сиэтлский отчет об исследованиях в области баз данных»).

Мне кажется, что Дагшульский отчет прекрасно дополняет последние отчеты сообщества систем баз данных. Он позволяет лучше понять, чем занимаются теоретики управления данными, какие практические проблемы мотивируют их теоретические исследования, как теоретические исследования связаны с исследованиями сообщества систем управления данными. Кстати, двое участников встречи в замке Дагшуль участвовали и двух последних встречах сообщества систем управления данными (Тито Мило и Дэн Сучиу). Так что деление общего сообщества баз данных на теоретиков и «системщиков» является достаточно условным.

Как и в своем переводе Сиэтлского отчета, я не вставлял в перевод Дагшульского отчета какие-либо свои комментарии (хотя временами очень хотелось) и ограничился лишь ссылками на доступные в Internet материалы, поясняющие некоторые понятия и термины. В моих планах числится написание отдельной статьи, содержащей сопоставление и критический анализ Бекманского (2013 г.), Дагшульского (2016 г.) и Сиэтлского отчетов

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

Сергей Кузнецов

Аннотация.

Область принципов управления данными (Principles of Data Management, PDM) внесла решающий вклад в разработку формальных основ для понимания данных и знаний, а также управления ими. Эта работа включала обильное взаимообогащение между PDM и другими дисциплинами математики и компьютерной науки, включая логику, теорию сложности и представление знаний. Мы ожидаем постоянного расширения направлений исследований PDM, поскольку технологии и приложения, связанные с управлением данными, продолжают расти и развиваться. В частности, жизненный цикл аналитики больших данных (Big Data Analytics) затрагивает большое количество проблемных областей, в которых может помочь PDM.

В этом отчете мы выявляем некоторые из наиболее важных направлений исследований, в которых сообщество PDM может внести существенный вклад. Это делается с трех точек зрения: потенциальная практическая значимость, уже полученные результаты и исследовательские проблемы, которые кажутся преодолимыми в краткосрочной и среднесрочной перспективе.

Ключевые слова и фразы: теория баз данных; принципы управления данными; языки запросов; эффективная обработка запросов; оптимизация запросов; неоднородные данные; неточность; управление данными, обогащенными знаниями; машинное обучение; потоки работ; данные, связанные с человеком; этика.

Основные положения

В апреле 2016 года сообщество исследователей, работающих в области «Принципов управления данными» (Principles of Data Management, PDM), собралось в замке Дагштуль (Dagstuhl) в Германии для проведения симпозиума, организованного совместно Исполнительным комитетом Симпозиума ACM по принципам систем баз данных (ACM Symposium on Principles of Database Systems, PODS) и Советом Международной конференции по теории баз данных (International Conference on Database Theory, ICDT). Задача этого симпозиума состояла в том, чтобы определить и изучить некоторые из наиболее важных направлений исследований, которые имеют большое значение для общества и компьютерных наук сегодня, и в которых сообщество PDM может внести существенный вклад. В этом отчете описывается набор направлений исследований, на которых участники симпозиума фокусировались с трех точек зрения: потенциальная практическая значимость, уже полученные результаты и исследовательские проблемы, которые кажутся преодолимыми в краткосрочной и среднесрочной перспективе. В этом отчете выявленные проблемы исследований для PDM относятся к семи основным темам: масштабируемая обработка; мультимодельные данные; неточная информация; данные, обогащенные знаниями; управление данными и машинное обучение; процессы и данные; а также этика и управление данными. Поскольку новые проблемы в PDM возникают постоянно, мы отмечаем, что этот список тем не является исчерпывающим.

Этот отчет предназначен для разнотипных читателей. Он предназначен для правительственных и отраслевых финансирующих организаций, поскольку включает в себя определение важных областей, в которых сообщество PDM уже вносит свой вклад в решение ключевых проблем управления данными нашего времени и может сделать гораздо больше. Он предназначен для университетов и колледжей по всему миру, поскольку в нем подчеркивается важность продолжения исследований и образования в области фундаментальных элементов управления данными, а также выделяются направления развития исследований в области компьютерных наук и науки об управлении информацией (Management of Information Science). Он предназначен для исследователей и студентов, потому что он определяет перспективные, интересные исследовательские задачи в области PDM, которые имеют очень актуальное практическое значение. Он также предназначен для политиков, социологов и философов, потому что в нем еще раз подчеркивается важность учета этики во многих аспектах создания данных, доступа к ним и их использования данных, а также говорится о том, как исследования могут помочь найти новые способы получения максимальных преимуществ от использования массивных данных, сохраняя при этом конфиденциальность и неприкосновенность граждан и общества.

1. Введение

В апреле 2016 года сообщество исследователей, работающих в области «Принципов управления данными» (Principles of Data Management, PDM), собралось в замке Дагштуль в Германии для проведения симпозиума, организованного совместно Исполнительным комитетом Симпозиума ACM по принципам систем баз данных (ACM Symposium on Principles of Database Systems, PODS) и Советом Международной конференции по теории баз данных (International Conference on Database Theory, ICDT). Задача этого симпозиума состояла в том, чтобы определить и изучить некоторые из наиболее важных направлений исследований, которые имеют большое значение для общества и компьютерных наук сегодня, и где сообщество PDM может внести существенный вклад. В этом отчете описывается набор направлений исследований, на которых участники симпозиума фокусировались с трех точек зрения: потенциальная практическая значимость, уже полученные результаты и исследовательские проблемы, которые кажутся преодолимыми в краткосрочной и среднесрочной перспективе. В этом отчете выявленные проблемы исследований для PDM относятся к семи основным темам: масштабируемая обработка; мультимодельные данные; неточная информация; данные, обогащенные знаниями; управление данными и машинное обучение; процессы и данные; а также этика и управление данными. Поскольку новые проблемы в PDM возникают постоянно, мы отмечаем, что этот список тем не является исчерпывающим.

Этот отчет предназначен для разнотипных читателей. Он предназначен для правительственных и отраслевых финансирующих организаций, поскольку включает в себя определение важных областей, в которых сообщество PDM уже вносит свой вклад в решение ключевых проблем управления данными нашего времени и может сделать гораздо больше. Он предназначен для университетов и колледжей по всему миру, поскольку в нем подчеркивается важность продолжения исследований и образования в области фундаментальных элементов управления данными, а также выделяются направления развития исследований в области компьютерных наук и науки об управлении информацией (Management of Information Science). Он предназначен для исследователей и студентов, потому что он определяет перспективные, интересные исследовательские задачи в области PDM, которые имеют очень актуальное практическое значение. Он также предназначен для политиков, социологов и философов, потому что в нем еще раз подчеркивается важность учета этики во многих аспектах создания данных, доступа к ним и их использования, а также говорится о том, как исследования могут помочь найти новые способы получения максимальных преимуществ от использования массивных данных, сохраняя при этом конфиденциальность и неприкосновенность граждан и общества.

Область PDM обширна. Она включает направления от разработки формальных инфраструктур для понимания данных и знаний, а также управления ими (включая модели данных, языки запросов, онтологии и модели транзакций) до структур данных и алгоритмов (включая оптимизацию запросов, механизмы обмена данными и манипуляции данными с сохранением конфиденциальности). Управление данными в настоящее время лежит в основе большинства IT-приложений и в обозримом будущем станет движущей силой в частной жизни людей, общественной жизни, промышленности и исследованиях. Мы ожидаем постоянного расширения исследований PDM, поскольку технологии и приложения, связанные с управлением данными, продолжают расти и развиваться.

Область PDM играла основную роль в становлении реляционной модели база данных, обосновав связь между алгебраическими и основанными на исчислении языками запросов, связав ограничения целостности с проектированием баз данных, выявив ключевые идеи оптимизации запросов и обеспечив теоретические основы согласованных параллельных транзакций. При выполнении этой начальной работы происходил плодотворный обмен идеями между PDM и другими дисциплинами математики и компьютерных наук, включая логику, теорию сложности и представление знаний. С 1990-х годов мы наблюдаем огромный рост как производства данных, так и возможности хранить эти данные и получать к ним доступ. Это привело к впечатляющему изменению способов управления данными и их использования. За это время мы перешли (1) от автономных дисковых баз данных к данным, которые распространяются через Web и связываются через Сеть, (2) от жестко структурированных к слабо структурированным данным и (3) от реляционных данных ко многим различным моделям данных (иерархические и графовые данные, точки данных (data point), NoSQL, текстовые данные, данные изображений и т.д.). В это же время развивались исследования в области PDM, которые сопровождали этот процесс и влияли на него. Были активизированы исследования, направленные на расширение реляционной модели (обмен данными, неполные данные, вероятностные данные, ...), ориентированные на другие модели данных (иерархические, полуструктурированные, графовые, текстовые данные, ...) и относящиеся к другим областям управления данными, включая представление знаний и Semantic Web, конфиденциальность и безопасность данных, а также (бизнес-)процессы, работающие с данными (data-aware (business) processes). Попутно сообщество PDM расширило взаимодействие со смежными областями, включая теорию автоматов, Web-сервисы, параллельные вычисления, обработку документов, структуры данных, научные потоки работ, управление бизнес-процессами, динамические системы, ориентированные на данные (data-centered dynamic systems) ), интеллектуальный анализ данных, машинное обучение, извлечение информации и т.д.

Смотря в будущее, можно выделить три широкие области управления данными, в которых строгое математическое мышление может принести новые подходы и крайне необходимую ясность. Первая область относится к полному жизненному циклу так называемой «аналитики больших данных» (Big Data Analytics), то есть к применению методов статистики и машинного обучения для осмысления данных огромного объема и извлечения из них пользы. Вторая область связана с новыми формами создания и обработки данных, особенно когда они возникают в таких приложениях, как Web-коммерция, приложения социальных сетей, а также при управлении потоками работ и бизнес-процессами, основанными на данных. Третья область, которая только начинает появляться, – это разработка новых принципов и подходов для поддержки этического управления данными. Мы кратко проиллюстрируем некоторые базисные подходы к решению проблем из этих трех областей на примере семи тем исследований PDM, которые рассматриваются в этом отчете.

Для поддержки полного жизненного цикла аналитики больших данных требуется решить множество проблем, в чем может помочь PDM. В многочисленных источниках документально подтверждается, что в аналитическом исследовании от 50% до 80% трудозатрат может занимать так называемая «первичная обработка данных» (data wrangling). Проблемы первичной обработки данных можно описать в терминах «4 V» – «Объем (Volume), Скорость (Velocity), Разнообразие (Variety) и Достоверность (Veracity)», – все они решались и будут решаться с использованием точных подходов. Как мы обсудим позже, PDM вносит новый вклад в решение проблем объема и скорости. Например, в разд. 2 «Масштабируемая обработка запросов» рассказывается о последних достижениях в способах эффективной обработки n-образных соединений (n-way join) в сильно распараллеленных системах, которые превосходят традиционные подходы, основанные на последовательности бинарных соединений [18], [37]. В этом разделе также представлены различные парадигмы приблизительной обработки запросов, в частности, в потоковой среде, когда пользователь может завершить работу, если его удовлетворяет качество ответа. PDM вносит вклад в решение проблем разнообразия: в разд. 5 «Данные, обогащенные знаниями» описываются инструменты для управления такими данными и эффективного логического вывода с использованием онтологий производственного масштаба [33], а подобласть PDM мультимодельных данных (разд. 3) обеспечивает подходы для эффективного доступа к данным, представленным в различных стилях, от табличных до древовидных, графических и неструктурированных. Обеспечение достоверности является особенно важной задачей при выполнении анализа данных большого объема, учитывая неизбежность противоречивых и неполных данных. В подобласти PDM неточной информации (разд. 4) около сорока лет тому назад был предоставлен формальный подход к выполнению запросов при наличии неточных данных [79], но его вычислительная сложность затруднила массовое внедрение – проблема, для решения которой нужно удвоить усилия сообщества PDM. Новые интересные возможности открываются в подобласти управления данными и машинного обучения (разд. 6) из-за нетрадиционных способов, которыми алгоритмы конструирования признаков (feature engineering) и машинного обучения получают доступ к большим наборам данных и управляют ими. Мы также видим новые подходы к включению методов машинного обучения в системы управления базами данных, например, для более эффективного извлечения информации из текстов и управления ей [12].

Появившиеся новые формы создания и обработки данных привели к новым формам обновления данных, транзакций и управления данными в целом. Web-коммерция произвела революцию в том, как бизнес работает с данными цепочек поставок, финансовыми, производственными и другими видами данных, а также в том, как предприятия взаимодействуют со своими заказчиками, как с потребителями, так и другими предприятиями. Социальные приложения революционизировали нашу личную и общественную жизнь и теперь оказывают аналогичное влияние на рабочие места. Транзакции все чаще становятся распределенными, адаптированными и персонализированными, обрабатываются все быстрее и основываются на огромных наборах данных и развитой аналитике. Эти тенденции сочетаются с тем, как все более реальным становится Интернет вещей, используемый для повышения уровня удобства людей и эффективности бизнеса. Масштабной задачей является упрощение понимания всех этих данных и способов их обработки; подходы к решению этой проблемы предлагаются как в подобласти мультимодельных данных (разд. 3), так и в подобласти данных, обогащенных знаниями (разд. 5). Многие формы данных, происходящих из Интернета, в том числе из социальных сетей, из ответов на запросы к данным краудсорсинга и неструктурированных данных в целом приводят к созданию неточной информации (разд. 4). Развитие коммуникаций на основе Internet-технологий также позволило совершить революцию в организации процессов с электронной поддержкой – от традиционных бизнес-процессов, которые в настоящее время становятся частично автоматизированными, до систем электронной торговли, ориентированных на потребителя, и до все более оптимизированных коммерческих приложений и приложений цепочек поставок. Появились подходы для единообразного понимания процессов и данных и управления ими (разд. 7), что позволяет создать новое семейство автоматизированных методов верификации [35]; это будет становиться все более важным, поскольку автоматизация процессов ускоряется.

Хотя этическое использование данных всегда было проблемой, появление нового поколения приложений, ориентированных на данные и информацию, включая аналитику больших данных и социальные приложения, а также все более широкое использование данных в коммерции (в приложениях классов «бизнес-клиент» и «бизнес-бизнес») сделали этические соображения более важными и сложными. В настоящее время собираются огромные объемы данных об отдельных лицах; эти данные интерпретируются многими различными способами различными организациями, имеющими разные интересы. Новые исследования показывают, что использование математических принципов в исследованиях в подобласти этики и управления данными (разд. 8) может привести к новым подходам для обеспечения конфиденциальности данных отдельных граждан и соблюдения государственных и общественных норм на корпоративном уровне. Например, появляются механизмы, обеспечивающие точное и «безобидное» представление базовых данных при применении аналитических методов [50].

Выводы, содержащиеся в данном отчете, отличаются от выводов Бекманского отчета 2016 года [1] и дополняют их в двух основных аспектах. В обоих отчетах подчеркивается важность «больших данных» как единой крупнейшей движущей силы нашего времени как использования технологии управления данными, так и исследовательской работы в этой области. В настоящем докладе основное внимание уделяется исследовательским задачам, для решения которых применяются математические подходы, оказывавшие и продолжающие оказывать существенное влияние. В число таких задач входит разработка новых алгоритмов крупномасштабной параллельной обработки запросов и машинного обучения, в также моделей и языков, относящихся к неоднородной и неточной информации. В данном докладе также рассматриваются дополнительные подобласти, в которых исследования принципов управления данными могут внести возрастающий вклад в ближайшие годы, например, подходы к совместному использованию данных, структурированных в соответствии с различными моделями данных, единое управление процессами и данными, а также этика в управлении данными

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

2. Масштабируемая обработка запросов

Объем по-прежнему является важнейшей характеристикой больших данных. Сообщество PDM, а также сообщество теоретиков информатики внесло значительный вклад в эффективную масштабируемую обработку запросов (в отношении как объема, так и скорости). Несомненен огромный успех параллельных алгоритмов, алгоритмов, связанных с использованием внешней памяти, потоковых алгоритмов и т.д. при их применении в крупномасштабных системах баз данных. Иногда вклад теоретических основ может проявляться не мгновенно, например, системному сообществу понадобилось более десяти лет, чтобы воплотить теоретическую массовую синхронную параллельную модель (bulk synchronous parallel (BSP)) Валианта (Valiant) [109] в системе MapReduce. Но это и означает, что никогда не следует недооценивать ценность теории.

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

Разработка новых парадигм для многоходовой обработки соединений. Выдающийся результат, полученный Ацериасом (Atserias), Гроэ (Grohe) и Марксом (Marx) [18], привел к целому ряду исследований, посвященных поиску новых способов вычисления многоходовых соединений. Во всех современных реляционных системах баз данных многоходовое соединение обрабатывается по попарной схеме с использованием двоичного дерева (плана), которое выбирается оптимизатором запросов ^[1]. Однако недавние теоретические исследования обнаружили, что для многих запросов и экземпляров данных стоимость наилучшего двоичного плана отличается от стоимости оптимального плана большим полиномиальным сомножителем. С того времени алгоритмы, оптимальные в худшем случае, были разработаны для моделей основной памяти [86], внешней памяти [65] и BSP [23], [5]. Разработчики всех этих новых алгоритмов отказались от парадигмы бинарного дерева, время применяя для достижения оптимальности более глобальный подход. Отрадно, что были проведены эмпирические исследования [37], которые демонстрируют практичность этих новых алгоритмов. В частности, оптимальный в худшем случае алгоритм скачкообразного соединения (leapfrog join) [111], реализован внутри полнофункциональной системы баз данных. Поэтому мы полагаем, что недавно разработанные в теоретическом сообществе алгоритмы могут изменить то, как в настоящее время обрабатываются многоходовые соединения в системах баз данных. Конечно, это может быть достигнуто только с помощью значительных инженерных усилий, особенно при разработке и внедрении новых оптимизаторов запросов и методов оценки стоимости планов в рамках новой парадигмы.

Приближенная обработка запросов. Большинство аналитических запросов к большим данным возвращают агрегированные ответы, которые не обязательно должны быть точными на 100%. В исследовательском направлении онлайн-агрегации [63] изучаются новые алгоритмы, которые позволяют процессору запросов на ранних стадиях обработки запроса возвращать приблизительные результаты (со статистическими гарантиями), чтобы пользователь мог прекратить обработку запроса, как только точность ответа станет приемлемой. Это улучшает интерактивность и сокращает неоправданное потребление ресурсов. Недавние исследования показали некоторые обнадеживающие результаты [62], [76], но все еще есть много возможностей для совершенствования. (1) В существующих алгоритмах для выборки из полного результата запроса использовались только простая случайная выборка или выборка на основе случайных блужданий (random walks). Более сложные методы, например, методы Монте-Карло с цепями Маркова (Markov Chain Monte Carlo) могут оказаться более эффективными. (2) В сообществе разработчиков алгоритмов потоковой обработки данных создано много методов для свертывания (summarization) больших наборов данных в компактные структуры данных с сохранением важных свойств данных. Эти методы свертывания данных могут быть полезны и при приближенной обработке запросов. (3) Реальная интеграция этих методов в современные механизмы обработки данных остается значительной практической проблемой.

Эти практические проблемы приводят к следующим теоретическим проблемам.

Связь между различными вычислительными моделями больших данных. В сообществе теоретиков компьютерной науки разработано много прекрасных вычислительных моделей, нацеленных на обработку наборов данных, которые слишком велики для традиционной модели машины с произвольным доступом к памяти (random access machine, RAM). К числу наиболее известных моделей относятся параллельная RAM (PRAM), модель внешней памяти (external memory, EM), потоковая модель, модель BSP и ее последние усовершенствования для моделирования современных распределенных архитектур. Некоторые исследования показывают, что существуют глубокие связи между вроде бы несвязанными вычислительными моделями больших данных потоковых вычислений, параллельной обработки и внешней памяти, особенно для класса задач, представляющих интерес для сообщества PDM (например, реляционная алгебра) [54], [72]. Исследование этих связей позволило бы выявить природу этих проблем по отношению к масштабируемым вычислениям, а также позволило бы нам использовать богатый набор идей и инструментов, которые теоретическое сообщество разработало за десятилетия.

Коммуникационная сложность параллельной обработки запросов. В новых крупномасштабных системах анализа данных для поддержки сложных запросов к большим наборам данных используется массивный параллелизм. В этих системах используются кластеры серверов, и для выполнения запроса требуется несколько раундов коммуникаций этих серверов. В таких системах ограничивающим фактором, как правило, является стоимость коммуникаций, которая является основной мерой сложности алгоритмов, разработанных в расчете на массивно-параллельную архитектуру. В недавних исследованиях (например, [23]) удалось определить строгие верхние и нижние границы стоимости коммуникаций, требуемых для выполнения некоторых запросов с соединениями, но многие вопросы остаются открытыми. (1) Существующие границы являются строгими только для однораундовых алгоритмов. Однако в новых крупномасштабных системах, таких как Spark, значительно повышена эффективность многораундовых итерационных вычислений, поэтому ограничение в один раунд кажется нецелесообразным. Определение коммуникационной сложности многораундовых вычислений остается в значительной степени открытой проблемой. (2) Имеющиеся результаты относятся только к небольшому классу запросов (полных конъюнктивных запросов – full conjunctive queries^[2]), в то время как многие другие типы запросов остаются без внимания. Если не вдаваться в детали, существует большой интерес к крупномасштабному машинному обучению с использованием массивно-параллельных систем, поэтому интересно и важно изучать коммуникационную сложность классических задач машинного обучения в рамках этих моделей. Это более подробно обсуждается в разд. 6, в котором обобщаются возможные направления исследований на стыке управления данными и машинного обучения. Массивно-параллельная обработка запросов поднимает много других (практических и фундаментальных) исследовательских вопросов. Например, последние фреймворки оптимизации параллельных запросов необходимо распространить на случай многораундового выполнения запросов [10]. Мы полагаем, что для решения отмеченных выше проблем (которые не рассматриваются как проблемы «классической» области PDM или теории баз данных) будут полезны методы следующих теорий: статистики, теории выборок (sampling theory)), теория приближений, коммуникационная сложность, теория информации, выпуклая оптимизация (convex optimization).

3. Мультимодельные данные: на пути к открытой экосистеме моделей данных

За последние 20 лет ландшафт доступных данных резко изменился. Несмотря на то, что огромное количество доступных данных воспринимается как явное положительное явление, с использованием этих данных связаны проблемы «четырех V», упомянутые во введении.

Одним из конкретных аспектов разнообразия данных является существование и сосуществование различных моделей для полуструктурированных и неструктурированных данных в дополнение к широко используемой модели реляционных данных. К числу примеров относятся древовидные данные (XML, JSON), графические данные (RDF, графы свойств (property graph), сети), табличные данные (CSV – comma separated data), временные и пространственные данные, текст и мультимедиа. Можно ожидать, что в ближайшем будущем появятся новые модели данных для удовлетворения конкретных потребностей. Важно отметить, что модели данных определяют не только способ структурирования данных, но также, среди прочего, подходы к формулировке запросов, операций обновления, ограничений целостности, представлений, а также к интеграции и преобразованию.

Успех реляционной модели данных, основанной на тесном взаимодействии теории и практики, побудил сообщество PDM к многолетней работе над формальной интерпретацией каждой из упомянутых моделей. Применительно к ним были заново рассмотрены классические темы области баз данных – схемы баз данных и языки запросов, обработка и оптимизация запросов, инкрементная обработка эволюционирующих данных, работа с несогласованными и неполными данными, интеграция данных, обмен данными и т.д. Это направление работы было успешным как с теоретической, так и с практической точек зрения. Поскольку даже для существующих моделей данных не для всех вопросов удалось получить полные ответы, и эти вопросы будут задаваться снова при появлении новых моделей, будут возникать все новые практически важные теоретические проблемы. Но то, что мы рассматриваем как новый грандиозный вызов, – это обеспечение сосуществования и взаимосвязи всех этих моделей, что еще более осложняется необходимостью быть готовым к появлению в любое время новых моделей.

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

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

Понимание данных. Как понять смысл данных? Ранее можно было обратиться к структурной информации, предоставляемой вместе с данными. Но в настоящее время данные вряд ли когда-либо поступают вместе достаточной структурной информацией, и нужно выяснять их структуру. Можем ли мы помочь пользователю и системам понять данные, не раскрывая их структуру полностью?

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

Обработка данных. Как эффективно выполнять запросы? Десятилетия усилий принесли изощренные методы ускорения обработки реляционных данных; достижение аналогичной эффективности для других моделей данных, даже самых зрелых, таких как XML, все еще остается проблемой. Но пришло время задуматься об обработке данных (возможно, распределенных и неполных), объединяющих несколько моделей.

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

Языки схем. Разработка гибких и надежных мультимодельных языков схем. Языки схем для данных XML и RDF стандартизированы, предпринимаются усилия для создания стандартов для JSON [90], обобщенных графовых данных [100] и табличных данных [82], [16]. Мультимодельные языки схем должны обеспечивать единообразный подход к различным моделям, способность описывать взаимные отображения моделей (реализация разных представлений для одних и тех же данных в духе интеграции данных) и гибкость, позволяющую легко включать новые модели по мере их появления.

Извлечение схем. Предоставление эффективных алгоритмов извлечения схем из данных или, по крайней мере, обнаружения частичной структурной информации (ср. [27], [31]). Давняя проблема разрешения сущностей (entity resolution)усугубляется в контексте поиска соответствий между наборами данных, структурированными в соответствии с различными моделями [107].

Визуализация данных и метаданных. Разработка удобных для пользователя парадигм представления метаданных и статистических свойств данных таким образом, чтобы это помогало при формулировании запросов. В идеальном решении пользователям должна представляться уместная информация о данных и метаданных при вводе запроса. Для этого требуются возможности понимания и определения того, что представляет собой уместная информация в конкретном контексте, а также представление этой информации таким образом, чтобы обеспечить ее эффективное обновление при изменении контекста (см. [36], [15]).

Языки запросов. Выход за рамки специализированных языков запросов, ориентированных на конкретные модели данных [14], и разработка языка запросов, пригодного для мультимодельных данных, с включением специализированных языков запросов в качестве подъязыков или с обеспечением единого подхода к формулировке запросов, возможно, за счет понижения выразительной мощности или усложнения языка.

Выполнение и оптимизация запросов. Обеспечение эффективных алгоритмов вычисления разумных ответов на запросы на основе структурной информации о данных, как межмодельных, так и внутримодельных. Этого можно достичь решено напрямую [70], [58] или путем применения статической оптимизации [24], [40]. В контексте распределенной или неполной информации даже формализация понятия осмысленного ответа является сложной задачей [78], что более подробно обсуждается в разд. 4.

Для решения всех этих проблем требуется применение мощных средств PDM и компьютерной науки в целом (теория сложности, логика, теория автоматов и т.д.) Но для их решения также потребуются знания и методы из соседних сообществ. Например, вторая, третья и пятая проблемы, естественно, связаны с аспектами интеллектуального анализа данных и машинного обучения (см. разд. 6). Первая, вторая и третья проблемы имеют отношение к вопросам представления знаний (см. разд. 5). Для решения первой и четвертой проблем требуют профессиональные знания языков программирования. Пятая проблема находится на стыке между PDM и теорией алгоритмов, а также между PDM и теорией систем. Третья проблема затрагивает вопросы взаимодействия человека и компьютера.

4. Неопределенная информация

Неполная, неопределенная и противоречивая информация повсеместно распространена в приложениях управления данными. Это было признано уже в 1970-х годах [39], и с тех пор значимость вопросов, связанных с неполнотой и неопределенностью, неуклонно возрастает: жизненные реалии состоят в том, что факты, с которыми нам повседневно приходится обращаться, редко бывает полными. Однако, хотя в области управления данными были разработаны методы, предназначенные специально для обработки неполных данных, их текущее состояние оставляет желать лучшего как теоретической, так и с практической точек зрения. Даже при выполнении SQL-запросов над неполными базами данных – проблема, решения которой можно было бы ожидать после более чем сорокалетнего периода развития реляционной технологии – можно получить результаты, которые вынуждают людей говорить: «Никогда нельзя доверять ответам, которые получены из [неполной] базы данных» [41]. И мы на самом деле знаем, что ответ на SQL-запрос может содержать любые ошибки, которые только можно себе представить, если в базе данных присутствуют неопределенные значения [77].

Со стороны теории у нас, как кажется, имеется хорошее понимание того, что необходимо для получения корректных результатов: вычисление надежных ответов (certain answer) на запросы. Это ответы, которые верны во всех полных базах данных, совместимых с данной неполной базой данных. Эта идея, появившаяся также в конце 1970-х годов, стала реальным способом предоставления ответов на запросы во всех приложениях, от классических баз данных с неполной информацией [67] до новых приложений, включающих интеграцию данных и обмен данными [74], [13], приложениях с согласованными ответами на запросы (consistent query answering) [26], приложениям с доступом к данным на основе онтологий [33] и т.д. Причина, по которой эти идеи нашли ограниченное применение в доминирующих системах баз данных, заключается в их сложности. Как правило, достоверные ответы на запросы к неполным базам данных могут быть эффективно вычислены для конъюнктивных запросов или некоторых тесно связанных с ними классов запросов, но без этих ограничений проблема быстро становится трудноразрешимой (иногда даже неразрешимой). Поскольку для реальных систем это не годится, в них применяются специальные решения, обеспечивающие эффективность в ущерб корректности; отсюда и происходит странное и неожиданное поведение.

Хотя даже основные проблемы, связанные с неполнотой реляционных баз данных, остаются нерешенными, сейчас мы постоянно имеем дело с более разнообразными типами неполных и неcогласованных данных. Ярким примером являются вероятностные базы данных [103], где достоверность ответа на запрос – это общий вес миров, поддерживающих этот ответ. Как и в случае вычисления точных ответов, вычисление вероятностей точных ответов, как правило, затруднительно, и тем не менее эта тема стала предметом теоретических исследований.

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

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

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

Конечно, это приведет к массе новых проблем. Как хранить/представлять более содержательные виды неопределенной информации, которые выходят далеко за рамки неопределенных значений в РСУБД? В приложениях интеграции данных, обмена данными, доступа к данным на основе онтологий и т.д. часто требуется большие возможности (по крайней мере, помеченные неопределенные значения (marked null)^[3]), и можно представить много других возможностей (например, интервалы для числовых значений). Это тесно связано с задачей моделирования данных, описанной в разд. 3.

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

Обработка несогласованных данных. Как сделать так, чтобы обработка несогласованности данных (в частности, обеспечение согласованных ответов на запросы) была применима на практике? Как это использовать при очистке данных (data cleaning)? Опять же, в этом направлении есть много сильных теоретических результатов, но они получены в первую очередь при исследованиях границ разрешимости проблемы и определении сложности решений для подклассов конъюнктивных запросов, а не при выработке практически применимых методов ответов на запросы. Имеются многообещающие работы по обогащению теоретических методов согласования данных информацией о предпочтениях пользователей [101] или онтологиями [51] в соответствии с подходами, описанными в разд. 5, но потребуется выполнить гораздо больше фундаментальных исследований, прежде чем удастся выйти на уровень практических инструментов.

Обработка вероятностных данных. Распространенные модели вероятностных баз данных, пожалуй, являются более простыми ограниченными, чем модели, изучаемые сообществами статистики и машинного обучения. Однако с применением вероятностных баз данных можно имитировать общие сложные модели, если удается поддерживать выразительные языки запросов [69]; таким образом, сложность модели может быть заменена сложностью запроса. Поэтому очень важно разработать методы приблизительных ответов на запросы на выразительных языках запросов, на больших объемах данных, с практически допустимыми затратами на выполнение. Хотя основное внимание сообщества PDM было сосредоточено на детерминированных и точных решениях [103], мы считаем, что больше внимания следует уделять статистическим методам с гарантиями точности аппроксимации, таким как выборочный подход (sampling approach), обычно используемый в сообществах (Байесовского) машинного обучения и статистики. В разд. 6 мы более подробно обсудим вычислительные проблемы машинного обучения в контексте баз данных.

Теоретические проблемы можно разделить на три группы.

Моделирование. Нам необходимо обеспечить прочную теоретическую основу для решения описанной выше практической задачи моделирования; это означает понимание различных типов неопределенности и их представлений. Как и при изучении любого другого типа информации, хранящейся в базах данных, у сообщества PDM возникает много вопросов, связанных со структурами данных, методами индексирования и т.д.

Есть и другие проблемы, связанные с моделированием данных. Например, когда мы можем сказать, что некоторые данные верны? Эта проблема особенно актуальна для краудсорсинговых приложений [95], [61]: наличие данных, которые выглядят полными, еще не означает, что они верны, как это часто предполагается.

Еще одна важная проблема связана с моделированием ответов на запросы. Как ранжировать неточные ответы на запросы? Имеется тенденция делить все ответы на точные и неопределенные, но часто это бывает слишком грубо.

Сообщества языков программирования и машинного обучения изучают вероятностное программирование [56] как парадигму, позволяющую разработчикам легко программировать решения машинного обучения. Сообщество баз данных возглавляет разработку парадигм для простого программирования при использовании больших объемов данных. Как подробно обсуждается ниже в разд. 6, мы считаем, что в настоящее время требуют усовершенствования технологии баз данных за счет использования средств машинного обучения. В частности, важной задачей является объединение двух ключевых возможностей (машинного обучения и данных) на основе языков запросов для построения статистических моделей; некоторые результаты уже имеются [21], [32].

Логический вывод. По этому поводу ведется много работ; см. разд. 5 о необходимости разработки инструментов логического вывода следующего поколения для задач управления данными. Когда дело доходит до использования таких инструментов с неполными и неточными данными, возникают следующие основные проблемы. Как производить логический вывод при наличии неполных данных? Как интегрировать разные типы неопределенности? Как учиться писать запросы к неопределенным данным? Что на самом деле говорят ответы на запросы, если эти запросы адресуются к неопределенным данным? То есть, как можно обобщить результаты запросов к конкретному набору неполных данных.

Алгоритмы. Чтобы преодолеть высокий уровень сложности, часто приходится прибегать к приближенным алгоритмам, но методы аппроксимации отличаются от стандартных методов, используемых в базах данных, поскольку они не только ускоряют выполнение, но и обеспечивают корректность. Потребность в таких приближениях приводит к множеству теоретических проблем. Как разрабатывать такие алгоритмы? Как показать корректность реляционных и других данных? Как оценить качество ответов на запросы? Как учитывать предпочтения пользователей?

Хотя все перечисленные пункты являются важными темами исследований, которые необходимо выполнить, есть несколько аспектов, которые можно рассматривать как приоритетные, не в последнюю очередь потому, что в них существует непосредственная связь между теорией и практикой. В частности, нужно обратить пристальное внимание на следующие задачи: (1) понять, что означает правильность или неправильность ответов на запросы, и как скорректировать стандартную реляционную технологию, чтобы можно было гарантировать, что пользователю никогда не будут возвращаться неправильные ответы; (2) предоставить и обосновать бенчмарки для работы с неполными/неопределенными данными; (3) разработать алгоритмы аппроксимации для классов запросов, которые заведомо трудноразрешимы; и (4) приложить усилия для достижения практичности подхода согласованных ответов на запросы и применить его в сценариях очистки данных.

Стоит отметить, что вопросы неопределенных данных часто рассматриваются в контексте очистки данных, исходя из предположения, что неопределенность вызвана наличием ошибочных (грязных) данных (dirty data). При очистке данных устранению неопределенности уделяется основное внимание, намного большее, чем запросам над данными, которым мы не совсем доверяем. Однако потребность в таких запросах нельзя игнорировать, поскольку методы очистки данных не всегда позволяют избавиться от неопределенных данных. На самом деле, тот факт, что данные являются неочищенными, лишь иногда – но далеко не всегда – является причиной неопределенности, а область неопределенных данных охватывает множество сценариев, которые не затрагиваются при очистке данных. К этим сценариям относятся обработка неопределенных значений в базах данных (неопределенные значения не всегда связаны с грязными данными) и вероятностные данные, где неопределенность связана с природой данных, а не с их ошибочностью. Среди рассматриваемых в данном отчете тем ближе всего к очистке данных находятся методы обеспечения согласованных ответов на запросы, но даже здесь фокус будет другим, поскольку эти методы позволяют увидеть, что можно осмысленно извлечь из данных, если их нельзя полностью очистить.

5. Управление данными, обогащенное знаниями

За последние два десятилетия мы стали свидетелями постепенного перехода из мира, в котором почти все данные, используемые компаниями и организациями, являлись надлежащим образом структурированными, аккуратно собирались в реляционные базы данных и считались полными, в мир, в котором данные являются неоднородными и распределенными, а также не могут быть больше считаться полными. Кроме того, у нас имеются не только огромные объемы данных; у нас также есть очень большие объемы ценных знаний о прикладной области данных в форме таксономий или полноценных онтологий, а также правила интерпретации данных и т.д. Методы и инструменты для управления такой сложной информацией широко изучались в подобласти представления знаний широкой исследовательской области искусственного интеллекта. В частности, были предложены основанные на логике формализмы, например, дескриптивная логика, а также различные языки, основанные на правилах, и разработаны соответствующие механизмы логического вывода. Однако при выполнении исследований в этой подобласти не делался особый акцент на традиционных задачах управления данными, а именно на наличии огромных объемов данных и потребности эффективно определять и выполнять сложные операции с данными, включая запросы и обновления.

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

Предоставление конечным пользователям гибкого и интегрированного доступа к данным. Ключевым требованием при работе со сложными, распределенными и разнородными данными является предоставление конечным пользователям возможности напрямую управлять такими данными. Это сложная задача, поскольку конечные пользователи могут обладать глубокими знаниями в конкретной интересующей их области, но в большинстве случаев не являться экспертами по управлению данными. В результате они могут быть не знакомы с традиционными методами и технологиями баз данных, например, могут не уметь формулировать сложные запросы или операции обновления, возможно, обращаясь к нескольким источникам данных, между которыми данные могут быть распределены, и понимать последствия для производительности. Для решения этой проблемы в качестве общей парадигмы недавно было предложено управление данными на основе онтологий. Этот подход основан на предположении, что онтология предметной области, содержащая сложные знания, может использоваться для управления данными путем связывания ее с источниками данных с помощью декларативных отображений [91]. После этого все информационные потребности конечных пользователей и их требования к управлению данными формулируются в терминах такой онтологии, а не источников данных, и автоматически транслируются в операции (запросы и обновления) над источниками данных. Открытые проблемы связаны с потребностью иметь дело с распределенностью данных, обработкой неоднородности как на интенсиональном, так и на экстенсиональном уровнях, с выполнением обновлений источников данных через онтологию и отображения, а также с достижением хорошей производительности даже при наличии крупных онтологий, сложных отображений и огромных объемов данных [33], [57], [59].

Обеспечение интероперабельности на уровне обмена данными между системами. Обогащение данных знаниями актуально не только для обеспечения доступа к данным конечных пользователей, но также обеспечивает непосредственное взаимодействие систем на основе обмена данными и знаниями на системном уровне. Для этого требуется определение и согласование стандартизованных онтологий, охватывающих все требуемые аспекты конкретных интересующих областей, а также их многочисленные модальности, в частности, временную и пространственную. Конкретной областью, в которой это начинает играть важную роль, является электронная коммерция, где стандартные онтологии уже доступны [64].

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

Использование знаний в области анализа и извлечения данных. Для выполнения сложного анализа и создания прогнозов собирается все больше данных. В настоящее время такие операции в основном основываются на данных в «сырой» форме, но есть огромный потенциал для повышения эффективности аналитических операций за счет обогащения и дополнения таких данных знаниями предметной области и использования этих знаний в процессе анализа и извлечения данных. Проблемы включают выбор надлежащих формализмов для выражения знаний как о необработанных, так и агрегированных/производных данных, разработку алгоритмов, основанных на знаниях, для извлечения данных и аналитики, в частности, для преодоления низкого качества данных, а также для работы с экстремальными отклонениями значений данных.

Обеспечение удобства для пользователей при управлении данными и знаниями. Системы, сочетающие большие объемы данных со сложными знаниями, сами по себе очень сложны, и поэтому их сложно разрабатывать и поддерживать. Соответствующие инструменты, поддерживающие все фазы жизненного цикла таких систем, должны быть спроектированы и разработаны на основе новых пользовательских интерфейсов для различных компонентов. Такие инструменты должны сами полагаться на знания предметной области и сложные механизмы логического вывода над такими знаниями, чтобы обеспечить более удобное взаимодействие скорее специалистам предметных областей, а не экспертам по информационной технологии или управлению данными. Поддерживаемые задачи должны включать в себя проектирование и сопровождение онтологий и отображений (включая поддержку отладки), формулировку запросов, интерпретацию результатов логического вывода и исследование данных и знаний [55], [73], [48], [15].

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

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

Выбор/разработка уместных языков. Языки и формализмы, применяемые в различных компонентах систем управления данными, обогащенных знаниями, должны поддерживать разные типы знаний и данных, например, смешивать предположения об открытом и закрытом мирах^[4] и позволять представлять временные, пространственные и другие аспекты информации [34], [19], [29], [17], [87]. Понятно, что требования к выразительной способности таких языков могут привести к формализмам, которые сделают различные задачи логического вывода неразрешимыми очень трудно разрешимыми. Поэтому при выборе или разработке уместных языков необходимо прагматично руководствоваться потребностями пользователей и приложений.

Новые меры сложности. Чтобы можно было надлежащим образом оценить производительность таких систем и уметь отличать простые случаи, должны хорошо обрабатываться, от сложных, требуются нетрадиционные меры сложности, которые не вписываются в рамки общепринятой сложности в наихудшем случае. В их число могут входить приемлемые формы сложности в среднем случае или параметризованной сложности, сложности с учетом распределения данных (в Web) и формы сглаженного анализа (smoothed analysis).

Службы логического вывода нового поколения. Разновидности служб логического вывода, требуемых в контексте приложений управления данными, обогащенных знаниями, выходят далеко за рамки традиционного логического вывода, принятого в области представления знаний, который обычно состоит из проверки согласованности, классификации и извлечения экземпляров классов. Требуемые формы логического вывода включают обработку сложных запросов при наличии знаний, интерпретацию (explanation) данных (которую можно считать обобщением поддержки информации о происхождении данных (provenance)), абдуктивный логический вывод (abductive reasoning), гипотетический логический вывод ((hypothetical reasoning), логический вывод, устойчивый к несогласованности (inconsistency-tolerant reasoning)^[5], и пересматриваемый логический вывод (defeasible reasoning), позволяющий учитывать исключения из правил. Особенно полезны формы логического вывода на основе неточных данных, в частности, вероятностных или нечетких (fuzzy) данных и знаний, так же как и логический вывод на метауровне (meta-level reasoning)^[6]. Кроме того, потребуется разработать новые формы логического вывода, в которых будут учитываться нефункциональные требования, в частности, различные показатели качества данных (полнота, надежность, согласованность) и методы повышения качества данных. Хотя такие формы логического вывода уже начали изучаться по отдельности (см., например, [52], [30], предстоит еще много работы по их объединению, включению в системы управления данными и достижению необходимого уровня производительности.

Учет временных и динамических аспектов. Ключевая проблема заключается в том, что данные и знания не статичны и изменяются со временем, например, из-за обновлений данных с учетом знаний, разновидностей потоковых данных и вообще данных, которыми манипулируют процессы. Обращение с динамическими данными и знаниями, а также предоставление средств логического вывода (например, формальной верификации) в присутствии как данных, так и знаний является чрезвычайно сложной задачей, для решения которой потребуется разработка новых методов и инструментов [35], [17].

Таким образом, внедрение предметно-ориентированных знаний в управление данными одновременно является и прекрасной возможностью, и серьезной проблемой. Этот подход содержит огромные возможности для того, чтобы сделать системы, ориентированные на данные, более интеллектуальными, гибкими и надежными, но влечет за собой вычислительные и технические проблемы, которые необходимо преодолеть. Мы считаем, что в ближайшие годы можно добиться многого. Действительно, растущее взаимодействие сообщества PDM и сообщества представления знаний является очень плодотворным, особенно благодаря попыткам понять сходства и различия между формализмами и методами, используемыми в обеих областях, и получению новых результатов, основанных на взаимном понимании. Дальнейшее тесное сотрудничество обеих областей представляется наиболее многообещающим способом достижения целей в направлении управления данными, обогащенными знаниями.

6. Управление данными и машинное обучение

Мы считаем, что исследования, сочетающие в себе управление данными (Data Management, DM) и машинное обучение (Machine Learning, ML), особенно важны, поскольку эти области могут извлекать пользу одна от другой. В настоящее время системы, созданные сообществом ML, сильны своими возможностями статистического логического вывода, а системы, созданные сообществом DM, сильны в своей поддержке семантики данных, сопровождения и масштабирования. Эта взаимодополняемость полезных качеств сопровождается различиями в основных механизмах: сообщество PDM в значительной степени приняло методологии, основанные на логике, в то время как сообщество ML базируется на теории вероятностей и статистике. Однако для поддержки современных приложений требуются системы, которые сильны в обоих аспектах, обеспечивая тщательное и изощренное управление данными при одновременном учете присущей им статистической природы. Мы предвидим множество исследовательских возможностей на пересечении PDM и ML.

Мы выделяем несколько направлений исследований, которые мы классифицируем на две категории: DM для ML и ML для DM. Категория DM для ML включает в себя направления, направленные на расширение возможностей ML за счет использования свойств данных. Ключевые проблемы заключаются в следующем.

Генерация и конструирование признаков (Feature Generation and Engineering). Генерация признаков относится к проблеме разработки и извлечения сигналов, которые необходимо предоставить имеющемуся алгоритму машинного обучения общего назначения, чтобы должным образом выполнить желаемую операцию (например, классификацию или регрессию). Это важная и трудоемкая задача [71], а также центральная тема современных методологий машинного обучения, таких как ядерные методы машинного обучения (kernel-based ML), где сложные признаки создаются неявно с помощью ядерных функций [97], и глубокое обучение (deep learning), где низкоуровневые функции объединяются в функции более высокого уровня иерархическим образом [25]. В отличие от обычных алгоритмов машинного обучения, которые рассматривают признаки как числовые значения, у системы баз данных имеется доступ к запросам и понимание результатов запросов, которые преобразуют необработанные данные в эти признаки. Таким образом, PDM может вносить свой вклад в конструирование признаков различными способами, особенно на семантическом уровне, и также обеспечить решения следующих проблем. Как разработать эффективные языки для создания признаков на основе запросов? Как использовать такие языки для разработки набора дополнительных, неизбыточных признаков, оптимально подходящих для текущей задачи ML? Подходит ли данный язык для определенного класса задач ML? Важные критерии хорошего качества языка признаков включают оценки рисков того, что наборы данных для обучения будут недообучающими (underfitting) или переобучающими (overfitting), а также вычислительную сложность выполнения (как для обучающих, так и для тестовых данных). Сообщество PDM уже исследовало проблемы подобного характера [60].

Предпосылка глубокого (нейросетевого) обучения заключается в том, что модель обладает достаточной выразительной способностью для работы только с исходными (raw) низкоуровневыми признаками и для реализации процесса автоматической, управляемой данными генерации высокоуровневых признаков [25]. Это вселяет существенную надежду на сокращение усилий при ручном конструировании признаков. Существует ли общий способ решения задач ML путем применения глубокого обучения непосредственно к базе данных (как это уже было сделано, например, с семантическим хешированием (semantic hashing) [94])? Могут ли запросы к базам данных (на разных языках) дополнять нейронные сети за счет выразительности и/или эффективности? И если да, то где проходит граница между уровнем конструирования признаков и сложностью сети?

Крупномасштабное машинное обучение. В настоящее время машинное обучение применяется к наборам данных значительного размера, включая потенциально неограниченные потоки данных. В таких условиях эффективное управление данными и использование соответствующих структур данных, которые обеспечивают алгоритму обучения быстрый доступ к данным, являются основные предпосылками эффективной по использованию ресурсов времени и памяти реализации индуктивного построения модели (model induction) (во время обучения) и логического вывода (inference) (во время прогнозирования) [92]. Исследования в этом направлении в последние годы расширились и включают, например, использование хеширования [112], фильтров Блюма [38] и древовидных структур данных [45] в алгоритмах обучения. Кроме того, было продемонстрировано, что сжатие без потерь больших наборов данных, свойственное факторизованным базам данных (factorized databases) [89], резко снижает стоимость выполнения задач машинного обучения. К этой теме также относятся работы по распределенному машинному обучению, когда хранение данных и вычисления данных производятся в сети распределенных устройств [6], и по поддержке машинного обучения системами управления потоками данных [84].

Анализ сложности. Сообщество PDM создало мощные механизмы для детального анализа сложности запросов; см., например, [9]. Анализ сложности на таком уровне детализации очень желателен для сообщества ML, особенно для анализа алгоритмов обучения, которые включают различные параметры, такие как объем ввода-вывода и число обучающих примеров [68]. Недавно были продемонстрированы результаты в этом направлении, связывающие сложность запросов в DM и сложность обучения в ML [96].

Мотивацией исследовательских направлений второй категории – ML для DM является возможность усилить основные возможности управления данными с помощью ML. Традиционно системы управления данными поддерживают основной набор операций запросов (например, реляционную алгебру, функции группирования и агрегирования, рекурсию), которые считаются обычным требованием со стороны приложений. Мы считаем, что этот базовый набор следует пересмотреть, а конкретнее, дополнить его обычными операциями ML.

Ярким примером, вызванным ростом числа доступных и ценных текстовых ресурсов, являются различные предложенные формализмы для включения средств извлечения информации из текста в реляционную модель [53, 98]. Однако, в отличие от структурированных данных, текстовые ресурсы связаны с высоким уровнем неопределенности из-за неконтролируемой природы контента и неточного характера обработки естественного языка. В связи с этим, для извлечения надежной информации из текста требуются методы ML.

Мы считаем, что внедрение машинного обучения является естественным развитием PDM. Системы баз данных, которые включают статистические средства и машинное обучение, уже разработаны [99], [12]. Языки запросов традиционно разрабатываются с акцентом на декларативность: в запросе указывается, как ответ должен логически соотноситься с содержимым базе данных, а не то, как он должен вычисляться алгоритмически. Внедрение ML привносит более высокий уровень декларативности: указывается, как должен себя вести конечный результат (на примерах), но не обязательно говорится, какой запрос приведет к получению такого результата.

В этом духе мы предлагаем следующие направления соответствующих исследований в области PDM.

Унифицированные модели. Значимая роль сообщества PDM заключается в определении общих формализмов и семантики для сообщества баз данных. Поэтому важной возможностью является определение «реляционной алгебры» систем управления данными со встроенными операциями машинного обучения/статистики.

Оптимизация с потерями. С первых дней существования сообщества PDF в центре его внимания находилась оптимизация без потерь, то есть оптимизация, не приводящая к изменению конечного результата. Как упоминалось в разд. 2, в некоторых сценариях имеет смысл применять оптимизацию с потерями (lossy), которая гарантирует получение только приближения истинного ответа. Включение машинного обучения в модель запросов обеспечивает дополнительные возможности для оптимизации с потерями, поскольку парадигмы обучения обычно связаны со встроенными функциями качества (или «риска»). Следовательно, мы можем принимать во внимание возможность снижения стоимости выполнения запросов, если это лишь ограниченным образом влияет на качество конечного результата [8]. Например, Риондато (Riondato) и др. в [93] разрабатывают метод случайной выборки из базы данных для оценки селективности заданного запроса. Для заданного класса запросов выполнение любого запроса в этом классе над образцом обеспечивает точную оценку селективности запроса в исходной большой базе данных.

Оценка достоверности. После включения в систему управления данными статистических компонентов и компонентов машинного обучения становится критически важным правильно оценить достоверность (confidence) ответов на запросы [99], поскольку это обеспечивает принципиальный подход к балансировке между точностью (precision) и полнотой (recall). Тем самым, важным направлением является создание вероятностных моделей, в которых фиксируется комбинированный процесс выполнения запроса и которые позволяют оценить вероятности конечных результатов. Например, применив к запросам к базе данных понятие размерности Вапника-Червоненкиса (Vapnik-Chervonenkis dimension) – важное теоретическое понятие в теории обобщений (generalization theory), Риондато и др. [93] обеспечивают точные границы для своих оценок селективности, которые соблюдаются с высокой вероятностью; кроме того, они вычисляют одновременно соблюдаемую вероятность ошибок оценок селективности всех запросов в заданном классе запросов. Вообще говоря, в этом направлении могут использоваться результаты исследований вероятностных баз данных последнего десятилетия [104], которые могут комбинироваться с теоретическими основами машинного обучения, например, обучение ВПК-обучением (вероятно приближённо корректное обучение, Probably Approximately Correct Learning, PAC-learning) [110].

В общем, имеется множество исследовательских проблем по совершенствованию машинного обучения с помощью методов управления данными (DM для ML) и по усилению технологий управления данными с помощью возможностей машинного обучения (ML для DM). Требуемые методологии и формальные основы охватывают ряд связанных областей, в частности, логику, формальные языки, сложность вычислений, статистический анализ и распределенные вычисления. Мы сформулировали темы теоретических исследований, но очевидно, что в каждом из таких исследований придется столкнуться с практической проблемой разработки эффективных решений для реальных систем, а также достоверных наборов данных и тестов.

7. Процессы и данные

Многие формы данных развиваются со временем, и большинство процессов обращаются к наборам данных и изменяют их. Промышленность работает с огромными объемами развивающихся данных, прежде всего в форме транзакционных систем и систем управления бизнес-процессами (Business Process Management, BPM). В последнее десятилетие растет число исследований основополагающих проблем систем, объединяющих процессы и данные, включая разработку формальных моделей, фреймворков для сравнения их выразительной способности, подходов для поддержки верификации поведенческих свойств и языков запросов для схем и экземпляров процессов.

Последние пятьдесят лет исследователи в области компьютерной науки изучали фундаментальные проблемы процессов и данных в основном по отдельности.

В последние годы данные и процессы исследовались совместно в двух важных областях: научные потоки работ (scientific workflow) и BPM с учетом данных (data-aware BPM) [66]. В центре внимания области научных потоков работ находится обеспечение повторяемости и надежности потоков обработки, включающих крупные наборы научных данных. В 1990-е годы и в первое десятилетие 2000-х годов фундаментальные исследования в этой области помогли базовую инфраструктуру поддержки этих потоков работ, которая обеспечивает возможность систематической регистрации и использования информации о происхождении данных, а также поддержку систем изысканий, которые производящих несколько запусков одного потока работ с изменяющимися конфигурациями [43]. Работа над научными потоками работ может также быть полезна для поддержки процессов анализа больших данных, особенно теперь, когда промышленность начинает создавать потоки аналитической обработки, которые могут повторяться для нескольких приложений и клиентов с относительно небольшими вариациями.

Основная работа над BPM с учетом данных началась в середине первого десятилетия 2000-х годов [28], [47], частично благодаря модели бизнес-процессов IBM «Business Artifacts» [88], в которой целостным образом объединяются понятия данных и процессов. В [46] Дойч (Deutch) и Майло (Milo) приводят обзор и сравнение нескольких наиболее важных ранних моделей и результатов в области управления бизнес-процессами с учетом данных. Один из вариантов модели бизнес-артефактов, который формально определяется на основе логики, а не сетей Петри, обеспечил концептуальную основу недавно принятого стандарта «Модели и нотации управления делами» OMG (OMG Case Management Model and Notation) [81]. Важно отметить, что концепция, основанная на артефактах, позволила сформировать основу для ряда работ, посвященных верификации систем, которые поддерживают процессы, связанные с крупномасштабными данными [35], [47]. Концепция на основе артефактов начинает также использоваться для более единообразного управления взаимодействием бизнес-процессов и унаследованными (legacy) системами данных [105]. Кроме того, стоит заметить, что подход, основанный на артефактах, по основным структурным элементам пересекается с подходом «распределенного реестра» (shared ledger) для поддержки деловых (и индивидуальных) взаимодействий при обмене товарами и услугами; последний подход был изначально встроен в парадигму блокчейн (blockchain) системы Биткойн (Bitcoin) [108].

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

Автоматизация ручных процессов. Большинство бизнес-процессов по-прежнему зависит от значительных трудозатрат. При выполнении внутренних бизнес-операций системы планирования ресурсов предприятия, такие как SAP, автоматически выполняют основную часть работы; это относится, например, к приложениям в областях финансов и управления человеческими ресурсами. Но все еще имеется удивительно много «второстепенных процессов», которые выполняются вручную, например, для обработки новых банковских счетов или оформления вновь нанятых сотрудников. В то же время, и бизнес-процессы, связанные с существенными человеческими решениями, к числу которых относятся, например, сложные продажи или смена поставщика ИТ-услуг, обрабатываются сегодня в основном с привлечением случайно доступных средств (ad hoc) и вручную, с использованием электронных таблиц в качестве предпочтительного инструмента управления потоками работ.

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

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

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

Раскрытие и понимание бизнес-процессов. Область бизнес-аналитики, которая предоставляет методы извлечения и анализа информации о бизнес-операциях, имеет важное значение для бизнеса. Сегодня эта область основывается на большом разнообразии специально разработанных методов, применяемых в автоматическом режиме или вручную [44]; с каждым из этих методов связаны соответствующие расходы и возможность ошибки. Одно из важных направлений в понимании процессов опирается на представление схем процессов и экземпляров процессов в виде данных и использование декларативных языков запросов над этими данными [20]. В более широком смысле, здесь пригодны методы из подобластей PDM управления мультимодельными данными (разд. 3), управления данными и машинного обучения (разд. 6) и неопределенных данных (разд. 4) из-за (соответственно) неоднородности данных о процессах и данных, производимых процессами, важности прогнозирования нежелательных результатов и смягчения их последствий, а также того факта, что хранимая информация о процессах часто бывает неполной.

Удобство использования потоков работ и бизнес-процессов. Операции средних и крупных предприятий очень сложны, и их выполнение отчасти обеспечивается способностью компьютеров управлять огромными объемами данных, поддерживать транзакции и обработку данных на чрезвычайно высоких скоростях. Это вызывает вопросы, связанные с масштабируемым управлением данными (разд. 2). Более того, обеспечение людям возможности понимания большого числа процессов и эффективного управления ими остается иллюзорным, особенно с учетом взаимодействия между процессами, данными (как новыми, и унаследованными), ресурсами, рабочим персоналом и деловыми партнерами.

Перечисленные практические задачи BPM порождают важные исследовательские проблемы, которые нужно решать с использованием подходов, включающих математические и алгоритмические методы и инструменты.

Верификация и статический анализ. Из-за бесконечного пространства состояний, присущего процессам с учетом данных [35], [47], верификация в настоящее время основывается на применении достоверных абстракций, сводящие проблему к классической верификации модели (model checking) с конечным числом состояний. Однако на сегодняшний день этот подход применим только к ограниченному классу приложений, и требуются исследования для разработки более мощных абстракций, позволяющих решать различные задачи статического анализа для реалистичных процессов с учетом данных. Необходимы инкрементальные методы верификации, а также методы, позволяющие использовать модульные стили верификации, поддерживающие подходы «подключи и работай» (plug and play). Такие исследования будет иметь отношение к первым четырем практическим задачам.

Инструменты для проектирования и синтеза. Формальные языки (например, контекстно-свободные) оказали глубокое влияние на теорию компиляторов и языки программирования. Теория зависимостей и нормальные формы оказали глубокое влияние на проектирование реляционных баз данных. Но до сих пор нет надежной инфраструктуры, поддерживающей принципиальное проектирование бизнес-процессов в расширенном контексте данных, ресурсов и рабочего персонала. Важной отправной точкой являются примитивные операции создания и изменения схем процессов с учетом данных; конечной целью является частичный или полный синтез процесса на основе требований, целей и/или нормативных актов. Такие исследования будут иметь отношение к первой, второй, четвертой и шестой практическим задачам.

Модели и семантика представлений, взаимодействий и интероперабельности. Четкое понимание представлений базы данных позволило упростить доступ к данным, совместное использования данных, обмен данными, интеграцию данных, обеспечение конфиденциальности, а также оптимизацию запросов. Аналогичным потенциалом обладает надежная теория представлений для бизнес-процессов с учетом данных. Например, на основе представлений могло бы поддерживаться следующее поколение методов компоновки услуг с учетом данных, включая возможности практической верификации. Отправной точкой для этого исследования может стать инфраструктура сравнения моделей процессов (например, [3]). Такие исследования будут актуальны для решения всех перечисленных практических задач.

Аналитика бизнес-процессов. Новое, более целостное восприятие процессов с учетом данных может помочь заложить новую основу в области бизнес-аналитики. Она может включать новые подходы к инструментированию процессов для упрощения обнаружения данных [80], а также новые стили использования модульности и иерархии как в процессах, так и в аналитике процессов.

Исследования процессов и данных требуют постоянного расширения традиционных подходов как в области баз данных, так и в области управления процессами. Новые подходы могут включать модели для создания (корпоративных) сервисов и поддержки взаимодействия между ними; полуструктурированные и неструктурированные формы описания бизнес-процессов с учетом данных (см. NoSQL); новые абстракции для верификации систем с бесконечным числом состояний и новые способы применения машинного обучения. В более широком плане, может появиться новая фундаментальная модель современного BPM, которая основывается на подходах артефактов и распределенного реестра, но способствует многостороннему пониманию, аналогично тому, как реляционная алгебра и исчисление обеспечивают две точки зрения на запросы данных.

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

8. Данные, связанные с людьми, и этика

Генерируется все больше и больше данных, «связанных с людьми», в частности, в Web и в телефонных приложениях. К этим данным применяется массовый анализ с использованием методов параллелизма и машинного обучения, что приводит к созданию еще больших объемов данных. Порознь или совместно, мы теряем контроль над этими данными. Мы не знаем ответов на многие важные вопросы, например, следующие. Действительно ли мои медицинские данные доступны для получения надлежащего лечения? Должным ли образом они защищены? Может ли частная компания, например, Google или Facebook, повлиять на исход национальных выборов? Следует ли мне доверять содержащейся в Web статистике об уровне преступности в моем районе?

Хотя мы продолжаем с энтузиазмом и удовольствием использовать новые Web-сервисы и телефонные приложения, нас все больше беспокоит преступная деятельность в Web, включая создание и поддержку сайтов расистской, террористической и педофильской направленности; хищение личных данных (identity theft); распространение заведомо ложной информации (cyber-bullying) и компьютерное мошенничество (cyber crime). Мы также ощущаем возрастающее недовольство навязчивой государственной практикой массового электронного наблюдения, распространенного даже в демократических странах, а также вызывающим поведением компаний: назойливый маркетинг, непредвиденная персонализация, непонятные или дискриминационные бизнес-решения.

Влияние на общество технологий больших данных привлекает большое внимание популярной прессы [11], активно изучается политическими деятелями [85] и правоведами [22]. Общепризнано, что эта технология может улучшить жизнь людей, ускорить научные открытия и инновации, а также привести к положительным изменениям в обществе. Но также очевидно, что та же технология может на практике ограничить соблюдение бизнесом правовых и этических норм. И хотя многие из возникающих проблем носят политический и экономический характер, технологические решения должны играть важную роль в том, чтобы наше общество могло извлекать все большие выгоды из больших данных, сохраняя при этом безопасность от рисков.

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

В оставшейся части этого раздела мы представим несколько аспектов этического управления данными.

Ответственный анализ данных. Анализ данных, связанных с человеком, должен быть «ответственным», т.е. должен руководствоваться гуманистическими соображениями, а не просто результативностью или возможностью получения прибыли. Понятие ответственного анализа данных в целом рассматривается в [102], и этому был посвящен недавний семинар в Дагштуле (Dagstuhl) [4]. Теперь мы представим в общих чертах несколько важных аспектов проблемы, особенно те, в которых мы видим возможности участия PDM.

Справедливость. Ответственный анализ данных требует, чтобы и исходные данные, и вычисления были «справедливыми», то есть не предвзятыми [50]. В настоящее время нет единого мнения относительно того, какие классы мер справедливости и какие конкретные формулировки подходят для различных задач анализа данных. Необходима работа, чтобы формализовать меры и понять связи между ними.

Прозрачность и контролируемость. Ответственные методы анализа данных должны быть прозрачными [42], [106], позволяя различным заинтересованным сторонам, таким как конечные пользователи, коммерческие конкуренты, политические деятели и общественность, тщательно изучать процессы сбора и анализа данных, а также интерпретировать результаты. Интересные исследовательские задачи, которые могут быть решены с помощью PDM, включают использование информации о происхождении данных для прояснения практических методов сбора и анализа данных, поддержку извлечения семантики методов и конвейеров анализа данных и предоставление толкований в различных контекстах, включая системы, основанные на знаниях и глубокое обучение.

Многообразие. Технология больших данных представляет собой значительный риск для тех объектов, которые ей игнорируются [75]. Принцип многообразия [7], [49] требует, чтобы не все внимание уделялось некоторому ограниченному набору объектов, действующих лиц или потребностей. Сообщество PDM может внести свой вклад, например, в определение взаимосвязи между многообразием и справедливостью, а также в разработку методов управления балансировкой многоообразия и традиционных показателей точности.

Верификация ответственности данных. Перед сообществом стоит серьезная проблема – разработать технологию верификации, чтобы открыть новую эру ответственных данных (responsible data). Можно представить себе исследования по разработке инструментов, которые помогли бы пользователям понимать результаты анализа данных (например, в Web) и верифицировать их. Можно также представить себе инструменты, которые помогли бы аналитикам, которые, как правило, не являются компьютерными специалистами или специалистами в области статистики, производить анализ ответственных данных «по дизайну» (Analytics by Design).

Качество данных и контроль доступа в Web. В наше время, когда жизнь людей все больше направляется и определяется данными, найденными во Всемирной паутине, определение качества данных в Web является проблемой первостепенной важности. Хотелось бы знать, можно ли доверять разнообразным данным, которые мы находим. Требуются исследования возможностей поддержки контроля доступа в Web. Он может основываться, например, на криптографии, технологии блокчейнов или распределенном управлении доступом [83].

Системы управления персональной информацией. Система управления персональной информацией (Personal Information Management System) – это (облачная) система, которая управляет всей информацией конкретного человека. Возвращая часть контроля над данными этому человеку, такие системы, как правило, лучше защищают конфиденциальность информации, изменяют баланс отношений между человеком и крупными интернет-компаниями в пользу человека и в целом способствуют защите этических ценностей [2].

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

9. Взгляд в будущее

Как показано в предыдущих разделах, теоретический, математически обоснованный подход к изучению проблем управления данными обеспечивает концептуальные основы, глубокое понимание и столь необходимую ясность. В этом отчете описывается представительное, но ни в коем случае не исчерпывающее семейство областей, в которых исследования принципов управления данными (Principles of Data Management, PDM) могут помочь сформировать общий подход к работе с данными, потребность в которой возникает во все более широком спектре прикладных областей.

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

Сообщество PDM также должно продолжать укреплять взаимовыгодные связи с сообществом систем управления данными. Наши совместные конференции (SIGMOD/PODS и EDBT/ICDT) создают уникальную ситуацию в области компьютерной наук, когда теоретики и разработчики систем могут контактировать и представлять друг другу свои лучшие работы. Исследователи PDM должны удвоить свои усилия по активному поиску важных проблем, требующих теоретического подхода. Аналогичным образом, организаторы соответствующих конференций должны продолжать развивать платформу взаимодействия теоретических и системных исследований.

Потребность в точных и надежных подходах к организации все более разнообразных форм управления данными продолжает усиливаться, учитывая основополагающую и преобразующую роль данных в современном обществе, а также постоянное расширение технических, концептуальных и этических проблем управления данными. С этим связано и непрерывное расширение семейства подходов и методов, имеющих отношение к исследованиям в области PDM. Центральное положение управления данными во многих прикладных областях дает возможность исследователям PDM освоить понятия и методы из смежных областей исследований, а исследователям из других областей – использовать понятия и методы PDM. Мы надеемся, что этот отчет может существенно упрочить междисциплинарные исследования, совместно проводимые PDM и соседними теоретическими сообществами, а также сообществами прикладных и системных исследований во многих прикладных областях, опирающихся на данные в той или иной форме.

Список литературы

[1] Daniel Abadi, Rakesh Agrawal, Anastasia Ailamaki, Magdalena Balazinska, Philip A. Bernstein, Michael J. Carey, Surajit Chaudhuri, Jeffrey Dean, AnHai Doan, Michael J. Franklin, Johannes Gehrke, Laura M. Haas, Alon Y. Halevy, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Donald Kossmann, Samuel Madden, Sharad Mehrotra, Tova Milo, Jeffrey F. Naughton, Raghu Ramakrishnan, Volker Markl, Christopher Olston, Beng Chin Ooi, Christopher Ré, Dan Suciu, Michael Stonebraker, Todd Walter, and Jennifer Widom. The Beckman report on database research. Commun. ACM, 59(2):92–99, 2016. doi:10.1145/2845915. Перевод на русский язык: Бекманский отчет об исследованиях в области баз данных.

[2] Serge Abiteboul, Benjamin André, and Daniel Kaplan. Managing your digital life. Commun. ACM, 58(5):32–35, 2015.

[3] Serge Abiteboul, Pierre Bourhis, and Victor Vianu. Comparing workflow specification languages: A matter of views. ACM Trans. Database Syst., 37(2):10, 2012.

[4] Serge Abiteboul, Gerome Miklau, Julia Stoyanovich, and Gerhard Weikum. Data, responsibly (dagstuhl seminar 16291). Dagstuhl Reports, 6(7):42–71, 2016. doi:10.4230/DagRep. 6.7.42.

[5] Foto N. Afrati and Jeffrey D. Ullman. Optimizing multiway joins in a map-reduce environment. IEEE Trans. Knowl. Data Eng., 23(9):1282–1298, 2011.

[6] Alekh Agarwal, Olivier Chapelle, Miroslav Dudik, and John Langford. A reliable effective terascale linear learning system. Journal of Machine Learning Research, 15:1111–1133, 2014.

[7] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. Diversifying search results. In International Conference on Web Search and Web Data Mining (WSDM), pages 5–14. ACM, 2009.

[8] Mert Akdere, Ugur Cetintemel, Matteo Riondato, Eli Upfal, and Stanley B. Zdonik. The case for predictive database systems: Opportunities and challenges. In Conference on Innovative Data Systems Research (CIDR), pages 167–174. www.cidrdb.org, 2011.

[9] Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 9135 of LNCS, pages 56–68. Springer, 2015.

[10] Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-correctness and transferability for conjunctive queries. In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, pages 47–58, 2015. doi: 10.1145/2745754.2745759.

[11] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May 2016. URL: https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing.

[12] Molham Aref, Balder ten Cate, Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn. Design and implementation of the LogicBlox system. In International Conference on Management of Data (SIGMOD), pages 1371–1382. ACM, 2015.

[13] Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014.

[14] Marcelo Arenas, Georg Gottlob, and Andreas Pieris. Expressive languages for querying the semantic web. In Symposium on Principles of Database Systems (PODS), pages 14–26. ACM, 2014.

[15] Marcelo Arenas, Bernardo Cuenca Grau, Evgeny Kharlamov, Sarunas Marciuska, and Dmitriy Zheleznyakov. Faceted search over RDF-based knowledge graphs. J. Web Sem., 37:55–74, 2016.

[16] Marcelo Arenas, Francisco Maturana, Cristian Riveros, and Domagoj Vrgoc. A framework for annotating CSV-like data. Proceedings of the VLDB Endowment, 9(11), 2016.

[17] Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev. A cookbook for temporal conceptual data modelling with description logics. ACM Trans. on Computational Logic, 15(3):25:1–25:50, 2014. doi:10.1145/2629565.

[18] Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM J. Comput., 42(4):1737–1767, 2013.

[19] Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artificial Intelligence, 175(9–10):1620–1654, 2011.

[20] Eran Balan, Tova Milo, and Tal Sterenzy. BP-Ex: a uniform query engine for business process execution traces. In International Conference on Extending Database Technology (EDBT), pages 713–716. ACM, 2010.

[21] Vince Bárány, Balder ten Cate, Benny Kimelfeld, Dan Olteanu, and Zografoula Vagena. Declarative probabilistic programming with datalog. In International Conference on Database Theory (ICDT), volume 48 of LIPIcs, pages 7:1–7:19. Schloss Dagstuhl–LZI, 2016.

[22] Solon Barocas and Andrew D. Selbst. Big data’s disparate impact. California Law Review, 104, 2016. URL: http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2477899.

[23] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Symposium on Principles of Database Systems (PODS), pages 273–284. ACM, 2013.

[24] Michael Benedikt, Wenfei Fan, and Floris Geerts. XPath satisfiability in the presence of DTDs. J. ACM, 55(2), 2008.

[25] Yoshua Bengio, Aaron C. Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013.

[26] Leopoldo Bertossi. Database Repairing and Consistent Query Answering. Morgan&Claypool Publishers, 2011.

[27] Geert Jan Bex, Frank Neven, Thomas Schwentick, and Stijn Vansummeren. Inference of concise regular expressions and DTDs. ACM Trans. Database Syst., 35(2), 2010.

[28] K. Bhattacharya, C.E. Gerede, R. Hull, R. Liu, and J. Su. Towards formal analysis of artifact-centric business process models. In International Conference on Business Process Management (BPM), volume 4714 of LNCS, pages 288–304. Springer, 2007.

[29] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: A study through Disjunctive Datalog, CSP, and MMSNP. ACM Trans. Database Syst., 39(4):33:1–33:44, 2014. doi:10.1145/2661643.

[30] Stefan Borgwardt, Felix Distel, and Rafael Peñaloza. The limits of decidability in fuzzy description logics with general concept inclusions. Artificial Intelligence, 218:23–55, 2015. doi:10.1016/j.artint.2014.09.001.

[31] Michael J. Cafarella, Dan Suciu, and Oren Etzioni. Navigating extracted data with schema discovery. In International Workshop on the Web and Databases (WebDB), 2007.

[32] Zhuhua Cai, Zografoula Vagena, Luis Leopoldo Perez, Subramanian Arumugam, Peter J. Haas, and Christopher M. Jermaine. Simulation of database-valued markov chains using simsql. In International Conference on Management of Data (SIGMOD), pages 637–648. ACM, 2013.

[33] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3):385–429, 2007.

[34] Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Conjunctive query containment and answering under description logics constraints. ACM Trans. on Computational Logic, 9(3):22.1–22.31, 2008.

[35] Diego Calvanese, Giuseppe De Giacomo, and Marco Montali. Foundations of data-aware process analysis: a database theory perspective. In Symposium on Principles of Database Systems (PODS), pages 1–12. ACM, 2013. doi:10.1145/2463664.2467796.

[36] Sejla Cebiric, François Goasdoué, and Ioana Manolescu. Query-oriented summarization of RDF graphs. Proceedings of the VLDB Endowment, 8(12):2012–2015, 2015. URL: http://www.vldb.org/pvldb/vol8/p2012-cebiric.pdf.

[37] Shumo Chu, Magdalena Balazinska, and Dan Suciu. From theory to practice: Efficient join query evaluation in a parallel database system. In International Conference on Management of Data (SIGMOD), pages 63–78. ACM, 2015.

[38] Moustapha Cissé, Nicolas Usunier, Thierry Artieres, and Patrick Gallinari. Robust Bloom filters for large multilabel classification tasks. In Advances in Neural Information Processing Systems (NIPS), 2013.

[39] E. F. Codd. Understanding relations (installment #7). FDT - Bulletin of ACM SIGMOD, 7(3):23–28, 1975.

[40] Wojciech Czerwinski, Wim Martens, Pawel Parys, and Marcin Przybylko. The (almost) complete guide to tree pattern containment. In Symposium on Principles of Database Systems (PODS), pages 117–130. ACM, 2015.

[41] Chris J. Date. Database in Depth – Relational Theory for Practitioners. O’Reilly, 2005.

[42] Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings. PoPETs, 2015(1):92–112, 2015. URL: http://www.degruyter.com/view/j/popets.2015.1.issue-1/popets-2015-0007/popets-2015-0007.xml.

[43] Susan B. Davidson and Juliana Freire. Provenance and scientific workflows: Challenges and opportunities. In International Conference on Management of Data (SIGMOD), pages 1345–1350. ACM, 2008.

[44] Umeshwar Dayal, Malú Castellanos, Alkis Simitsis, and Kevin Wilkinson. Data integration flows for business intelligence. In International Conference on Extending Database Technology (EDBT), pages 1–11. ACM, 2009.

[45] K. Dembczynski, W. Cheng, and E. Hüllermeier. Bayes optimal multilabel classification via probabilistic classifier chains. In International Conference on Machine Learning (ICML), pages 279–286. Omnipress, 2010.

[46] Daniel Deutch and Tova Milo. A quest for beauty and wealth (or, business processes for database researchers). In Symposium on Principles of Database Systems (PODS), pages 1–12. ACM, 2011.

[47] Alin Deutsch, Richard Hull, and Victor Vianu. Automatic verification of database-centric systems. SIGMOD Record, 43(3):5–17, 2014. doi:10.1145/2694428.2694430.

[48] Zlatan Dragisic, Patrick Lambrix, and Eva Blomqvist. Integrating ontology debugging and matching into the eXtreme design methodology. In Workshop on Ontology and Semantic Web Patterns (WOP), volume 1461 of CEUR Workshop Proceedings, 2015. URL: http://ceur-ws.org/Vol-1461/WOP2015_paper_1.pdf[49] Marina Drosou and Evaggelia Pitoura. DisC diversity: result diversification based on dissimilarity and coverage. Proceedings of the VLDB Endowment, 6(1):13–24, 2012. URL: http://www.vldb.org/pvldb/vol6/p13-drosou.pdf.

[50] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science (ITCS), pages 214–226. ACM, 2012.

[51] Thomas Eiter, Thomas Lukasiewicz, and Livia Predoiu. Generalized consistent query answering under existential rules. In International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 359–368. AAAI Press, 2016.

[52] Corinna Elsenbroich, Oliver Kutz, and Ulrike Sattler. A case for abductive reasoning over ontologies. In International Workshop on OWL (OWLED), volume 216 of CEUR Workshop Proceedings, 2006. http://ceur-ws.org/Vol-216/submission_25.pdf.

[53] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Document spanners: A formal approach to information extraction. J. ACM, 62(2):12, 2015.

[54] Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. On distributing symmetric streaming computations. In Symposium on Discrete Algorithms (SODA), pages 710–719. SIAM, 2008.

[55] Enrico Franconi, Paolo Guagliardo, Marco Trevisan, and Sergio Tessaris. Quelo: an ontology-driven query interface. In Workshop on Description Logics (DL), volume 745 of CEUR Workshop Proceedings, 2011. URL: http://ceur-ws.org/Vol-745/paper_58.pdf.

[56] Noah D. Goodman. The principles and practice of probabilistic programming. In Symposium on Principles of Programming Languages (POPL), pages 399–402. ACM, 2013.

[57] Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, and Michael Zakharyaschev. The price of query rewriting in ontology-based data access. Artificial Intelligence, 213:42–59, 2014. doi:10.1016/j.artint.2014.04.004.

[58] Georg Gottlob, Christoph Koch, and Reinhard Pichler. Efficient algorithms for processing XPath queries. ACM Trans. Database Syst., 30(2):444–491, 2005.

[59] Georg Gottlob, Giorgio Orsi, and Andreas Pieris. Query rewriting and optimization for ontological databases. ACM Trans. Database Syst., 39(3):25:1–25:46, 2014. doi:10.1145/2638546.

[60] Georg Gottlob and Pierre Senellart. Schema mapping discovery from data instances. J. ACM, 57(2), 2010. doi:10.1145/1667053.1667055.

[61] Benoît Groz, Tova Milo, and Sudeepa Roy. On the complexity of evaluating order queries with the crowd. IEEE Data Eng. Bull., 38(3):44–58, 2015. URL: http://sites.computer.org/debull/A15sept/p44.pdf.

[62] Peter J. Haas and Joseph M. Hellerstein. Ripple joins for online aggregation. In International Conference on Management of Data (SIGMOD), pages 287–298. ACM, 1999.

[63] Joseph M. Hellerstein, Peter J. Haas, and Helen J. Wang. Online aggregation. In International Conference on Management of Data (SIGMOD), pages 171–182. ACM, 1997.

[64] Martin Hepp. The web of data for e-commerce: Schema.org and GoodRelations for researchers and practitioners. In International Conference on Web Engineering (ICWE), volume 9114 of LNCS, pages 723–727. Springer, 2015. doi:10.1007/978-3-319-19890-3_66.

[65] Xiao Hu and Ke Yi. Towards a worst-case i/o-optimal algorithm for acyclic joins. In Symposium on Principles of Database Systems (PODS). ACM, 2016.

[66] R. Hull and J. Su. NSF Workshop on Data-Centric Workflows, May, 2009. URL: http: //dcw2009.cs.ucsb.edu/report.pdf.

[67] Tomasz Imielinski and Witold Lipski. Incomplete information in relational databases. J. ACM, 31(4):761–791, 1984.

[68] Kalina Jasinska, Krzysztof Dembczynski, , Robert Busa-Fekete, Karlson Pfannschmidt, Timo Klerx, and Eyke Hüllermeier. Extreme F-measure maximization using sparse probability estimates. In International Conference on Machine Learning (ICML). JMLR.org, 2016.

[69] Abhay Kumar Jha and Dan Suciu. Probabilistic databases with MarkoViews. Proceedings of the VLDB Endowment, 5(11):1160–1171, 2012.

[70] Mark Kaminski and Egor V. Kostylev. Beyond well-designed SPARQL. In International Conference on Database Theory (ICDT), volume 48 of LIPIcs, pages 5:1–5:18. Schloss Dagstuhl – LZI, 2016.

[71] Sean Kandel, Andreas Paepcke, Joseph M. Hellerstein, and Jeffrey Heer. Enterprise data analysis and visualization: An interview study. IEEE Trans. Vis. Comput. Graph., 18(12):2917–2926, 2012.

[72] Paraschos Koutris, Paul Beame, and Dan Suciu. Worst-case optimal algorithms for parallel query processing. In International Conference on Database Theory (ICDT), volume 48 of LIPIcs, pages 8:1–8:18. Schloss Dagstuhl – LZI, 2016.

[73] Domenico Lembo, José Mora, Riccardo Rosati, Domenico Fabio Savo, and Evgenij Thorstensen. Mapping analysis in ontology-based data access: Algorithms and complexity. In International Semantic Web Conference (ISWC), volume 9366 of LNCS, pages 217–234. Springer, 2015. doi:10.1007/978-3-319-25007-6_13.

[74] Maurizio Lenzerini. Data integration: a theoretical perspective. In ACM Symposium on Principles of Database Systems (PODS), pages 233–246. ACM, 2002.

[75] Jonas Lerman. Big data and its exclusions. Stanford Law Review Online, 66, 2013.

[76] Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. Wander join: Online aggregation via random walks. In International Conference on Management of Data (SIGMOD), pages 615–629. ACM, 2016.

[77] L. Libkin. SQL’s three-valued logic and certain answers. ACM Trans. Database Syst., 41(1):1, 2016.

[78] Leonid Libkin. Certain answers as objects and knowledge. Artificial Intelligence, 232:1–19, 2016.

[79] W. Lipski. On semantic issues connected with incomplete information databases. ACM Trans. Database Syst., 4(3):262–296, 1979.

[80] Rong Liu, Roman Vaculín, Zhe Shan, Anil Nigam, and Frederick Y. Wu. Business artifactcentric modeling for real-time performance monitoring. In International Conference on Business Process Management (BPM), pages 265–280, 2011.

[81] Mike Marin, Richard Hull, and Roman Vaculín. Data-centric BPM and the emerging Case Management standard: A short survey. In Business Process Management Workshops, pages 24–30, 2012.

[82] Wim Martens, Frank Neven, and Stijn Vansummeren. SCULPT: A schema language for tabular data on the web. In International Conference on World Wide Web (WWW), pages 702–720. ACM, 2015.

[83] Vera Zaychik Moffitt, Julia Stoyanovich, Serge Abiteboul, and Gerome Miklau. Collaborative access control in WebdamLog. In International Conference on Management of Data (SIGMOD), pages 197–211. ACM, 2015.

[84] G. De Francisci Morales and A. Bifet. SAMOA: Scalable advanced massive online analysis. Journal of Machine Learning Research, 16:149–153, 2015.

[85] Cecilia Muñoz, Megan Smith, and DJ Patil. Big data: A report on algorithmic systems, opportunity, and civil rights. Executive Office of the President, The White House, May 2016. URL: https://www.whitehouse.gov/sites/default/files/microsites/ostp/2016_0504_data_discrimination.pdf.

[86] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In Symposium on Principles of Database Systems (PODS), pages 37–48. ACM, 2012.

[87] Nhung Ngo, Magdalena Ortiz, and Mantas Simkus. Closed predicates in description logics: Results on combined complexity. In International Conference on the Principles of Knowledge Representation and Reasoning (KR), pages 237–246. AAAI Press, 2016. URL: http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12906.

[88] A. Nigam and N.S. Caswell. Business Artifacts: An Approach to Operational Specification. IBM Systems Journal, 42(3), 2003.

[89] Dan Olteanu and Jakub Závodný. Size bounds for factorised representations of query results. ACM Trans. Database Syst., 40(1):2, 2015. doi:10.1145/2656335.

[90] Felipe Pezoa, Juan L. Reutter, Fernando Suarez, Martín Ugarte, and Domagoj Vrgoc. Foundations of JSON schema. In International Conference on World Wide Web (WWW), pages 263–273. ACM, 2016.

[91] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. J. on Data Semantics, X:133–173, 2008. doi:10.1007/978-3-540-77688-8_5.

[92] Yashoteja Prabhu and Manik Varma. FastXML: a fast, accurate and stable tree-classifier for extreme multi-label learning. In International Conference on Knowledge Discovery and Data Mining (KDD), pages 263–272. ACM, 2014.

[93] Matteo Riondato, Mert Akdere, Ugur Cetintemel, Stanley B. Zdonik, and Eli Upfal. The vc-dimension of SQL queries and selectivity estimation through sampling. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD), volume 6912 of LNCS, pages 661–676. Springer, 2011.

[94] Ruslan Salakhutdinov and Geoffrey E. Hinton. Semantic hashing. Int. Journal of Approximate Reasoning, 50(7):969–978, 2009.

[95] Akash Das Sarma, Aditya G. Parameswaran, and Jennifer Widom. Towards globally optimal crowdsourcing quality management: The uniform worker setting. In International Conference on Management of Data (SIGMOD), pages 47–62, 2016. doi:10.1145/2882903.

[96] Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. Learning linear regression models over factorized joins. In International Conference on Management of Data (SIGMOD), pages 3–18. ACM, 2016. doi:10.1145/2882903.2882939.

[97] B. Schölkopf and AJ. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2001.

[98] Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan. Declarative information extraction using datalog with embedded extraction predicates. In International Conference on Very Large Data Bases (VLDB), pages 1033–1044. ACM, 2007.

[99] Jaeho Shin, Sen Wu, Feiran Wang, Christopher De Sa, Ce Zhang, and Christopher R?. Incremental knowledge base construction using deepdive. Proceedings of the VLDB Endowment, 8(11):1310–1321, 2015. URL: http://www.vldb.org/pvldb/vol8/p1310-shin.pdf.

[100] Slawek Staworko, Iovka Boneva, José Emilio Labra Gayo, Samuel Hym, Eric G. Prud’hommeaux, and Harold R. Solbrig. Complexity and expressiveness of shex for RDF. In International Conference on Database Theory (ICDT), volume 31 of LIPIcs, pages 195–211. Schloss Dagstuhl – LZI, 2015.

[101] Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell., 64(2-3):209–246, 2012.

[102] Julia Stoyanovich, Serge Abiteboul, and Gerome Miklau. Data responsibly: Fairness, neutrality and transparency in data analysis. In International Conference on Extending Database Technology (EDBT), pages 718–719. OpenProceedings.org, 2016.

[103] D. Suciu, D. Olteanu, C. Re, and C. Koch. Probabilistic Databases. Morgan&Claypool Publishers, 2011.

[104] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

[105] Y. Sun, J. Su, and J. Yang. Universal artifacts. ACM Trans. on Management Information Systems, 7(1), 2016.

[106] Latanya Sweeney. Discrimination in online ad delivery. Commun. ACM, 56(5):44–54, 2013. doi:10.1145/2447976.2447990.

[107] Balder ten Cate, Víctor Dalmau, and Phokion G. Kolaitis. Learning schema mappings. ACM Trans. Database Syst., 38(4):28, 2013.

[108] Florian Tschorsch and Björn Scheuermann. Bitcoin and beyond: A technical survey on decentralized digital currencies. Cryptology ePrint Archive, Report 2015/464, 2015.

[109] Leslie G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103–111, 1990.

[110] LG. Valiant. A theory of the learnable. Commun. ACM, 17(11):1134–1142, 1984.

[111] Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In International Conference on Database Theory (ICDT), pages 96–106. OpenProceedings.org, 2014.

[112] K.Q. Weinberger, A. Dasgupta, J. Langford, A. Smola, and J. Attenberg. Feature hashing for large scale multitask learning. In International Conference on Machine Learning (ICML), pages 1113–1120. ACM, 2009.

1. Т.е. R₁ JOIN R₂ JOIN R₃ … JOIN R_n = (R_i1 JOIN R_i2) JOIN R_i3) JOIN … ) JOIN R_in ^

2. Определение конъюнктивного запроса см. в WIKI. Полный конъюнктивный запрос – это конъюнктивный запрос, не содержащий кванторов (см., например, эту статью). ^

3. Paolo Guagliardo, Leonid Libkin. On the Codd semantics of SQL nulls. Information Systems, vol. 86, 2019, pp. 46-60. ^

4. Carsten Lutz, Inanc Seylan, Frank Wolter. Mixing Open and Closed World Assumption in Ontology-Based Data Access: Non-Uniform Data Complexity. In Proc. of the 2012 International Workshop on Description Logics, DL-2012, Rome, Italy, June 7-10, 2012. ^

5. Timothy L. Hinrichs, Jui-Yi Kao, Michael R. Genesereth. Inconsistency-tolerant Reasoning with Classical Logic and Large Databases. In Proc. of the Eighth Symposium on Abstraction, Reformulation, and Approximation, SARA 2009, Lake Arrowhead, California, USA, 8-10 August 2009. ^

6. Yi Zhou, Yan Zhang. Meta Level Reasoning and Default Reasoning. Lecture Notes in Computer Science book series (LNCS, volume 5293), 2008. ^