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: 995
Venue: PODS
Year: 1993
Pagerank: 5.5958254e-05
Overall Rank: 7,563 | 48.12%
DOI: 10.1145/153850.153864

Incoming Non-self Citations Over Time

Authors

1. Thomas Eiter (Vienna University of Technology)
2. Georg Gottlob (Vienna University of Technology)

BibTeX Citation

@inproceedings{eiter_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Complexity Aspects of Various Semantics for Disjunctive Databases}},
        url = {https://dl.acm.org/doi/10.1145/153850.153864},
        doi = {10.1145/153850.153864},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Eiter, Thomas and Gottlob, Georg},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,964	Negation and Minimality in Non-Horn Databases	1993	PODS	6.0262735e-05
13,027	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	5.093636e-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
5,964	Negation and Minimality in Non-Horn Databases	1993	PODS	6.0262735e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,939	Binding Propagation in Disjunctive Databases	1998	VLDB
2	1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS
3	9,946	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
4	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
6	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
7	13,129	Complexity of Query Processing in Databases with OR-Objects	1989	PODS
8	4,266	Counting Answers to Existential Positive Queries: A Complexity Classification	2016	PODS
9	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
10	13,027	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS