Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||Equivalence and normal forms for the restricted and bounded fixpoint in the Nested Algebra.|
|Authors: ||GYSSENS, Marc|
Van Gucht, Dirk
|Issue Date: ||2001|
|Citation: ||Information and computation, 154(1). p. 85-117|
|Abstract: ||The nested model is an extension of the traditional, "flat"
in which relations can also have relation-valued entries. Its
language, the nested algebra, is rather weak, unfortunately, since it
is only a
conservative extension of the traditional, "flat"
relational algebra, and thus can
only express a small fraction of the polynomial-time queries.
Therefore, it was
proposed to extend the nested algebra with a least-fixpoint
construct, but the
resulting language turned out to be too powerful: many inherently
queries could also be expressed. Two polynomial-time restrictions of
least-fixpoint closure of the nested algebra were proposed: the
closure (by Gyssens and Van Gucht) and the bounded fixpoint closure
(by Suciu). Here, we prove two results. First we show that that both
are equivalent in expressive power. The proof technique relies on
encodings of nested relations into flat ones, and on a novel encoding method of nested relations into flat ones.|
|ISI #: ||000166731400003|
|Type: ||Journal Contribution|
|Validation: ||ecoom, 2002|
|Appears in Collections: ||Research publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.