Scholarlink

<p>Incremental view maintenance (IVM) has long been a central problem in database theory and practice. Many solutions have been proposed for restricted classes of database languages (such as the relational algebra or Datalog), restricted classes of queries, and restricted classes of database changes. In this paper we give a general, heuristic-free solution to this problem in 4 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a new mathematical definition of IVM using DBSP; (3) we give an algorithm for converting any DBSP program into an incremental program; this algorithm reduces the problem of incrementalizing a complex query to the problem of incrementalizing the primitive operations that compose the query. Finally, (4) we show that practical database query languages, such as SQL and Datalog, can be directly implemented on top of DBSP, using primitives that have efficient incremental implementations. As a consequence, we obtain a general recipe for efficient IVM for essentially arbitrary queries written in all these languages.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

DBSP: automatic incremental view maintenance for rich query languages

  • 期刊论文

  • 发表日期：

    2025年5月8日

查看全文
  • Mihai Budiu,
  • Leonid Ryzhyk,
  • Gerd Zellweger,
  • Ben Pfaff,
  • Lalith Suresh,
  • Simon Kassing,
  • Abhinav Gyawali,
  • Matei Budiu,
  • Tej Chajed,
  • Frank McSherry,
  • Val Tannen

摘要

Incremental view maintenance (IVM) has long been a central problem in database theory and practice. Many solutions have been proposed for restricted classes of database languages (such as the relational algebra or Datalog), restricted classes of queries, and restricted classes of database changes. In this paper we give a general, heuristic-free solution to this problem in 4 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a new mathematical definition of IVM using DBSP; (3) we give an algorithm for converting any DBSP program into an incremental program; this algorithm reduces the problem of incrementalizing a complex query to the problem of incrementalizing the primitive operations that compose the query. Finally, (4) we show that practical database query languages, such as SQL and Datalog, can be directly implemented on top of DBSP, using primitives that have efficient incremental implementations. As a consequence, we obtain a general recipe for efficient IVM for essentially arbitrary queries written in all these languages.