The expressive power of stratified logic programs

DOI10.1016/0890-5401(91)90059-BMaRDI QIDQ803773zbMATH OpenOpenAlexFDO

Authors Phokion G. Kolaitis

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90059-b

zbMATH Keywords

database queriesfixedpoint logicgame treesstratified logic programs

Mathematics Subject Classification ID

Inductive definability (03D70) Logic programming (68N17) Database theory (68P15)

Review text

Along the interface between the theory of logic programming and relational database theory a particular class of programs has been discovered which is in some sense maximal with respect to the property of having a well behaved semantics. It is the class of stratified programs, consisting of programs in a Datalog style, which combine recursion and negation, with the proviso that the collection of intensional predicates ocurring in these programs is stratified: the predicates can be ordered into strata in such a way that recursive definitions don't invoke predicates in a higher stratum than the predicate defined by this definition, and that all used predicates from the same stratum occur just positively. Aside from describing the class of stratified programs itself the theory has been looking for an independent description of its expressive power. For some time researchers believed that the expressive power of stratified programs over finite structures coincides with that of fixedpoint logic. Such an assertion was stated and proved by Chandra and Harel in 1985. The author of the present paper spotted a difficulty in the proof, and subsequently the result was found to be false by Dahlhaus in 1987. The present paper presents a proof for the correct characterization: the class of stratified programs are as powerful as the existential fragment of fixedpoint logic. Also the full fragment of fixedpoint logic is of a higher expressive power. The proof uses the game trees introduced by Chandra and Harel in a paper from 1982. The result is extended to some infinite structures as well.

Recommendations

• The expressiveness of locally stratified programs
• Stratified least fixpoint logic
• The expressive powers of the logic programming semantics
• scientific article; zbMATH DE number 4199653
• The expressive power of stratified logic programs with value invention

Cites work

• Contributions to the Theory of Logic Programming
• Elementary induction on abstract structures
• Fixed-point extensions of first-order logic
• Horn clause queries and generalizations
• scientific article; zbMATH DE number 4199654 (Why is no real title available?)
• scientific article; zbMATH DE number 4199656 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 4035805 (Why is no real title available?)
• scientific article; zbMATH DE number 4185010 (Why is no real title available?)
• Relational queries computable in polynomial time
• Structure and complexity of relational queries

Cited in

(41)

• Datalog extensions for database queries and updates
• Why not negation by fixpoint?
• On the expressive power of database queries with intermediate types
• The expressive power of the bounded-iteration construct
• Capturing complexity classes by fragments of second-order logic
• The functional dimension of inductive definitions
• Testing logic programs for local stratification
• Verifying local stratifiability of logic programs and databases
• Expressive power and complexity of partial models for disjunctive deductive databases
• Semantics and expressiveness issues in active databases
• The expressive power of stratified logic programs with value invention
• Stratified least fixpoint logic
• Non-determinism in logic-based languages
• The expressive powers of stable models for bound and unbound DATALOG queries
• Polynomial-time computable stable models
• Abduction from logic programs: Semantics and complexity
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Functional queries in datalog
• The expressive powers of the logic programming semantics
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• The expressiveness of locally stratified programs
• Complexity and undecidability results for logic programming
• scientific article; zbMATH DE number 1696722 (Why is no real title available?)
• On Q-resolution and CDCL QBF solving
• scientific article; zbMATH DE number 4199653 (Why is no real title available?)
• scientific article; zbMATH DE number 4147555 (Why is no real title available?)
• The defining power of stratified and hierarchical logic programs
• Subsumption-stratified datalog
• scientific article; zbMATH DE number 515730 (Why is no real title available?)
• On the impact of stratification on the complexity of nonmonotonic reasoning
• A finite-model-theoretic view on propositional proof complexity
• Complexity and expressive power of second-order extended Horn logic
• A declarative extension of horn clauses, and its significance for Datalog and its applications
• Semantics and expressive power of nondeterministic constructs in deductive databases
• Bottom-up evaluation and query optimization of well-founded models
• Can't you answer while you wait?
• Hypothetical answers to continuous queries over data streams
• Convergence of datalog over (pre-) semirings
• NP-completeness by first-order and quantifier-free interpretations and related topics
• Argumentation frameworks, games and kernels: time for a family Reunion!
• Negation in rule-based database languages: A survey

This page was built for publication: The expressive power of stratified logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q803773)