Semi-determinism (extended abstract)

ABSTRACT

We investigate under which conditions a non-deterministic query is semi-deterministic, meaning that two different results of the query to a database are isomorphic. We also consider uniform semi-determinism, meaning that all intermediate results of the computation are isomorphic. Semi-determinism is a concept bridging the new trends of non-determinism and object generation in database query languages. Our results concern decidability, both at compile time and at run time; expressibility of the infamous counting queries; and completeness, which is related to the issue of copy elimination raised by Abiteboul and Kannelakis.

REFERENCES

• Abi: S. Abiteboul. Personal communication. 1990.
• ACM90: Proceedings of the Ninth A CM Symposium on Principles of Database Systems. ACM Press, 1990.
• ACM91: Proceedings of the Tenth A CM Symposium on Principles of Database Systems. ACM Press, 1991.
• AK89: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
• AP92: Marc Andries , Jan Paredaens, A Language for Generic Graph-Transformations, Proceedings of the 17th International Workshop, p.63-74, June 17-19, 1991
• ASV90: Serge Abiteboul , Eric Simon , Victor Vianu, Non-deterministic languages to express deterministic transformations, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.218-229, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298575]
• AV90: Serge Abiteboul , Victor Vianu, Procedural languages for database queries and updates, Journal of Computer and System Sciences, v.41 n.2, p.181-229, Oct. 1990 [doi>10.1016/0022-0000(90)90036-K]
• AV91a: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• AV91b: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• CH80: A. Chandra and D. Hard. Computable queries for relational database systems. Journal of Computer and System Sciences, 21(2):156-178, 1980.
• Cha88: Ashok K. Chandra, Theory of database queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-9, March 1988, Austin, Texas, United States [doi>10.1145/308386.308396]
• GPVG90: Marc Gyssens , Jan Paredaens , Dirk van Gucht, A graph-oriented object database model, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.417-424, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298593]
• HS89: R. Hull , J. Su, Untyped sets, invention, and computable queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.347-359, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73755]
• HY90: Richard Hull , Masatoshi Yoshikawa, ILOG: declarative creation and manipulation of object identifiers, Proceedings of the sixteenth international conference on Very large databases, p.455-468, September 1990, Brisbane, Australia
• HY91: Richard Hull , Masatoshi Yoshikawa, On the equivalence of database restructurings involving object identifiers (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.328-340, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113443]
• Imm86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• Kim89: W. Kim, A model of queries for object-oriented databases, Proceedings of the 15th international conference on Very large data bases, p.423-432, July 1989, Amsterdam, The Netherlands
• KLW90: Michael Kifer , Georg Lausen , James Wu, Logical Foundations of Object-Oriented and Frame-Based Languages, University of Mannheim, 1990
• Kup85: Gabriel Mark Kuper, The logical data model: a new approach to database logic, Stanford University, Stanford, CA, 1986
• KV84: Gabriel M. Kuper , Moshe Y. Vardi, A new approach to database logic, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588026]
• NT89: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• SZ90: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• VdBP91: Jan Van den Bussche , Jan Paredaens, The expressive power structured values in pure OODB's (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.291-299, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113440]
• Zan89: C. Zaniolo. Object identity and inheritance in deductive databases#an evolutionary approach. In W. Kim, J.-M. Nicolas, and S. Nishio, editors, Proceedings 1st International Conference on Deductive and Object- Oriented Databases, pages 2-19. Elsevier Science Publishers, 1989.

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: Data models
      H.2.4 Systems

General Terms:
Languages, Verification