Non-Deterministic Languages to Express Deterministic Transformations
Summary: Non-deterministic Datalog and FO/fixpoint (via a witness operator) precisely capture PTIME transformations, unlike any deterministic language. Also studies determinism detection (static/dynamic/semantic) and termination for these programs. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Serge Abiteboul
- 2. Eric Simon
- 3. Victor Vianu
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,040 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6707607e-05 |
| 5,705 | Datalog Unchained | 2021 | PODS | 5.3621239e-05 |
| 8,570 | Semi-determinism (extended abstract) | 1992 | PODS | 4.4937074e-05 |
| 12,833 | Adding Disjunction to Datalog (Extended Abstract) | 1994 | PODS | 4.1945683e-05 |
| 12,855 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 4.1945683e-05 |
| 12,888 | Knowledgebase Transformations | 1992 | PODS | 4.1945683e-05 |
| 12,910 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 172 | Decidability And Expressiveness Aspects Of Logic Queries | 1987 | PODS | 0.00038808816 |
| 200 | OPTIMIZING DATALOG PROGRAMS (Extended Abstract) | 1987 | PODS | 0.00035012858 |
| 2,197 | Update Semantics for Incomplete Databases | 1985 | VLDB | 9.3085358e-05 |
| 3,317 | Data Functions, Datalog and Negation (Extended Abstract) | 1988 | SIGMOD | 7.2283048e-05 |
| 6,693 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 4.9598818e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,368 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD | 4.7507411e-05 |
| 12,847 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1945683e-05 |
| 7,774 | Decidability and Undecidability Results for the Termination Problem of Active Database Rules | 1998 | PODS | 4.6543275e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.655071e-05 |
| 6,693 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 4.9598818e-05 |
| 374 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025286717 |
| 3,251 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS | 7.3215694e-05 |
| 12,782 | Static Analysis of Intensional Databases in U-Datalog | 1996 | PODS | 4.1945683e-05 |
| 8,570 | Semi-determinism (extended abstract) | 1992 | PODS | 4.4937074e-05 |
| 12,910 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.1945683e-05 |