Fundamental properties of deterministic and nondeterministic extensions of Datalog

DOI10.1016/0304-3975(51)90006-0MaRDI QIDQ756410zbMATH OpenOpenAlexFDO

Authors Serge Abiteboul, Eric Simon

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(51)90006-0

zbMATH Keywords

Datalogquery language

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15)

Review text

Fundamental properties of deterministic and non-deterministic extensions of Datalog from Abiteboul and Vianu (1988) are studied. The extensions involve the use of negative literals both in bodies and heads of rules. Negative literals in heads are interpreted as deletions. A deterministic semantics is obtained by firing in parallel all applicable rules. The nondeterministic semantics results from firing (non-deterministically) one rule at a time. In the nondeterministic case programs do not describe functions but relations between database states. In both cases, the result is an increase in expressive power over Datalog. The price for it is that programs do not always terminate. It is studied when a program (i) is such that on a given input, all its successful computations reach a unique fixpoint, (ii) yields at least one output on every input and (iii) has only loop-free computations. It is also shown how to simulate programs containing loops by loop-free programs.

Recommendations

• Datalog extensions for database queries and updates
• Deterministic and non-deterministic stable models
• Datalog with non-deterministic choice computes NDB-PTIME
• Complexity and expressive power of deterministic semantics for DATALOG^ .
• A nondeterministic well-founded semantics

Cites work

• Computable queries for relational data bases
• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• scientific article; zbMATH DE number 4064544 (Why is no real title available?)
• scientific article; zbMATH DE number 1142327 (Why is no real title available?)
• Why not negation by fixpoint?

Cited in

(10)

• Datalog extensions for database queries and updates
• Temporal connectives versus explicit timestamps to query temporal databases
• A semantics for a class of non-deterministic and causal production system programs
• Non-determinism in logic-based languages
• Games and total Datalog\(^{\lnot}\) queries
• Positive Dedalus programs tolerate non-causality
• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• Datalog with non-deterministic choice computes NDB-PTIME
• scientific article; zbMATH DE number 638306 (Why is no real title available?)
• A value-propagating transformation technique for Datalog programs based on non-deterministic constructs

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Fundamental properties of deterministic and nondeterministic extensions of Datalog

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