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
Review
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.
References
- [1]
- Marc Andries, Jan Paredaens:
On Instance-Completeness for Database Query Languages involving Object Creation.
J. Comput. Syst. Sci. 52(2): 357-373(1996) BibTeX
BibTeX
Digital Review - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
Digital Review: Copyright © by ACM (info@acm.org),
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:57:29 2009