Fundamental properties of deterministic and nondeterministic extensions of Datalog (Q756410): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Datalog / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(51)90006-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2035762642 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3204028 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable queries for relational data bases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4385543 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Why not negation by fixpoint? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3798300 / rank | |||
Normal rank |
Latest revision as of 15:05, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fundamental properties of deterministic and nondeterministic extensions of Datalog |
scientific article |
Statements
Fundamental properties of deterministic and nondeterministic extensions of Datalog (English)
0 references
1991
0 references
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.
0 references
query language
0 references
Datalog
0 references