On the Power of Rule-Based Languages with Sets.

Kumar V. Vadaparty: On the Power of Rule-Based Languages with Sets. PODS 1991: 26-36

@inproceedings{DBLP:conf/pods/Vadaparty91,
  author    = {Kumar V. Vadaparty},
  title     = {On the Power of Rule-Based Languages with Sets},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {26-36},
  ee        = {http://doi.acm.org/10.1145/113413.113416, db/conf/pods/Vadaparty91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

This paper studies the data complexity and expressibility of COL and the "finite versions" of LDL, ELPS and IQL. We distinguish between different "levels" of each of these languages and show that the data complexity of each k-level language is complete for the k'th level of the hyper-exponential time. We also show that with a given domain order, each k-level language can express every relational generic query in the k'th level of the hyper-exponential time, while without an order, it can express every relational generic query in the (k-1)-level. We also remark on the need for negation by the finite version of ELPS for the expressibility results. The techniques used to prove these results yield some interesting by-products: (i) Grouping rule can encode some non-monotonic queries that can not be encoded by several other non-monotonic query languages, thus making it a powerful set-construct (ii) Positive ELPS can group ordered sets, thus showing a strict increase in its expressive power when augmented with domain order.

Copyright © 1991 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/...

BibTeX

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 784 KB]

Journal Version

Kumar V. Vadaparty: On the Power of Rule-Based Query Languages for Nested Data Models. J. Log. Program. 21(3): 155-175(1994) BibTeX

References

[AB87]: ...
[AK89]: Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
[AK90]: Serge Abiteboul, Paris C. Kanellakis: Database Theory Column: Query Languages for Complex Object Databases. SIGACT News 21(3): 9-18(1990) BibTeX
[AG88]: Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. EDBT 1988: 271-293 BibTeX
[BK86]: François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX
[BNST90]: Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. J. Log. Program. 10(1/2/3&4): 181-232(1991) BibTeX
[Chandra88]: Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX
[CH82]: Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[GvG88]: Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232 BibTeX
[H87]: ...
[HS90]: Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
[HY90]: Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468 BibTeX
[J82]: Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX
[Ku90]: Gabriel M. Kuper: Logic Programming with Sets. J. Comput. Syst. Sci. 41(1): 44-64(1990) BibTeX
[KV84]: Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX
[KV88]: Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280 BibTeX
[Vardi82]: Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

Kumar V. Vadaparty, Y. Alp Aslandogan, Gultekin Özsoyoglu: Towards a Unified Visual Database Access. SIGMOD Conference 1993: 357-366
Natraj Arni, Sergio Greco, Domenico Saccà: Set-Term Matching in Logic Programming. ICDT 1992: 436-449

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]