Semantic representations and query languages for or-sets

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.

REFERENCES

• 1: S. Abiteboul, C. Beeri, On the power of languages for the manipulation of complex objects, In Proc. of Int. Workshop on Theory and Applications of Nested Relations and Complex Objects, Darmstadt, 1988.
• 2: S. Abiteboul , P. C. Fischer , H. -J. Schek, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 3: Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.9-19, April 1992, Nafplion, Greece
• 4: Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
• 5: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• 6: O. P. Buneman , S. B. Davidson , A. Watters, A semantics for complex objects and approximate answers, Journal of Computer and System Sciences, v.43 n.1, p.170-218, Aug. 1991 [doi>10.1016/0022-0000(91)90035-4]
• 7: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
• 8: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 11: Reinhold Heckmann, Lower and upper power domain constructions commute on all cpos, Information Processing Letters, v.40 n.1, p.7-11, Oct. 11, 1991 [doi>10.1016/S0020-0190(05)80003-1]
• 12: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 13: Tomasz Imielinski , Shamim Naqvi , Kumar Vadaparty, Incomplete object—a data model for design and planning applications, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.288-297, May 29-31, 1991, Denver, Colorado, United States
• 14: T. Imielinski, S. Naqvi, and K. Vadaparty. Querying design and planning databases. In LNCS 566: Deductive and Object Oriented Databases, pages 524-545, Berlin, 1991. Springer-Verlag.
• 15: Leonid Libkin, A relational algebra for complex objects based on partial information, Proceedings of the 3rd symposium on Mathematical fundamentals of database and knowledge base systems, p.29-43, May 1991, Rostock, Germany
• 16: L. Libkin, An elementary proof that upper and lower powerdomain constructions commute, Bulletin of the EATCS, 48 (1992), 175- 177.
• 17: L. Libkin, L. Wong, Semantic representations and query languages for or-sets, Technical Report MS-CIS-92-88, University of Pennsylvania, 1992.
• 18: Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
• 19: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 20: B. Rounds, Situation-theoretic aspects of databases, In Proc. Conf. on Situation Theory and Applications, CSLI vol. 26, 1991, pages 229-256.
• 21: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Design, Languages, Theory