On Computing Restricted Projections of Representative Instances

Summary: FO-definability of restricted projections iff the full implicational dependencies are equivalent to one join dependency plus EGDs (for pure TGDs this collapses to a single JD). Also gives complexity bounds for union-of-tableaux construction (worst-case exponential, sometimes polynomial) and a simpler characterization of independent schemes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 733
Venue: PODS
Year: 1985
Pagerank: 0.0001354084
Overall Rank: 1,167 | 91.90%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yehoshua Sagiv

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
541	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00020586706
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
2,352	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	8.9815852e-05
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05
5,322	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	5.56739e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
9,569	Understanding the implications of view update policies	1985	VLDB	4.3212967e-05
12,936	Efficient Updates to Independent Schemes in the Weak Instance Model	1990	SIGMOD	4.1905499e-05
12,986	A New Basis for the Weak Instance Model	1987	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.0007528369
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064817807
131	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00043719033
500	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00021622167
2,531	Efficient Query Answering in the Representative Instance Approach	1985	PODS	8.5916172e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,053	A Less Costly Constraints Checking for Join Dependency	1984	VLDB	4.1905499e-05
7,983	A Characterization of Constant-time-maintainability for BCNF Database Schemes	1988	SIGMOD	4.6089395e-05
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064817807
7,982	Independence-reducible Database Schemes	1988	PODS	4.6089395e-05
6,604	Properties Of Database Schemata With Functional Dependencies	1984	PODS	4.9923197e-05
131	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00043719033
7,070	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	4.8380576e-05
1,310	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB	0.000126534
12,960	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS	4.1905499e-05
2,531	Efficient Query Answering in the Representative Instance Approach	1985	PODS	8.5916172e-05