MAGIC: MAnaGing InComplete Data - New Foundations

在我们这个数据驱动的世界里，人们几乎每天都要使用高度复杂的软件系统，我们已经学会了依赖这些系统，但同时也知道它们会产生错误的结果。这些是我们笔记本电脑上的系统，它们为公司的网站提供动力，并使公司和政府办公室保持运转。然而，错误的行为是内置在它们中的，它是多个标准的一部分，很少有人去改变它。这些系统是商业DBMS（数据库管理系统）。我们可以依靠他们，只要他们存储的信息是完整的。在自治环境中，这是一个合理的假设，但如今的数据是由大量用户和应用程序生成的，其不完整性是生活中的一个事实。当不完整性进入画面的那一刻，一切都改变了：意想不到的行为发生了;我们教学生写的查询并给他们满分停止工作，人们对从这些数据中获得的结果失去了信任。更糟糕的是，许多现代数据应用，包括数据集成、数据交换、基于本体的数据访问、数据质量、不一致性管理和许多其他应用，都内置了不完整性，并试图依赖标准技术来处理它。这不可避免地导致可疑的，有时甚至是明显错误的结果。这背后的关键原因是复杂性与正确性的权衡：当前保证正确性的技术带来了巨大的复杂性代价，应用程序在寻找方法，牺牲过程中的正确性。我们的主要目标是结束这种令人遗憾的状态。正确性和效率可以共存，但我们需要为不完全信息领域开发新的基础，并在这些基础上开发一套新的技术，以协调两者。为此，我们需要重新思考该领域的基础;至关重要的是，我们需要理解在正确性保证的情况下回答不完整数据的查询意味着什么。经典理论使用了一个单一的、放之四海而皆准的定义，经过仔细研究，这个定义似乎并不普遍正确。我们有一种方法，可以让我们开发一个正确的理论，并将其应用于标准的数据管理任务及其新的应用程序。使这一方法切实可行至关重要。商业系统专注于有效的评估，牺牲了正确性。我们提供正确答案的解决方案将可在现有系统上实施，以保证其适用性。没有必要为了利用处理不完整信息的新方法而抛弃现有的产品和技术。我们的最初目标是提供解决方案来解决商业数据库管理系统的问题，即展示如何以低且可接受的成本提供正确性保证。我们将这样做的各种查询，远远超出了现在已知的可能性。在那之后，我们将看看应用程序，这将使我们第一次确保对集成和交换数据的非常有表达力的查询的正确性。我们将进一步扩展，无论是在数据模型方面（例如，图形、XML、noSQL数据库）和应用程序（不一致数据、本体）。我们还将研究考虑大量数据的解决方案，并在这些情况下产生近似答案。通过我们开发的工具包，“不完整信息的诅咒”，即，认为不可能同时实现正确性和效率的想法应该成为过去。

In our data-driven world, one can hardly spend a day without using highly complex software systems that we have learned to rely on, but that at the same time are known to produce incorrect results. These are systems we have on our laptops, they power websites of companies, and they keep companies and government offices running. And yet the incorrect behaviour is built into them, it is a part of multiple standards, and very little effort is made to change things.The systems are commercial DBMSs (database management systems). We can rely on them as long as information they store is complete. In an autonomous environment, this is a reasonable assumption, but these days data is generated by a huge number of users and applications, and its incompleteness is a fact of life. The moment incompleteness enters the picture, everything changes: unexpected behaviour occurs; queries that we teach students to write and give them full marks for stop working, and one loses trust in the results one gets from such data. To make matters worse, many modern applications of data, including data integration, data exchange, ontology based data access, data quality, inconsistency management and a host of others, have incompleteness built into them, and try to rely on standard techniques for handling it. This inevitably leads to questionable, or sometimes plain incorrect results. The key reason behind this is the complexity vs correctness tradeoff: current techniques guaranteeing correctness carry a huge complexity price, and applications look for ways around it, sacrificing correctness in the process.Our main goal is to end this sorry state of affairs. Correctness and efficiency can co-exist, but we need to develop new foundations of the field of incomplete information, and a new set of techniques based on these foundations, to reconcile the two.To do so, we need to rethink the very basics of the field; crucially, we need to understand what it means to answer queries over incomplete data with correctness guarantees. The classical theory uses a single one-size-fits-all definition, that, upon a careful examination, does not appear to be universally correct. We have an approach that will let us develop a proper theory of correctness and apply it in standard data management tasks and their new applications as well. It is crucial to make this approach practical. Commercial systems concentrate on efficient evaluation, sacrificing correctness. Our solutions for delivering correct answers will be implementable on top of existing systems, to guarantee their applicability. There will be no need to throw away existing products and techniques to take advantage of new approaches to handling incomplete information. Our initial set of goals is to deliver solutions for fixing problems with commercial DBMSs, namely to show how to provide correctness guarantees at low and acceptable costs. We shall do so for a wide variety of queries, going far beyond what is now known to be possible. After that, we shall look at applications that will let us, for the first time, ensure correctness of very expressive queries over integrated and exchanged data. We shall expand further, both in terms of data models (e.g., graphs, XML, noSQL databases), and applications (inconsistent data, ontologies). We shall also look at solutions that take into account very large amounts of data, and produce approximate answers in those scenarios.With the toolkit we develop, the "curse of incomplete information", i.e., the perceived impossibility of achieving correctness and efficiency simultaneously, should be a thing of the past.