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 |
|---|---|---|---|---|
| 3,046 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.7144804e-05 |
| 5,067 | Datalog Unchained | 2021 | PODS | 6.2898972e-05 |
| 7,991 | When Can We Answer Queries Using Result-Bounded Data Interfaces? | 2018 | PODS | 5.4115836e-05 |
| 8,935 | Semi-determinism (extended abstract) | 1992 | PODS | 5.2559789e-05 |
| 13,317 | Adding Disjunction to Datalog (Extended Abstract) | 1994 | PODS | 4.9793485e-05 |
| 13,338 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 4.9793485e-05 |
| 13,372 | Knowledgebase Transformations | 1992 | PODS | 4.9793485e-05 |
| 13,395 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.9793485e-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 |
|---|---|---|---|---|
| 177 | Decidability And Expressiveness Aspects Of Logic Queries | 1987 | PODS | 0.000266613 |
| 317 | OPTIMIZING DATALOG PROGRAMS (Extended Abstract) | 1987 | PODS | 0.00021220438 |
| 2,459 | Update Semantics for Incomplete Databases | 1985 | VLDB | 8.4353518e-05 |
| 3,541 | Data Functions, Datalog and Negation (Extended Abstract) | 1988 | SIGMOD | 7.2161746e-05 |
| 6,892 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB | 5.6541068e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,051 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD |
| 2 | 13,330 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB |
| 3 | 8,303 | Decidability and Undecidability Results for the Termination Problem of Active Database Rules | 1998 | PODS |
| 4 | 8,300 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD |
| 5 | 6,892 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB |
| 6 | 718 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS |
| 7 | 3,663 | On Probabilistic Fixpoint and Markov Chain Query Languages | 2010 | PODS |
| 8 | 13,266 | Static Analysis of Intensional Databases in U-Datalog | 1996 | PODS |
| 9 | 8,935 | Semi-determinism (extended abstract) | 1992 | PODS |
| 10 | 13,395 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD |