Maintaining Triangle Queries under Updates
RelationalAI
02 January 2020
less than a minute read
Maintaining Triangle Queries under Updates
We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations.
Authors: Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang. 2020.
In ACM Transactions on Database Systems (TODS ‘20). Vol. 45, No. 3, Article 11. (Best of ICDT 2019 and Regular Papers).
We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations. We introduce an approach called IVM that exhibits a trade-off between the update time, the space, and the delay for the enumeration of the query result, such that the update time ranges from the square root to linear in the database size while the delay ranges from constant to linear time. IVM achieves Pareto worst-case optimality in the update-delay space conditioned on the Online Matrix-Vector Multiplication conjecture. It is strongly Pareto optimal for the triangle queries with zero or three free variables and weakly Pareto optimal for the triangle queries with one or two free variables.
Related Posts
Deep Learning with Relations, NeurIPS 2021
Molham shares some history of relational databases, trends in modern cloud-native database systems, and the innovations pioneered at RelationalAI to bring deep learning with relations from idea to reality.
Read More
AI workloads inside databases, NeurIPS 2021
This incredible panel of experts gathered to discuss the current state of AI and machine learning workloads inside databases. The panel discussed new techniques, technologies, and recent papers that progress our understanding of what is possible. Q&A among the panel and from the audience concludes this deep and wide ranging conversation.
Read More
Machine Learning through Database Glasses, NeurIPS 2021
This talk explores several techniques to improve the runtime performance of machine learning by taking advantage of the underlying structure of relational data. While most data scientists use relational data in their work, the data science tooling that works with relational data is quite lacking today. Let’s explore these new techniques and see how we can drastically improve machine learning through a database-oriented lens.
Read More