Why not negation by fixpoint?

ABSTRACT

There is a fixpoint semantics for DATALOG programs with negation that is a natural generalization of the standard semantics for DATALOG programs without negation. We show that, unfortunately, several compelling complexity-theoretic obstacles rule out its efficient implementation. As an alternative, we propose Inflationary DATALOG, an efficiently implementable semantics for negation, based on inflationary fixpoints

REFERENCES

• AV88: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• Ac77: Aczel, P An Introduction to Inductive Defimtlons Handbook of Malhematzcal Logzc (J Barwine, ed ), North-Holland, 1977, pp 739-782
• AU79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• ABW86: 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
• AvE82: 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]
• BG82: Blass, A, Gurevlch, Y On the Umque Satlsfiablllty Problem lnformatzon and Control 55 (1982), pp 80-88
• CaH86: J Cai , L Hemachandra, The Boolean hierarchy: hardware over NP, Proc. of the conference on Structure in complexity theory, p.105-124, June 1986, Berkeley, California, United States
• CH82: Chandra, A, Hard, D Structure and Complexity of Relatmnal Querms J Computer and Systems Sctences 25 (1982), pp 99-128
• CH85: Chandra, A, Hard, D Horn Clause Queues and Generahzatmns J Logzc Programmzng, 1985 1, pp 1-15
• Cl78: Clark, K L Negatmn as Fadure Logzc and Data Bases (H A Gallalre, } Mlnkel, eds ), Plenum Press, New York, 1978, pp 293-322
• Da87: Elias Dahlhaus, Skolem normal forms concerning the least fixpoint, Computation theory and logic, Springer-Verlag, London, 1987
• Fa74: Fagln, R Generahzed first-order spectra and polynomial time recognizable sets Complexz~y of Computatzons (R, Karp, ed ), SIAM-AMS Proc 7 (1974), pp 43-73
• GJS76: Garej, M R, Johnson, D S, Stockmeyer, L Some simplified NP-complete gre~ph problems Theor Comp Scz 1 (1976), pp 237-267
• GS86: Gurevlch, Y, Shelah, S Fixed-Point Extensions of First-Order Logic Annals of Pure and 4pphed Log,c 32 (1986), pp 265-280
• Im86: 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]
• Ka87: Jim Kadin, The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses, Cornell University, Ithaca, NY, 1987
• Kar72: Karp, R M Reduclblhtms among combinatorial problems Complemiy of Computer Computatsons (R E Mallet, 3 W Thatcher, eds ), Plenum Press, New York, 1972, pp 85-103
• Ko87: Kolaatls, Ph On the expressive power of strat- ~ed logic programs, preprmt, Stanford University, November 1987
• Mo74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• PY82: Pap~d~m~tnou, C H , Yannaknk~s, M The complexity of facets (and some facets of complexity) J Computer and Systems Sciences 28, 2 (1982), pp 244-259
• PY86: Christos H. Papadimitriou , Mihalis Yannakakis, A note on succinct representations of graphs, Information and Control, v.71 n.3, p.181-185, Dec. 1986 [doi>10.1016/S0019-9958(86)80009-2]
• VG86: Van Gelder, A Negatmn as Failure Using T~ght Denv~tmns for General Logic Programs Proc Third IEEE Symposium on Logzc Programming, pp 127-139
• Va82: 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]
• We85: Gerd Wechsung, On the Boolean closure of NP, Fundamentals of Computation Theory, p.485-493, September 09-13, 1985