Knowledge compilation = Query rewriting + View synthesis

Summary: Recasts knowledge compilation in relational DBs: model KB and formula as databases and deduction as a second-order query Q; compilation = view synthesis (D_KB) + query rewriting (Q_r). Identify syntactic Q-classes that admit poly-size D_KB and FO Q_r (phase-2 polytime), and complementary hardness (no poly D_KB or FO Q_r unless PH collapses). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1264
Venue: PODS
Year: 2002
Pagerank: -
Overall Rank: 13,956 | 4.25%
DOI: 10.1145/543613.543640

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Marco Cadoli (University of Roma Tre)
2. Toni Mancini (University of Roma Tre)

BibTeX Citation

@inproceedings{cadoli_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Knowledge compilation = Query rewriting + View synthesis}},
        url = {https://dl.acm.org/doi/10.1145/543613.543640},
        doi = {10.1145/543613.543640},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cadoli, Marco and Mancini, Toni},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
2	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
3	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
4	2,527	Rewriting Queries Using Views in Description Logics	1997	PODS
5	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
6	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
7	1,830	Optimizing the Rule-Data Interface in a KMS	1986	VLDB
8	12,029	Bounded Query Rewriting Using Views	2016	PODS
9	69	Answering Queries Using Views (Extended Abstract)	1995	PODS
10	7,886	Polynomial-time program transformations in deductive databases	1990	PODS