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,043 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6632326e-05 |
| 5,716 | Datalog Unchained | 2021 | PODS | 5.3569788e-05 |
| 8,567 | Semi-determinism (extended abstract) | 1992 | PODS | 4.4893996e-05 |
| 12,842 | Adding Disjunction to Datalog (Extended Abstract) | 1994 | PODS | 4.1905499e-05 |
| 12,864 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 4.1905499e-05 |
| 12,898 | Knowledgebase Transformations | 1992 | PODS | 4.1905499e-05 |
| 12,920 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.1905499e-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 |
|---|---|---|---|---|
| 173 | Decidability And Expressiveness Aspects Of Logic Queries | 1987 | PODS | 0.00038731283 |
| 209 | OPTIMIZING DATALOG PROGRAMS (Extended Abstract) | 1987 | PODS | 0.00034147258 |
| 2,203 | Update Semantics for Incomplete Databases | 1985 | VLDB | 9.2995519e-05 |
| 3,320 | Data Functions, Datalog and Negation (Extended Abstract) | 1988 | SIGMOD | 7.2212998e-05 |
| 6,695 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 4.9550839e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,363 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD | 4.7461604e-05 |
| 12,856 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1905499e-05 |
| 7,774 | Decidability and Undecidability Results for the Termination Problem of Active Database Rules | 1998 | PODS | 4.6498948e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.6506061e-05 |
| 6,695 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 4.9550839e-05 |
| 375 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025262028 |
| 3,256 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS | 7.3135363e-05 |
| 12,791 | Static Analysis of Intensional Databases in U-Datalog | 1996 | PODS | 4.1905499e-05 |
| 8,567 | Semi-determinism (extended abstract) | 1992 | PODS | 4.4893996e-05 |
| 12,920 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.1905499e-05 |