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

@inproceedings{DBLP:conf/dbpl/DongLW95,
  author    = {Guozhu Dong and
               Leonid Libkin and
               Limsoon Wong},
  editor    = {Paolo Atzeni and
               Val Tannen},
  title     = {On Impossibility of Decremental Recomputation of Recursive Queries
               in Relational Calculus and SQL},
  booktitle = {Database Programming Languages (DBPL-5), Proceedings of the Fifth
               International Workshop on Database Programming Languages, Gubbio,
               Umbria, Italy, 6-8 September 1995},
  publisher = {Springer},
  series    = {Electronic Workshops in Computing},
  year      = {1995},
  isbn      = {3-540-76086-5},
  pages     = {7},
  ee        = {db/conf/dbpl/DongLW95.html},
  crossref  = {DBLP:conf/dbpl/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-5 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[2]

Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX

[3]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[4]

Latha S. Colby: A recursive algebra for nested relations. Inf. Syst. 15(5): 567-582(1990) BibTeX

[5]

Guozhu Dong, Jianwen Su: Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. Inf. Comput. 120(1): 101-106(1995) BibTeX

[6]

Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296 BibTeX

[7]

Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150 BibTeX

[8]

...

[9]

...

[10]

...

[11]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[12]

Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX

[13]

Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166 BibTeX

[14]

Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221 BibTeX

[15]

Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX

Referenced by

1. William Hesse: The Dynamic Complexity of Transitive Closure Is In DynTC⁰. ICDT 2001: 234-247
2. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)
3. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
4. Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238
5. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)