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: 1265
Venue: PODS
Year: 2002
Pagerank: -
Overall Rank: 13,755 | 4.31%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Marco Cadoli
2. Toni Mancini

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	Pagerank
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
2,536	Rewriting Queries Using Views in Description Logics	1997	PODS	8.5837937e-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
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
854	Optimizing the Rule-Data Interface in a KMS	1986	VLDB	0.00015933596
11,826	Bounded Query Rewriting Using Views	2016	PODS	4.1945683e-05
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05