Complexity and expressive power of logic programming
ACM Computing SurveysPublished 1 September 2001
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Андрей Воронков
Citations753
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This article surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and datalog, but we also mention general logic programming with function symbols. Next to classical results on plain logic programming (pure Horn clause programs), more recent results on various important extensions of logic programming are surveyed. These include logic programming with different forms of negation, disjunctive logic programming, logic programming with equality, and constraint logic programming.
Keywords
Computer Science
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Journal of the ACMA Machine-Oriented Logic Based on the Resolution Principle
3,885 Citations1965John A. Robinson
The paper concludes with a discussion of several principles which are applicable to the design of efficient proof-procedures employing resolution as the basle logical process.
The stable model semantics for logic programming
3,405 Citations1988Michael Gelfond, Vladimir Lifschitz
A new de larative semanti for logistic programs with negation is proposed, quite simple and at the same time simple to understand.
Foundations of databases
3,400 Citations1994Serge Abiteboul, Richard Hull +1 more
Choice Reviews OnlinePrinciples of database and knowledge-base systems
2,701 Citations1989
This book goes into the details of database conception and use, it tells you everything on relational databases from theory to the actual used algorithms.
New Generation ComputingClassical negation in logic programs and disjunctive databases
2,313 Citations1991Michael Gelfond, Vladimir Lifschitz
It is shown that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available.
Journal of the ACMThe well-founded semantics for general logic programs
1,670 Citations1991Allen Van Gelder, Kenneth A. Ross +1 more
It is shown that the class of programs possessing a total well-founded model properly includes previously studied classes of "stratified" and "locally stratified" programs, and is compared with other proposals in the literature.
Journal of the ACMThe Semantics of Predicate Logic as a Programming Language
1,463 Citations1976M. H. van Emden, Robert Kowalski
In this paper the operational and fixpoint semantics of predicate logic programs are defined, and the connections with the proof theory and model theory of logic are investigated, and it is concluded that operational semantics is a part ofProof theory and that fixpoint semantic is a special case of model-theoretic semantics.
Journal of the ACMLogical foundations of object-oriented and frame-based languages
1,456 Citations1995Michael Kifer, Georg Lausen +1 more
A novel formalism, called Frame Logic (abbr., F-logic), is proposed, that accounts in a clean and declarative fashion for most of the structural aspects of object-oriented and frame-based languages.
Journal of Computer and System SciencesRelationships between nondeterministic and deterministic tape complexities
1,362 Citations1970Walter J. Savitch
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated and a specific set is produced, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeter microscopic complexity classes from deterministic tape complexity classes, then this is one such set.
The Journal of Logic ProgrammingConstraint logic programming: a survey
1,332 Citations1994Joxan Jaffar, Michael J. Maher
This survey of CLP is to give a systematic description of the major trends in terms of common fundamental concepts and the three main parts cover the theory, implementation issues, and programming for applications.
Optimal implementation of conjunctive queries in relational data bases
1,237 Citations1977Ashok K. Chandra, Philip M. Merlin
It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal.
The complexity of relational query languages (Extended Abstract)
1,189 Citations1982Moshe Y. Vardi
The pattern which will be shown is that the expression complexity of the investigated languages is one exponential higher then their data complexity, and for both types of complexity the authors show completeness in some complexity class.
Springer monographs in mathematicsFinite Model Theory
1,073 Citations1995Heinz-Dieter Ebbinghaus, Jörg Flum
The text presents the main results of descriptive complexity theory, the connection between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds.
The Journal of Logic ProgrammingLinear-time algorithms for testing the satisfiability of propositional horn formulae
1,021 Citations1984William F. Dowling, Jean Gallier
The formulation of the satisfiability problem as a data flow problem appears to be new and suggests the possibility of improving efficiency using parallel processors.
Elsevier eBooksFoundations of Deductive Databases and Logic Programming
973 Citations1988
This book is referred to read because it is an inspiring book to give you more chance to get experiences and also thoughts and this foundations of deductive databases and logic programming.
ACM Transactions on Programming Languages and SystemsAn Efficient Unification Algorithm
772 Citations1982Alberto Martelli, Ugo Montanari
A new unification algorithm, characterized by having the acyclicity test efficiently embedded into it, is derived from the nondeterministic one, and a PASCAL implementation is given.
ParasiteProceedings of the International Symposium
756 Citations2014Dominique A. Vuitton, Laurence Millon +2 more
Surveys in computer scienceLogic Programming and Databases
746 Citations1990Stefano Ceri, Georg Gottlob +1 more
Information and ControlRelational queries computable in polynomial time
648 Citations1986Neil Immerman
The rotary ball valve includes a generally annular seal which is held in place by an edge anchored annular retainer which is oversized for the valve housing and on installation resides in a state of compression.
Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics
607 Citations1994Jan Van Leeuwen
This handbook will provide professionals and students with a comprehensive overview of the main results and developments in this rapidly evolving field of theoretical computer science with a focus on core areas of theoretical computer science as it is practiced today.
Journal of the ACMContributions to the Theory of Logic Programming
586 Citations1982Krzysztof R. Apt, M. H. van Emden
It is shown that nondeterministic flowchart schemata of bounded nondeterminacy are modeled by this special case of Hom clauses, and the connection between finite failure and greatest fixpoint is used to give a semantic characterization of termination, blocking, and nontermination of such flowchart Schemata.
Some algebraic and geometric computations in PSPACE
570 Citations1988John Canny
A PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations is given and it is shown that the existential theory of the real numbers can be decided in PSPACE.
Elsevier eBooksOn the Declarative Semantics of Deductive Databases and Logic Programs
556 Citations1988Teodor C. Przymusiński
The class of perfect models of a deductive database is introduced and it is argued that this class of models provides a correct intended semantics for such databases, incorporating a natural form of the closed-world assumption.
SIAM Journal on ComputingLanguages that Capture Complexity Classes
545 Citations1987Neil Immerman
It is shown that projection translations are a uniform version of Valiant’s projections, and that the usual complete problems remain complete via these very restrictive reductions.
Journal of Computer and System SciencesStructure and complexity of relational queries
537 Citations1982Ashok K. Chandra, David Harel
This paper is an attempt at laying the foundations for the classification of queries on relational data bases according to their structure and their computational complexity, using a Σ-Π hierarchy of height, ω2, called the fixpoint query hierarchy, and its properties investigated.
Very Large Data BasesAlgorithms for acyclic database schemes
495 Citations1981Mihalis Yannakakis
The purpose in this paper is to describe efficient algorithms in this setting for various problems, such as computing projections, minimizing joins, inferring dependencies, and testing for dependency satisfaction.
Mathematics of the USSR-SbornikTHE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
492 Citations1977G. S. Makanin
The Journal of Logic ProgrammingLogic programming and knowledge representation
438 Citations1994Chitta Baral, Michael Gelfond
This paper considers extensions of the language of definite logic programs by classical (strong) negation, disjunction, and some modal operators and shows how each of the added features extends the representational power of thelanguage.
Journal of the ACMThe complexity of logic-based abduction
428 Citations1995Thomas Eiter, Georg Gottlob
It is shown that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases.
The Journal of Logic ProgrammingThe integration of functions into logic programming: From theory to practice
426 Citations1994Michael Hanus
The development of the operational semantics as well as the improvement of the implementation of the implementation of functional logic languages are surveyed.
Journal of the ACMAutoepistemic logic
422 Citations1991Wiktor Marek, Mirosław Truszczyński
It is proven that the problem of existence of stable models is NP-complete and the definition of stratified theories is extended and efficient algorithms for testing whether atheory is stratified are proposed.
Theory of formal systems
392 Citations1962Raymond M. Smullyan
Lecture notes in computer scienceOn indefinite databases and the closed world assumption
383 Citations2005Jack Minker
A database is said to be indefinite if there is an answer to a query of the form Pa V Pb where neither Pa nor Pb can be derived from the database.
Annals of Mathematics and Artificial IntelligenceOn the computational cost of disjunctive logic programming: Propositional case
380 Citations1995Thomas Eiter, Georg Gottlob
This paper shows that the consistency check is Σ2p-complete for the disjunctive stable model semantics, the iterated closed world assumption, and the perfect model semantics; analogous results are derived for the answer sets semantics of extendeddisjunctive logic programs.
The alternating fixpoint of logic programs with negation
370 Citations1989Allen Van Gelder
It is shown that a system is fixpoint Logic, which permits rule bodies to be first order formulas but requires inductive relations to be positive within them, can be transformed straightforwardly into a normal logic program whose alternating fixpoint partial model corresponds to the least fixpoint of the fixpoint logic system.
Journal of the ACMEquivalences Among Relational Expressions with the Union and Difference Operators
369 Citations1980Yehoshua Sagiv, Mihalis Yannakakis
It is shown that containment of tableaux is a necessary step in testing equivalence of queries with union and difference, and the containment problem is shown to be NP-complete even for tableaux that correspond to expressions with only one project and several join operators.
ACM SIGMOD RecordObject identity as a query language primitive
363 Citations1989Serge Abiteboul, Paris C. Kanellakis
Artificial IntelligenceOn the complexity of propositional knowledge base revision, updates, and counterfactuals
346 Citations1992Thomas Eiter, Georg Gottlob
Elsevier eBooksA Catalog of Complexity Classes
346 Citations1990David S. Johnson
This chapter discusses the concepts needed for defining the complexity classes, a set of problems of related resource-based complexity that can be solved by an abstract machine M using O(f(n) of resource R, where n is the size of the input.
Journal of Symbolic ComputationSolving systems of polynomial inequalities in subexponential time
332 Citations1988D. Yu. Grigor'ev, Nicolai Vorobjov
The algorithm constructs a certain finite set of solutions for the family of components of connectivity of the set of all real solutions of the system in the case of a positive answer.
Deep Blue (University of Michigan)Logic and the Challenge of Computer Science
317 Citations1985Yuri Gurevich
The Journal of Logic ProgrammingHorn clause queries and generalizations
309 Citations1985Ashok K. Chandra, David Harel
It is shown that logic programs express precisely the queries in YE + (the set of queries representable by a fixpoint applied to a positive existential query), and the resulting class has the expressive power of universally quantified second-order logic.
New Generation ComputingStable semantics for disjunctive programs
309 Citations1991Teodor C. Przymusiński
Thestable model semantics for disjunctive logic programs and deductive databases is introduced, which generalizes the stable model semantics, defined earlier for normal (i.e., non-disjunctive) programs, and can be generalized to the class of all disjunctions logic programs.
Annals of Mathematics and Artificial IntelligencePropositional semantics for disjunctive logic programs
280 Citations1994Rachel Ben-Eliyahu, Rina Dechter
It is shown that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former.
Journal of Computer and System SciencesLinear unification
280 Citations1978Mike Paterson, Mark N. Wegman
Medical Entomology and ZoologyFoundations of disjunctive logic programming
269 Citations1992Jorge Lobo, Jack Minker +1 more
This paper discusses first-order theory - syntax first order theory - semantics logic programs - syntax Logic programs - semantics - models and interpretations substitutions and unifiers fixpoint theory, a comparison of definite and disjunctive logic programs and normal logic programs.
Theoretical Computer SciencePrinciples of programming with complex objects and collection types
261 Citations1995Peter Buneman, Shamim A. Naqvi +2 more
A new principle for the development of database query languages that the primitive operations should be organized around types is presented, in which a number of well-known languages are to be found as natural sublanguages.
Journal of Computer and System SciencesDatalog extensions for database queries and updates
256 Citations1991Serge Abiteboul, Victor Vianu
Deterministic and non-deterministic extensions of Datalog with fixpoint semantics are proposed, and their expressive power characterized, to overcome the limited expressive power available with purely declarative semantics.
Artificial IntelligenceLinear resolution with selection function
256 Citations1971Robert Kowalski, D. Brian Kuehner
Linear resolution with selection function (SL-resolution) is a restricted form of linear resolution which chooses from each clause a single literal to be resolved upon in that clause.
Artificial IntelligencePreferred answer sets for extended logic programs
250 Citations1999Gerhard Brewka, Thomas Eiter
This paper addresses the issue of how Gelfond and Lifschitz's answer set semantics for extended logic programs can be suitably modified to handle prioritized programs, and defines a strong and a weak notion of preferred answer sets.
Annals of Pure and Applied LogicFixed-point extensions of first-order logic
243 Citations1986Yuri Gurevich, Saharon Shelah
Elsevier eBooksElements of Relational Database Theory
199 Citations1990Paris C. Kanellakis
This paper is to provide a systematic and unifying introduction to relational database theory, including some of the recent developments in database logic programming.
Theoretical Computer ScienceDeclarative modeling of the operational behavior of logic languages
199 Citations1989Moreno Falaschi, Giorgio Levi +2 more
A new declarative semantics for logic programs is defined, which is based on interpretations containing (possibly) non-ground atoms, and one of the two models allows the set of computed answer substitutions to be characterized precisely.
Information and ComputationDisjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation
197 Citations1997Nicola Leone, Pasquale Rullo +1 more
Stable model semantics is focused on, it is shown that the set of stable models coincides with the family of unfounded-free models, and it is proved that stable models can be defined equivalently by a property of their false literals.
Constraint query languages (preliminary report)
197 Citations1990Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving, and the key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints.
IEEE Transactions on Knowledge and Data EngineeringEnhancing Disjunctive Datalog by constraints
193 Citations2000Francesco Buccafurri, Nicola Leone +1 more
An extension of Disjunctive Datalog by integrity constraints that is well-suited to represent common sense reasoning and knowledge-based problems arising in different areas of computer science such as planning, graph theory optimizations, and abductive reasoning is presented.
Generic Computation and its complexity
193 Citations1991Serge Abiteboul, Victor Vianu
A normal form is proved for the Turing Machines, which provides a key technical tool for while queries, and complexity measures for generic mappings are defined, focusing on notions of polynomial time and space complexit y forGeneric mappings, and show their robustness.
Information and ControlA note on succinct representations of graphs
186 Citations1986Christos H. Papadimitriou, Mihalis Yannakakis
It is shown that under the same representation, graph properties that are ordinarily NP-complete become complete for non-deterministic exponential time.
Decidability and expressiveness aspects of logic queries
180 Citations1987Oded Shmueli
It is shown that H+ is more expressive than YE++ and that any H+ program can be transformed into an equivalent H+ program containing a single recursive predicate without using the equality or inequality operators.
Theoretical Computer SciencePropositional circumscription and extended closed-world reasoning are ΠP2-complete
167 Citations1993Thomas Eiter, Georg Gottlob
The Journal of Logic ProgrammingA survey of complexity results for non-monotonic logics
149 Citations1993Marco Cadoli, Marco Schaerf
This paper focuses mainly on non-monotonic formalisms, like default logic, autoepistemic logic, circumscription, closed-world reasoning, and abduction, whose relations with logic programming are clear and well studied.
Lecture notes in computer scienceFoundations of Equational Logic Programming
149 Citations1989Steffen H dobler
This paper presents a meta-modelling framework for Universal Unification by Complete Sets of Transformations and Lazy Resolution and Complete sets of Inference Rules for Horn Equational Theories.
Texts in theoretical computer scienceThe Resolution Calculus
147 Citations1997Alexander Leitsch
This is a completely new presentation of resolution as a logical calculus and as a basis for computational algorithms and decision procedures and a systematic treatment of recent research topics.
Theoretical Computer ScienceThe complexity of logical theories
147 Citations1980L. Berman
A method of encoding the computation of an alternating TM into a logical theory, using Ehrenfencht games, and the proof of a general theorem is outlined.
On the expressive power of datalog
144 Citations1990Phokion G. Kolaitis, Moshe Y. Vardi
It is shown here that the two dichotomies are indeed proper in terms of expressibility in Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules.
Journal of the ACMAutomatic recognition of tractability in inference relations
143 Citations1993David McAllester
A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations that automatically recognize the tractability of the inference rules underlying congruence closure.
Journal of Computer and System SciencesThe Expressive Powers of the Logic Programming Semantics
138 Citations1995J.S. Schlipf
The proof is a corollary of the result that over non-Herbrand infinite models, the well-founded semantics is more expressive than the three-valued program completion semantics, which is in a sense uniform in the strata.
On the complexity of bounded-variable queries (extended abstract)
136 Citations1995Moshe Y. Vardi
This paper shows that, for bounded-variable queries, the gap between their expression and combined complexities, one one hand, and their data complexity, on the other hand, narrows and in some cases disappears, and suggests variable minimization as a query optimization methodology.
Theoretical Computer ScienceAbduction from logic programs: Semantics and complexity
134 Citations1997Thomas Eiter, Georg Gottlob +1 more
It is shown that logic programming semantics can be more meaningful for abductive reasoning than classical inference by providing examples from the area of knowledge representation and reasoning, and proves abduction from logic programs as a rich source of problems of varying complexity.
Complexity and expressive power of logic programming
134 Citations2002Evgeny Dantsin, Thomas Eiter +2 more
The main focus is on decidable forms of logic programming, in particular propositional logic programming and datalog, but the also mention general logic programming with function symbols, and the complexity of the unification problem is addressed.
The Journal of Logic ProgrammingNegation as failure in the head
121 Citations1998Katsumi Inoue, Chiaki Sakama
The class of general extended disjunctive programs (GEDPs) is considered as logic programs with negation as failure in the head and it is discussed that the class of GEDPs is useful for representing knowledge in various domains in which the principle of minimality is too strong.
Lecture notes in computer scienceCol: A logic-based language for complex objects
115 Citations1988Serge Abiteboul, Stéphane Grumbach
A logic-based language for manipulating complex objects constructed using set and tuple constructors is introduced and applications of the language to procedural data, semantic database models, heterogeneous databases integration, and datalog query evaluation are presented.
Information and ComputationThe expressive power of stratified logic programs
109 Citations1991Phokion G. Kolaitis
Stratified logic programs became the choice for the treatment of negation in the NAIL ! system developed at Stanford University by Ullman and his co-workers.
Elsevier eBooksEquivalences of Logic Programs
107 Citations1988Michael J. Maher
This paper provides a systematic comparison of the relative strengths of various formulations of equivalence for logic programs and introduces the notion of subsumption-equivalence, which is used to give syntactic characterizations of the programs P for which the function TP satisfies some continuity properties.
Journal of the ACMRelational expressive power of constraint query languages
107 Citations1998Michael Benedikt, Guozhu Dong +2 more
The conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals is settled and a number of collapse results of the following form are established.
Theoretical Computer ScienceNegation by default and unstratifiable logic programs
105 Citations1991Nicole Bidoít, Christine Froidevaux
The contribution of the paper is to exhibit an interesting class of programs having a default semantics, called effectively stratifiable programs, and to provide a constructive definition of well-founded models of logic programs.
Bulletin of the London Mathematical SocietyTHE CLASSICAL DECISION PROBLEM (Perspectives in Mathematical Logic)
105 Citations1998A. J. Wilkie
This year saw the development of both the Go$ del–Herbrand–Kleene theory of recursive functions and, independently, the equivalent notion of machine computable sets of words by Turing.
Lecture notes in computer scienceNP-completeness of the set unification and matching problems
104 Citations1986Deepak Kapur, Paliath Narendran
The set-unification and set-matching problems, which are very restricted cases of the associative-commutative-idempotent unification and matching problems, respectively, are shown to be NP-complete and the NP-completeness of the subsumption check in first-order resolution follows from these results.
Theoretical Computer ScienceCapturing complexity classes by fragments of second-order logic
102 Citations1992Erich Grädel
It is shown that all these logics collapse to their existential fragments and they are strictly weaker than previously known logics for these classes and fail to express some very simple properties.
The MIT Press eBooksInductive Logic Programming
102 Citations1995Francesco Bergadano, Daniele Gunetti
An extended, up-to-date survey of ILP, emphasizing methods and systems suitable for software engineering applications, including inductive program development, testing, and maintenance is provided.
Hypertree decompositions and tractable queries
98 Citations1999Georg Gottlob, Nicola Leone +1 more
This paper presents a meta-modelling architecture suitable for hierarchical database systems and some examples of such systems have been presented at the ACM Symposium on Principles of Database Systems.
Logical Writings
98 Citations1971Jacques Herbrand
BIT Numerical MathematicsHorn clause computability
97 Citations1977Sten-Åke Tärnlund
It is proved that a Turing computable functionf is computable in binary Horn clauses, which are a subset of first order logic and do not need more than one function symbol.
Journal of Symbolic ComputationComplexity of matching problems
96 Citations1987Dan Benanav, Deepak Kapur +1 more
If every variable appears at most once in a term being matched, then the associative-commutative matching problem is shown to have an upper-bound of O (|s| * |t|3), where |s| and |t | are respectively the sizes of the pattern s and the subject t.
Journal of Computer and System SciencesThe Complexity of Querying Indefinite Data about Linearly Ordered Domains
92 Citations1997Ron van der Meyden
Annals of Mathematics and Artificial IntelligenceStatic semantics for normal and disjunctive logic programs
90 Citations1995Teodor C. Przymusiński
It is shown that among all static expansions of a disjunctive programP there is always the least static expansion, which is called the static completion¯P, which can be defined as the least fixed point of a naturalminimal model operator and can be constructed by means of a simpleiterative procedure.
Journal of Automated ReasoningDualities between alternative semantics for logic programming and nonmonotonic reasoning
89 Citations1993Chitta Baral, V. S. Subrahmanian
This paper proves that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming, and shows how the same technique may be applied to ‘strong’ autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.
Journal of Computer and System SciencesComputing with First-Order Logic
89 Citations1995Serge Abiteboul, Victor Vianu
It is shown that fixpoint and while are the PTIME and PSPACE restrictions of GMloose, and more powerful languages which model arbitrary computation interacting with a database using a finite set of FO queries are considered.
Journal of Computer and System SciencesOn the Expressive Power of Datalog: Tools and a Case Study
89 Citations1995Phokion G. Kolaitis, Moshe Y. Vardi
Bulletin of the London Mathematical SocietyFINITE MODEL THEORY (Perspectives in Mathematical Logic)
88 Citations1997Anuj Dawar
Lecture notes in computer scienceConstraint programming and database query languages
87 Citations1994Paris C. Kanellakis, Dina Goldin
This overview of constraint query languages (CQLs) presents an algebra for dense order constraints that is simpler to evaluate than the calculus described in [KKR], and sharpen some of the related data complexity bounds.
Lecture notes in computer scienceStrong and weak constraints in disjunctive datalog
85 Citations1997Francesco Buccafurri, Nicola Leone +1 more
A number of examples shows that the proposed language (call it Data-log∨,⌝, c) is well-suited to represent complex knowledge-based problems, such as, for instance, NP optimization problems.
Journal of Automated ReasoningAn alternative approach to the semantics of disjunctive logic programs and deductive databases
85 Citations1994Chiaki Sakama, Katsumi Inoue
This paper presents a proof procedure for the possible model semantics, an alternative theoretical framework to the classical minimal model semantics and provides a flexible inference mechanism for inferring negation in disjunctive logic programs.
ACM Transactions on Database SystemsConverting nested algebra expressions into flat algebra expressions
84 Citations1992Jan Paredaens, Dirk Van Gucht
It is shown that the flat relational algebra is rich enough to extract the same “flat information” from a flat database as the nested algebra does, which implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nestedgebra.
Journal of Computer and System SciencesDatalog vs first-order logic
84 Citations1994Miklós Ajtai, Yuri Gurevich
Lecture notes in computer scienceLogic and databases: A 20 year retrospective
83 Citations1996Jack Minker
In this retrospective I shall review developments that have taken place in the field, assess the contributions that have been made, consider the status of implementations of deductive databases and discuss the future of work in this area.
AlgorithmicaA time bound on the materialization of some recursively defined views
82 Citations1986Yannis Ioannidis
Considering a restricted class of recursive Horn clauses, this work gives necessary and sufficient conditions for members of the class to have this bound.
…