Complexity Aspects of Various Semantics for Disjunctive Databases

Summary: Classifies complexity of literal/formula inference and model-existence for propositional disjunctive databases across several standard semantics. Places each decision problem at precise levels of the polynomial hierarchy, highlighting semantic-driven complexity separations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 996
Venue: PODS
Year: 1993
Pagerank: 5.0239231e-05
Overall Rank: 6,519 | 54.70%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Thomas Eiter
2. Georg Gottlob

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,855	Negation and Minimality in Non-Horn Databases	1993	PODS	6.6953111e-05
12,842	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3,855	Negation and Minimality in Non-Horn Databases	1993	PODS	6.6953111e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,755	Binding Propagation in Disjunctive Databases	1998	VLDB	4.1905499e-05
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
9,794	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2777144e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952
12,944	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	4.1905499e-05
3,005	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7315492e-05
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
12,842	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1905499e-05