ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Semantic Representations and Query Languages for Or-sets.

Leonid Libkin, Limsoon Wong: Semantic Representations and Query Languages for Or-sets. PODS 1993: 37-48
@inproceedings{DBLP:conf/pods/LibkinW93,
  author    = {Leonid Libkin and
               Limsoon Wong},
  title     = {Semantic Representations and Query Languages for Or-sets},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {37-48},
  ee        = {http://doi.acm.org/10.1145/153850.153854, db/conf/pods/LibkinW93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Or-sets were introduced by Imielinski, Naqvi and Vadaparty for dealing with limited forms of disjunctive information in database queries. Independently, Rounds used a similar notion for representing disjunctive and conjunctive information in the context of situation theory. In this paper we formulate a query language with adequate expressive power for or-sets. Using the notion of normalization of or-sets, queries at the "structural" and "conceptual" levels are distinguished. Losslessness of normalization is established for a large class of queries. We have obtained upper bounds for the cost of normalization. An approach related to that of Rounds is used to provide semantics for or-sets.

Copyright © 1993 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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1063 KB]

References

[1]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[2]
...
[3]
Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX
[4]
Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX
[5]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX
[6]
Peter Buneman, Susan B. Davidson, Aaron Watters: A Semantics for Complex Objects and Approximate Answers. J. Comput. Syst. Sci. 43(1): 170-218(1991) BibTeX
[7]
Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991) BibTeX
[8]
...
[9]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[10]
...
[11]
Reinhold Heckmann: Lower and Upper Power Domain Constructions Commute on all Cpos. Inf. Process. Lett. 40(1): 7-11(1991) BibTeX
[12]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[13]
Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Incomplete Objects - A Data Model for Design and Planning Applications. SIGMOD Conference 1991: 288-297 BibTeX
[14]
Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Querying Design and Planning Databases. DOOD 1991: 524-545 BibTeX
[15]
Leonid Libkin: A Relational Algebra for Complex Objects Based on Partial Information. MFDBS 1991: 29-43 BibTeX
[16]
...
[17]
...
[18]
Eugenio Moggi: Notions of Computation and Monads. Inf. Comput. 93(1): 55-92(1991) BibTeX
[19]
Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
[20]
...
[21]
...

Referenced by

  1. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  2. Catriel Beeri, Tova Milo, Paula Ta-Shma: Towards a Language for the Fully Generic Queries. DBPL 1997: 239-259
  3. Kumar V. Vadaparty, Shamim A. Naqvi: Using Constraints for Efficient Query Processing in Nondeterministic Databases. IEEE Trans. Knowl. Data Eng. 7(6): 850-864(1995)
  4. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
  5. Leonid Libkin: Normalizing Incomplete Databases. PODS 1995: 219-230
  6. Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424
  7. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  8. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  9. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:07 2009