+1 Recommend
1 collections
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

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


      , ,

      Proceedings of the Fifth International Workshop on Database Programming Languages (DBPL-5)

      Database Programming Languages

      6-8 September 1995

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          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.

          Related collections

          Author and article information

          September 1995
          September 1995
          : 1-12
          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
          © Guozhu Dong et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

          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/

          Proceedings of the Fifth International Workshop on Database Programming Languages
          Gubbio, Umbria, Italy
          6-8 September 1995
          Electronic Workshops in Computing (eWiC)
          Database Programming Languages
          Product Information: 1477-9358BCS Learning & Development
          Self URI (journal page): https://ewic.bcs.org/
          Electronic Workshops in Computing


          Comment on this article