Tie-breaking semantics and structural totality

ABSTRACT

We address the question of when the structure of a Datalog program with negation guarantees the existence of a fixpoint. We propose a semantics of Datalog programs with negation, which we call the tie–breaking semantics. The tie–breaking semantics can be computed in polynomial time, and results in a fix-point whenever the rule–goal graph of the program has no cycle with an odd number of negative edges. We show that, in some well-defined sense, this is the most general fixpoint semantics of negation possible; in particular we show that if a cycle with an odd number of negative edges is present, then the logic program is not structurally total, that is, it has an alphabetic variant which has no fixpoint semantics whatsoever. Determining whether a program is (nonstructurally) total is undecidable.

REFERENCES

• AV: 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]
• ABW: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• AvE: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• CH: A. Chandra, D. Harel "Horn Clause Queries and Generalizations," J. Logic Progr., 2(1), pp. 1-15, 1985.
• Cl: K. L. Clarke "Negation as Failure", in Logic and Databases, H. Galaire and J. Minker, eds., Plenum Press, pp. 239-322, 1978.
• G+: H. Gaifman, H. Mairson, Y. Sagiv, M. Vardi "Undecidable Optimization Problems for Database Logic Programs," Proc. 2nd IEEE LICS, pp. 106- 115, 1987.
• GL: M. Gelfond, V. Lifschitz "The Stable Model Semantics for Logic Programming," Proc. 5th Intl. Conf. on Logic Programming, IEEE, pp. 1070- 1080, 1988.
• KP: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Journal of Computer and System Sciences, v.43 n.1, p.125-144, Aug. 1991 [doi>10.1016/0022-0000(91)90033-2]
• K: Kenneth Kunen, Signed data dependencies in logic programs, Journal of Logic Programming, v.7 n.3, p.231-245, Nov. 1989 [doi>10.1016/0743-1066(89)90022-8]
• PS: C. H. Papadimitriou, M. Sideri "On Finding Extensions of Default Theories," manuscript, September 1991.
• P: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• S: Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• VG+: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]

INDEX TERMS

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

          Nouns: Datalog

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Languages, Theory