Grant: Discovery Grants Program - Individual
University of Waterloo
$55,000.00
Architectural Principles of Modern Datalog Database Management Systems
FY 2024-25
Summary
Datalog and its modern day extensions have recently gained renewed popularity as their recursive capabilities make them suitable to support several modern day applications, such as graph analytics, machine learning and enhancing large language models with reasoning capabilities. This has resulted in the development of several new commercial and academic Datalog database management systems (DBMSs). The popularity of these applications and the size of the databases over which they run raise significant data management challenges that require rethinking the design and implementation of modern Datalog DBMS. The central research question posed in this proposal is: What are the architectural principles for developing a modern Datalog DBMSs? This proposal focuses on three system components: (i) query processor; (ii) incremental maintenance algorithms; and (iii) storage structures and indices for Datalog systems. As a methodology, I will be basing this research on a new prototype Datalog DBMS that my group will develop and use as the foundation to validate and invalidate different design points in these three areas through extensive experimentation.
For query processor, I plan to study the core recursive join operators that can subsume highly optimized operators of specialized systems, such as graph DBMSs, the principles of parallelizing these operators, and the suitability of modern query processor architectures of vectorized and compiled processors for Datalog.
For incremental maintenance, I will study existing main approaches of traditional Delete Re-derive algorithm, recent differential computation and DBSP technique, which index the
per-operator input-output tuple differences, and an approach based on keeping the provenance of tuple derivations in programs. These approaches have different memory and computational resources. I plan to develop a general theoretical framework that connects these techniques and study their optimality in terms of their resource usages. I further plan to develop new techniques that can flexibly trade off memory and computational resources.
For storage and indices, I will study the suitability of core principles for analytical relational DBMSs, which are based on columnar storage structures, to Datalog. I will then study the suitability of existing intermediate relation representation schemes of vectors, factorized vectors, and general tries for a processor that is optimized for recursive computations. I further plan to study the suitability of write or read-optimized indices to keep the tuple differences generated by differential computation and DBSP techniques.
The successful completion of this research program will lay the foundations of architecting modern Datalog systems whose blueprints will be implemented in an open-source prototype system that will be freely available for the research community.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2024-04781
Name nom
Salihoglu, Semih
Department département
Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2711
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Database management
Research subject fr
Gestion de bases de données
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Architectural Principles of Modern Datalog Database Management Systems
Keywords
datalog; query processing; database management systems; incremental view maintenance; recursive queries; inference; reasoning; query optimization; storage structures; indexes
Application summary
Datalog and its modern day extensions have recently gained renewed popularity as their recursive capabilities make them suitable to support several modern day applications, such as graph analytics, machine learning and enhancing large language models with reasoning capabilities. This has resulted in the development of several new commercial and academic Datalog database management systems (DBMSs). The popularity of these applications and the size of the databases over which they run raise significant data management challenges that require rethinking the design and implementation of modern Datalog DBMS. The central research question posed in this proposal is: What are the architectural principles for developing a modern Datalog DBMSs? This proposal focuses on three system components: (i) query processor; (ii) incremental maintenance algorithms; and (iii) storage structures and indices for Datalog systems. As a methodology, I will be basing this research on a new prototype Datalog DBMS that my group will develop and use as the foundation to validate and invalidate different design points in these three areas through extensive experimentation.
For query processor, I plan to study the core recursive join operators that can subsume highly optimized operators of specialized systems, such as graph DBMSs, the principles of parallelizing these operators, and the suitability of modern query processor architectures of vectorized and compiled processors for Datalog.
For incremental maintenance, I will study existing main approaches of traditional Delete Re-derive algorithm, recent differential computation and DBSP technique, which index the
per-operator input-output tuple differences, and an approach based on keeping the provenance of tuple derivations in programs. These approaches have different memory and computational resources. I plan to develop a general theoretical framework that connects these techniques and study their optimality in terms of their resource usages. I further plan to develop new techniques that can flexibly trade off memory and computational resources.
For storage and indices, I will study the suitability of core principles for analytical relational DBMSs, which are based on columnar storage structures, to Datalog. I will then study the suitability of existing intermediate relation representation schemes of vectors, factorized vectors, and general tries for a processor that is optimized for recursive computations. I further plan to study the suitability of write or read-optimized indices to keep the tuple differences generated by differential computation and DBSP techniques.
The successful completion of this research program will lay the foundations of architecting modern Datalog systems whose blueprints will be implemented in an open-source prototype system that will be freely available for the research community.