Digital Review

Review - On Instance-Completeness for Database Query Languages involving Object Creation.

Victor Vianu: Review - On Instance-Completeness for Database Query Languages involving Object Creation. ACM SIGMOD Digital Review 2: (2000) BibTeX


New developments in systems occasionally hold immediate theoretical appeal, and other times they seem hopelessly idiosycratic and unsuited for formal treatment. At the time when object-oriented database systems came into fashion, there wasn't much theory around them, and it was not clear that there would be. This paper was a revelation to me: it showed beyond any doubt that the there is deep, original theory to be done about object-orientation. The paper looks at object-oriented languages that can produce new objects in results to queries or updates. One might expect this would be a minor variation over classical languages, and that conventional wisdom would hold with small adjustments. For example, one might think that languages which are complete in the classical relational sense (i.e. they can express every computable query whose answer is made up of values from the input) would remain complete when augmented with an objects creation mechanism. A while earlier, it had already been pointed out by Abiteboul and Kanellakis that this is not the case, using a simple but ingenious example. In this paper, Andries and Paredaens take the issue further: they charcterizes precisely when an input-output pair where the output involves new objects can be obtained in specific languages. The characterization is stunningly elegant and powerful. Basically, it requires that automorphisms of the input be extensible to automorphisms of the output, including the new objects. This is an example of a simple result with a hard proof (the proof uses rather sophisticated techniques from group theory). The characterization provides a powerful tool for understanding the ability of object-oriented languages to define answers with new objects. More broadly, it clearly showed that there are fundamental differences between object-oriented languages and classical relational ones.

Copyright © 2000 by the author(s). Review published with permission.


Marc Andries, Jan Paredaens: On Instance-Completeness for Database Query Languages involving Object Creation. J. Comput. Syst. Sci. 52(2): 357-373(1996) BibTeX
Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Digital Review: Copyright © by ACM (,
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:57:29 2009