On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL

Abstract

We study the problem of maintaining recursively-de ned views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. In particular, we show that the transitive closure cannot be maintained in relational calculus under deletion of edges. We use new proof techniques to show this result. These proof techniques generalize to other languages, for example, to the language for nested relations that also contains a number of aggregate functions. Such a language is considered in this paper as a theoretical reconstruction of SQL. Our proof techniques also generalize to other recursive queries. Consequently, we show that a number of recursive queries cannot be maintained in an SQL-like language. We show that this continues to be true in the presence of certain auxiliary relations. We also relate the complexity of updating transitive closure to that of updating the same-generation query and show that the latter is strictly harder than the former. Then we extend this result to that of updating queries based on context-free sets.

Contributors

Guozhu Dong

Leonid Libkin

Limsoon Wong

Conference

Publication date: September 1995

Publication date (Print): September 1995

Pages: 1-12

Affiliations

Department of Computer Science

University of Melbourne

Parkville, Vic. 3052, Australia

Bell Laboratories

600 Mountain Avenue

Murray Hill, NJ 07974, USA

Institute of Systems Science

Heng Mui Keng Terrace

Singapore 0511

Article

DOI: 10.14236/ewic/DBPL1995.10

Copyright statement: © Guozhu Dong et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Proceedings of the Fifth International Workshop on Database Programming Languages

Conference acronym: DBPL-5

Conference number: 5

Conference location: Gubbio, Umbria, Italy

Conference date: 6-8 September 1995

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: Database Programming Languages

Product

Product Information: 1477-9358BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/DBPL1995.10

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing