Adding disjunction to datalog (extended abstract)
Published 1 January 1994Open access
Thomas Eiter, Georg Gottlob, Heikki Mannila
Citations60
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.
TL;DR
The brave variants of these semantics of disjunctive datalog express the same set of queries and precisely capture the complexity of class &Sgr;P/2.
Abstract
We study the expressive power and complexity of disjunctive datalog, i.e., datalog with disjunctive rule heads, under three different semantics: the minimal model semantics, the perfect models semantics, and the stable model semantics. We show that the brave variants of these semantics express the same set of queries. In fact, they precisely capture the complexity of class ΣP/2. The combined complexity of disjunctive datalog is shown to be NEXPTIMENP-complete.
Keywords
Computer Science
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.
Artificial IntelligenceCircumscription—A form of non-monotonic reasoning
2,012 Citations1980John McCarthy
Circumscription formalizes conjectural reasoning that humans and intelligent computer programs must often jump to the conclusion that the objects they can determine to have certain properties or relations are the only objects that do.
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.
Theoretical Computer ScienceThe polynomial-time hierarchy
1,303 Citations1976Larry J. Stockmeyer
The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established.
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.
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.
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.
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.
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.
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.
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.
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.
Journal of Automated ReasoningDeduction in non-Horn databases
147 Citations1985Adnan Yahya, LawrenceJ. Henschen
The class of non-Horn, function-free databases is investigated and several aspects of the problem of using theorem proving techniques for such databases are considered, including exploring the treatment of negative information and extending the existing method to accept non-unit negative clauses.
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 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.
Journal of Computer and System SciencesOn the Expressive Power of Datalog: Tools and a Case Study
89 Citations1995Phokion G. Kolaitis, Moshe Y. Vardi
Theory of Computing SystemsComplexity classes and theories of finite models
83 Citations1981James F. Lynch
Journal of Computer and System SciencesWhy not negation by fixpoint?
77 Citations1991Phokion G. Kolaitis, Christos H. Papadimitriou
Non-deterministic languages to express deterministic transformations
73 Citations1990Serge Abiteboul, Eric Simon +1 more
It is shown thatNon-determinism resolves some difficulties concerning the expressive power of deterministic languages: there are non-deterministic languages expressing low complexity classes of queries/updates, whereas no such deterministic language exist.
Journal of Computer and System SciencesOn the expressive power of database queries with intermediate types
60 Citations1991Richard Hull, Jianwen Su
The Complexity of Algorithmic Problems on Succinct Instances
56 Citations1992José L. Balcázar, Antoni Lozano +1 more
Two powerful lemmas quantifying exactly this increase of complexity are presented to show that previous results in the area can be interpreted assufficient conditions for completeness in the logarithmic time and polynomial time counting hierarchies.
The expressive powers of the logic programming semantics (extended abstract)
42 Citations1990John S. Schlipf
In this sense of uniform translatability, the well-founded semantics is shown to be more expressive than the 3-valued program completion and well- founded semantics over infinite Herbrand models.
Journal of Logic and ComputationComplete Problems Involving Boolean Labelled Structures and Projection Transactions
33 Citations1991Iain A. Stewart
Most of the problems involve the reliability of networks of processors where the links may fail and where these failures may be related to one another in a restricted way, but it is shown how the trick of labelling discrete structures with Boolean literals can be applied to yield other new natural complete problems involving digraphs and Boolean formulae.
On the expressive power of the extended relational algebra for the unnormalized relational model
32 Citations1987Dirk Van Gucht
The orlgmal relatIona database model proposed by Codd permltted complex structures to be entrles m a component of a tuple to be able to more falthfully model some database apphcatlons.
Complexity aspects of various semantics for disjunctive databases
32 Citations1993Thomas Eiter, Georg Gottlob
On the completeness of object-creating query languages
24 Citations1992Jan Van den Bussche, Dirk Van Gucht +2 more
This paper provides a precise characterization for the class of queries that can be expressed in database query languages and motivates this class the constructive queries by establishing a close correspondence between object creation and the construction of hereditarily finite sets.