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 (INRIA)
- 2. Eric Simon (INRIA)
- 3. Victor Vianu (University of California San Diego)
BibTeX Citation
@inproceedings{abiteboul_pods90,
address = {New York, NY, USA},
series = {{PODS} '90},
title = {{Non-Deterministic Languages to Express Deterministic Transformations}},
url = {https://dl.acm.org/doi/10.1145/298514.298575},
doi = {10.1145/298514.298575},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Abiteboul, Serge and Simon, Eric and Vianu, Victor},
year = {1990}
}Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,986 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.8912631e-05 |
| 4,943 | Datalog Unchained | 2021 | PODS | 6.4332239e-05 |
| 7,830 | When Can We Answer Queries Using Result-Bounded Data Interfaces? | 2018 | PODS | 5.5357919e-05 |
| 8,773 | Semi-determinism (extended abstract) | 1992 | PODS | 5.3766157e-05 |
| 13,027 | Adding Disjunction to Datalog (Extended Abstract) | 1994 | PODS | 5.093636e-05 |
| 13,048 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 5.093636e-05 |
| 13,082 | Knowledgebase Transformations | 1992 | PODS | 5.093636e-05 |
| 13,105 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 5.093636e-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 |
|---|---|---|---|---|
| 174 | Decidability And Expressiveness Aspects Of Logic Queries | 1987 | PODS | 0.00027231487 |
| 313 | OPTIMIZING DATALOG PROGRAMS (Extended Abstract) | 1987 | PODS | 0.0002168869 |
| 2,402 | Update Semantics for Incomplete Databases | 1985 | VLDB | 8.6276184e-05 |
| 3,476 | Data Functions, Datalog and Negation (Extended Abstract) | 1988 | SIGMOD | 7.3807586e-05 |
| 6,752 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 5.7837368e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,885 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD |
| 2 | 13,040 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB |
| 3 | 8,128 | Decidability and Undecidability Results for the Termination Problem of Active Database Rules | 1998 | PODS |
| 4 | 8,120 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD |
| 5 | 6,752 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB |
| 6 | 702 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS |
| 7 | 3,590 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS |
| 8 | 12,976 | Static Analysis of Intensional Databases in U-Datalog | 1996 | PODS |
| 9 | 8,773 | Semi-determinism (extended abstract) | 1992 | PODS |
| 10 | 13,105 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD |