Expressibility of Bounded-Arity Fixed-Point Query Hierarchies.

Pratul Dublish, S. N. Maheshwari: Expressibility of Bounded-Arity Fixed-Point Query Hierarchies. PODS 1989: 324-335

@inproceedings{DBLP:conf/pods/DublishM89,
  author    = {Pratul Dublish and
               S. N. Maheshwari},
  title     = {Expressibility of Bounded-Arity Fixed-Point Query Hierarchies},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {324-335},
  ee        = {http://doi.acm.org/10.1145/73721.73753, db/conf/pods/DublishM89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The expressibility of bounded-arity query hierarchies resulting from the extension of first- order logic by the least fixed-point, inductive fixed-point and generalized fixed-point operators is studied. In each case, it is shown that increasing the arity of the predicate variable from k to k+1 always allows some more k-ary predicates to be expressed. Further, k-ary inductive fixed-points are shown to be more expressive than k-ary least fixed-points and k-ary generalized fixed-points are shown to be more expressive than k-ary inductive fixed-points.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents

Online Edition: ACM Digital Library

References

[AU]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[Be]: ...
[CH]: Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982)
[Du]: ...
[Eh]: ...
[En]: ...
[Fr]: ...
[Gu]: ...
[GS]: Yuri Gurevich, Saharon Shelah: Fixed-Point Extensions of First-Order Logic. FOCS 1985: 346-353
[Im1]: Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981)
[Im2]: Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)