Aggregates in datalog
Abstract/Contents
- Abstract
- Datalog is a logic programming language that is often used as a query language for deductive databases, with many practical applications, ranging from declarative networking to data integration to computational law. While Datalog is highly expressive and easy to understand, there is no agreed-upon way of representing aggregate queries, i.e., queries that provide summary values of sets of data. Over the years, Datalog has been extended in various ways to address this deficiency. Unfortunately, these extensions are either not expressive enough or do not deal with incremental updates or folding of aggregate queries in a general setting. We present a Datalog extension, called DatalogA, that provides a representation for aggregates while eliminating the above weaknesses. We show that DatalogA is more expressive than prior aggregate extensions of Datalog. Keys to the increased expressivity in DatalogA are the inclusion of lists and sets as first class citizens in the language, a general aggregation operator that allows us to characterize sets of objects with specified properties, and the use of Prolog-like rules to define aggregation functions on these sets (e.g., count, sum). We present an algorithm to incrementally maintain materialized DatalogA views in response to changes to the underlying data. We show that the taken to incrementally maintain DatalogA views can be decreased by materializing additional views and tracking the number of tuple derivations. We also present an algorithm to fold DatalogA queries using views. We characterize two classes of query folding problems for which our algorithm generates maximally contained query answers.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Mohapatra, Abhijeet |
|---|---|
| Degree supervisor | Genesereth, Michael R, 1948- |
| Thesis advisor | Genesereth, Michael R, 1948- |
| Thesis advisor | Ré, Christopher |
| Thesis advisor | Waldinger, Richard |
| Degree committee member | Ré, Christopher |
| Degree committee member | Waldinger, Richard |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Abhijeet Mohapatra. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Abhijeet Mohapatra
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...