Grants and Contributions:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

Database has been a cornerstone in the data-driven digital age. Events and observations in the world generate large volumes of data which are safely stored in databases and efficiently analyzed by database queries. The results of the analysis further support decision making of a wide range of software systems, e.g. payroll and financial management, control systems, and operational research. These decisions must respect safety and correctness constraints. Examples of constraints are everywhere: payroll deadlines, maximal power capacity, server availability etc.. While the database technology excels at data storage and analytics, presently it fails to provide the same level of effectiveness for the management and verification of constraints. Currently, to fill this gap, application specific programs need to be manually developed by programmers. But such efforts are costly and highly error-prone. Constraint violations as the results of human errors and buggy software are frequently observed in different sectors of the industry and governments. This proposed research program is aimed to rectify the situation by extending the role of the database to include the management of constraints.

The applicant’s objective is to extend the data model and the query language of databases to include logical constraints as first-class citizens just like data. This allows a well-defined declarative semantics to store and manage constraints and data in a unified framework. Building on top of state-of-art A.I. constraint satisfaction algorithms, the research program is to augment existing database technology to actively reason about decisions in the presence of constraints and data, thus alleviating the need for secondary safety-maintenance software. Such database engines can verify and actively synthesize data-driven decisions that are safe, correct and optimal.

The proposed research program contributes to the theory and system design of future databases. Towards database theory, we will be studying (1) new constraint query operators and their properties, (2) new algorithms to manage mutually conflicting, incomplete and time varying constraints, and (3) distributed algorithms that are capable of processing large collections of constraints at Internet scale. Towards the system design of constraint database engines, we will perform research on (4) integration of constraint solvers with database engines, (5) implementation of highly concurrent constraint solvers, and (6) user interface design and implementation for interactive and crowdsourcing constraint satisfaction and verification.
In summary, the success of the proposed research program will enable databases to manage constraints using a declarative query language. Database engines will help software systems to make safer decisions that are provably correct with respect to the constraints in the database.