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,769 | 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
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
2,539	Rewriting Queries Using Views in Description Logics	1997	PODS	8.5759464e-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
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
850	Optimizing the Rule-Data Interface in a KMS	1986	VLDB	0.00015911875
11,834	Bounded Query Rewriting Using Views	2016	PODS	4.1905499e-05
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05