Article

Free access

Sets and negation in a logic data base language (LDL1)

Authors:

R. Ramakrishnan,

S. TsurAuthors Info & Claims

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 21 - 37

https://doi.org/10.1145/28659.28662

Published: 01 June 1987 Publication History

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

References

[1]

K Apt, H Blair, A Walker Towards a Theory of Declara~ve Knowledge, unpubhshed manuscript, 1986

[2]

K Apt, M Van Emden Oontnbutlons to the Theory of Logic Programming', J of the AC~ 29, No 3, 1982

Digital Library

[3]

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

Digital Library

[4]

C Been, R Ramaknshnan On the Power of Magac, to appear m AOM PODS 1987

[5]

A Ohandra, D Harel Horn Clause Quenes and Generahzat~ons, Journal of L~~c ~ng, 1-15, 1985

[6]

K Clark Negatmn as Fadure, m Logm and Databu~, (J Gallatre, J Mmker, eds), Plenum Press, 1978

[7]

M Flmng A Knpke-Kleene Semantics for Logic Programs, Jouraal at L~c Pmgranmm~ 4, 295-312, 1985

[8]

A Van Gelder Negation as Failure Using Tight Denvataons for General Logic Programs, unpubhshed manuscnpt

[9]

R Kowalskl, M Van Emden The Semantics of Predicate Logm m a Programming Language, J of the ACIM: 23, No 4, Oct 1976

Digital Library

[10]

G M Kuper Logm Programming With Sets, XP/7 52 Workshop on Database Theory, Umver- 8lt~ of Texas, Ausian, 1986

[11]

J Lloyd Founda~ons of Logic Programming, Spnnger-Verlag, 1984

Digital Library

[12]

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, 1986

[13]

A Tarsh A La~t~ce-Theoretmal Flxpomt Theorem and l~s Apphcataons', Padfi~ J Math 5, 1955

[14]

S Tsur, and C Zanmlo "LDL Rev 0", MOC Techmcal Report, DB-150-85, 1986

[15]

S Tsur, aad C Zanmlo "LDL A Logae-lhsed Da~a, Language", Proc 12th Int Conf on very Laxge D~abases, Kyoto, Japaa, 1986

Digital Library

[16]

C Zanmlo The Repreaentalaon and Deductave Retrieval of Complex Objects", Proc 11th Int Conf Very Large Databases, Stockholm, 1985

[17]

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

Digital Library

[18]

G M Kuper Logic Programming With Sets, XP/ff 52 Workshop on Database Theory, Umverslty of Texas, Austin, 1986

[19]

J Lloyd Foundations of Logm Programming, Sprmger-Veflag 1984

Digital Library

[20]

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, 1986

[21]

O Shmueh, S Naqvl Set Grouping and Layering m IIorn Clause Programs, unpubhshed manuscript

[22]

A T, wskl A Lattice-Theoretical Ftxpomt Theorem and its Apphc,ttlons", Pacafie J Math 5, 1955

[23]

S Tsur, and C Zanlolo "LDL Rev 0", MCC Technical Report, DB-150-85, 1986

[24]

S Tsur, and C Zalllolo "LDL A Logic-Based Dat~Language', Proc 12th Int Conf on very Large Databases, Kyoto, Japan, 1986

Digital Library

[25]

C Zaniolo The Representation and Deductave Retrieval of Complex ObJects", Proc llth Int Conf Very Large Databases, Stockholm, 1985

[26]

J D Ullman Implementation of Log3cal Query Languages for Databases, TODS, Vol 10, Nix 3, pix 289-321, 1985

Digital Library

Cited By

INTERLANDI MTANCA L(2018)A datalog-based computational model for coordination-free, data-parallel systemsTheory and Practice of Logic Programming10.1017/S147106841800042X18:5-6(874-927)Online publication date: 5-Sep-2018
https://doi.org/10.1017/S147106841800042X
Zhou YGrau BNenov YKaminski MHorrocks I(2015)PAGOdAJournal of Artificial Intelligence Research10.5555/2910557.291056654:1(309-367)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.5555/2910557.2910566
Hibti MLegeard BLombardi H(2011)Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement finiRAIRO - Theoretical Informatics and Applications10.1051/ita/199731030205131:3(205-236)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1997310302051
Show More Cited By

Recommendations

Guarded negation
ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

June 1987

363 pages

ISBN:0897912233

DOI:10.1145/28659

Editor:
Moshe Y. Vardi

Copyright © 1987 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS '87

Sponsor:

PODS '87: Principles of database systems

March 23 - 25, 1987

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

96
Total Citations
View Citations
432
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)3

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

INTERLANDI MTANCA L(2018)A datalog-based computational model for coordination-free, data-parallel systemsTheory and Practice of Logic Programming10.1017/S147106841800042X18:5-6(874-927)Online publication date: 5-Sep-2018
https://doi.org/10.1017/S147106841800042X
Zhou YGrau BNenov YKaminski MHorrocks I(2015)PAGOdAJournal of Artificial Intelligence Research10.5555/2910557.291056654:1(309-367)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.5555/2910557.2910566
Hibti MLegeard BLombardi H(2011)Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement finiRAIRO - Theoretical Informatics and Applications10.1051/ita/199731030205131:3(205-236)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1997310302051
Wang QSchewe KFekete ALin X(2008)A typed higher-order calculus for querying XML databasesProceedings of the nineteenth conference on Australasian database - Volume 7510.5555/1378307.1378328(115-125)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1378307.1378328
Liu HYu JLiang W(2008)Safety, domain independence and translation of complex value database queriesInformation Sciences: an International Journal10.1016/j.ins.2008.02.005178:12(2507-2533)Online publication date: 20-Jun-2008
https://dl.acm.org/doi/10.1016/j.ins.2008.02.005
Tovar EVidal M(2008)Magic Rewritings for Efficiently Processing Reactivity on Web OntologiesProceedings of the OTM 2008 Confederated International Conferences, CoopIS, DOA, GADA, IS, and ODBASE 2008. Part II on On the Move to Meaningful Internet Systems10.1007/978-3-540-88873-4_29(1338-1354)Online publication date: 9-Nov-2008
https://dl.acm.org/doi/10.1007/978-3-540-88873-4_29
Takagi TSuzuki TGoto SUshijima K(2007)Evaluation of a deductive database system for CAD applicationsSystems and Computers in Japan10.1002/scj.469023130223:13(15-27)Online publication date: 21-Mar-2007
https://doi.org/10.1002/scj.4690231302
Liu HYu J(2005)Algebraic equivalences of nested relational operatorsInformation Systems10.1016/j.is.2003.12.00130:3(167-204)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.is.2003.12.001
Zhang R(2005)Computing infinite relations using finite expressions: A new approach to the safety issue in relational databasesComputing and Combinatorics10.1007/BFb0030823(91-100)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030823
Osorio MJayaraman B(2005)Aggregation and well-founded semantics+Non-Monotonic Extensions of Logic Programming10.1007/BFb0023802(71-90)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0023802
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents