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.0287573e-05
Overall Rank: 6,522 | 54.63%
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,852	Negation and Minimality in Non-Horn Databases	1993	PODS	6.7017663e-05
12,833	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1945683e-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,852	Negation and Minimality in Non-Horn Databases	1993	PODS	6.7017663e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,746	Binding Propagation in Disjunctive Databases	1998	VLDB	4.1945683e-05
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
9,791	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2818172e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
12,934	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	4.1945683e-05
3,003	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS	7.7388586e-05
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
12,833	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.1945683e-05