Non-deterministic languages to express deterministic transformations

ABSTRACT

The use of non-deterministic database languages is motivated using pragmatic and theoretical considerations. It is shown that non-determinism resolves some difficulties concerning the expressive power of deterministic languages: there are non-deterministic languages expressing low complexity classes of queries/updates, whereas no such deterministic languages exist. Various mechanisms yielding non-determinism are reviewed. The focus is on two closely related families of non-deterministic languages. The first consists of extensions of Datalog with negations in bodies and/or heads of rules, with non-deterministic fixpoint semantics. The second consists of non-deterministic extensions of first-order logic and fixpoint logics, using the witness operator. The ability of the various non-deterministic languages to express deterministic transformation is characterized. In particular, non-deterministic languages expressing exactly the queries/updates computable in polynomial time are exhibited, whereas it is conjectured that no analogous deterministic language exists. The connection between non-deterministic languages and determinism is also explored. Several problems of practical interest are examined, such as checking (statically or dynamically) if a given program is deterministic, detecting coincidence of deterministic and non-deterministic semantics, and verifying termination for non-deterministic programs.

REFERENCES

• AbGra: Abiteboul, S., G. Grahne, Update Semantics for Incomplete Databases, VLDB (1985), 1-12.
• AbHu: Serge Abiteboul , Richard Hull, Data functions, datalog and negation, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.143-153, June 01-03, 1988, Chicago, Illinois, United States
• AbSi: Serge Abiteboul , Eric Simon, Fundamental properties of deterministic and nondeterministic extensions of Datalog, Theoretical Computer Science, v.78 n.1, p.137-158, Jan. 21, 1991
• AbVi1: S. Abiteboul , V. Vianu, Fixpoint extensions of first-order logic and datalog-like languages, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.71-79, June 1989, Pacific Grove, California, United States
• AbVi2: Abiteboul, S., V. Vianu, Datalog extensions for database updates and queries, I.N.R.I.A. Technical Report No.715 (1988). Submitted to J. of Computer and Systems Science.
• Ch: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• ChHar: Chandra, A.K., D. ttarel, Computable Queries for Relational Databases, Journal of Computer and System Sciences 21:2 (1980), 156-178.
• ChVar: Chandra, A., M. Vardi, The Implication Problem for Functional and Inclusion Dependencies is Undecidable, SIAM J. Computing 14,3 (1985), 671-677.
• Fag: Fagin, R., Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, Complezity o/ Computation, ed. tt.Karp, SIAM-AMS Proc. 7 (1974), 43-73.
• GurSh: Gurevich, Y., S. Shelah, Fixed-Point Extensions of First-Order Logic, 26th Symp. on Found. of Comp. Sci. (1985), 346-353.
• ImLi: 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]
• Imm1: 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]
• Imm2: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• deK: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9]
• Le: Leisenring, A.C., Mathematical Logic and Hilbert's e-symbol. Gordon and Breach ed. (1969).
• MaSim: Christophe de Maindreville , Eric Simon, Modelling Non Deterministic Queries and Updates in Deductive Databases, Proceedings of the 14th International Conference on Very Large Data Bases, p.395-406, August 29-September 01, 1988
• NaqTs: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• Sag: Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28696]
• Shm: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• SimMa: E. Simon de Maindreville, Deciding whether a production rule is relational computable, Lecture notes in computer science on ICDT '88, p.205-222, October 1988, Bruges, Belgium
• Ull: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Var: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism

General Terms:
Design, Languages, Management, Performance, Theory, Verification