C. Beeri
ABSTRACT
In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDL1. We define the notion of a model and show that a negation-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restriction in order to define a deterministic language. These restrictions allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDL1 programs. Finally, we show how the technique of magic sets can be extended to translate LDL1 programs into equivalent programs which can often be executed more efficiently
- ABW86.K Apt, H Blair, A Walker Towards a Theory of Declara~ve Knowledge, unpubhshed manuscript, 1986Google Scholar
- AE82.K Apt, M Van Emden Oontnbutlons to the Theory of Logic Programming', J of the AC~ 29, No 3, 1982 Google ScholarDigital Library
- BMSU86.F Baacllhon, D Mater, Y Saglv, J Ullman Magic Sets and Other Strange Ways to Implement Logm Programs, Pmc of the 5th ACM Conf on P(X)S, Cambridge, 1986 Google ScholarDigital Library
- BR87.C Been, R Ramaknshnan On the Power of Magac, to appear m AOM PODS 1987Google Scholar
- CH85.A Ohandra, D Harel Horn Clause Quenes and Generahzat~ons, Journal of L~~c ~ng, 1-15, 1985Google Scholar
- CLAR78.K Clark Negatmn as Fadure, m Logm and Databu~, (J Gallatre, J Mmker, eds), Plenum Press, 1978Google Scholar
- FITT85.M Flmng A Knpke-Kleene Semantics for Logic Programs, Jouraal at L~c Pmgranmm~ 4, 295-312, 1985Google Scholar
- GELD86.A Van Gelder Negation as Failure Using Tight Denvataons for General Logic Programs, unpubhshed manuscnptGoogle Scholar
- KE76.R Kowalskl, M Van Emden The Semantics of Predicate Logm m a Programming Language, J of the ACIM: 23, No 4, Oct 1976 Google ScholarDigital Library
- KUPE86.G M Kuper Logm Programming With Sets, XP/7 52 Workshop on Database Theory, Umver- 8lt~ of Texas, Ausian, 1986Google Scholar
- LLOY84.J Lloyd Founda~ons of Logic Programming, Spnnger-Verlag, 1984 Google ScholarDigital Library
- NAQV86.S Naqvl A Logic for Negation m Database System", MC~ Techmcal Report Also m Pmc of the Workshop on Logic and Databases, Washington, D C, 1986Google Scholar
- TARS55.A Tarsh A La~t~ce-Theoretmal Flxpomt Theorem and l~s Apphcataons', Padfi~ J Math 5, 1955Google Scholar
- TZ85.S Tsur, and C Zanmlo "LDL Rev 0", MOC Techmcal Report, DB-150-85, 1986Google Scholar
- TZ86.S Tsur, aad C Zanmlo "LDL A Logae-lhsed Da~a, Language", Proc 12th Int Conf on very Laxge D~abases, Kyoto, Japaa, 1986 Google ScholarDigital Library
- ZANI85.C Zanmlo The Repreaentalaon and Deductave Retrieval of Complex Objects", Proc 11th Int Conf Very Large Databases, Stockholm, 1985Google Scholar
- KE76.R Kowalsh, M Van Emden The Semantics of Predma~e Lo~pc as a Programming Language, J of the ACM 23, No 4, Oct 1976 Google ScholarDigital Library
- KUPE86.G M Kuper Logic Programming With Sets, XP/ff 52 Workshop on Database Theory, Umverslty of Texas, Austin, 1986Google Scholar
- LLOY84.J Lloyd Foundations of Logm Programming, Sprmger-Veflag 1984 Google ScholarDigital Library
- NAQV86.S Naqvl A I,oglc for Negation in Database System", MCC'Fechnl(al RcpoIt Also m Proc of the Workshop on Logw and Databases, Washington, D C, 1986Google Scholar
- SN86.O Shmueh, S Naqvl Set Grouping and Layering m IIorn Clause Programs, unpubhshed manuscriptGoogle Scholar
- TARS55.A T, wskl A Lattice-Theoretical Ftxpomt Theorem and its Apphc,ttlons", Pacafie J Math 5, 1955Google Scholar
- TZ85.S Tsur, and C Zanlolo "LDL Rev 0", MCC Technical Report, DB-150-85, 1986Google Scholar
- TZ86.S Tsur, and C Zalllolo "LDL A Logic-Based Dat~Language', Proc 12th Int Conf on very Large Databases, Kyoto, Japan, 1986 Google ScholarDigital Library
- ZANI85.C Zaniolo The Representation and Deductave Retrieval of Complex ObJects", Proc llth Int Conf Very Large Databases, Stockholm, 1985Google Scholar
- ULLM86.J D Ullman Implementation of Log3cal Query Languages for Databases, TODS, Vol 10, Nix 3, pix 289-321, 1985 Google ScholarDigital Library
Index Terms
- Sets and negation in a logic data base language (LDL1)
Recommendations
Guarded negation
ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part IIWe consider restrictions of first-order logic and of fixpoint logic in which all occurrences of negation are required to be guarded by an atomic predicate. In terms of expressive power, the logics in question, called GNFO and GNFP, extend the guarded ...
Negation and Constraint Logic Programming
Almost all constraint logic programming systems include negation, yet nowhere has a sound operational model for negation in CLP been discussed. The SLDNF approach of only allowing ground negative subgoals to execute is very restrictive in constraint ...
Classical Negation and Expansions of Belnap---Dunn Logic
We investigate the notion of classical negation from a non-classical perspective. In particular, one aim is to determine what classical negation amounts to in a paracomplete and paraconsistent four-valued setting. We first give a general semantic ...
Comments