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.00013403617
Overall Rank: 1,196 | 91.69%
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
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
2,347	Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases	1989	PODS	8.9890664e-05
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05
5,841	Constant Time Maintenance or The Triumph of the fd.	1986	PODS	5.3039672e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
9,570	Understanding the implications of view update policies	1985	VLDB	4.3254416e-05
12,926	Efficient Updates to Independent Schemes in the Weak Instance Model	1990	SIGMOD	4.1945683e-05
12,975	A New Basis for the Weak Instance Model	1987	PODS	4.1945683e-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.00075110004
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
135	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00042421957
458	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00022657396
2,318	Efficient Query Answering in the Representative Instance Approach	1985	PODS	9.0400919e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,042	A Less Costly Constraints Checking for Join Dependency	1984	VLDB	4.1945683e-05
7,980	A Characterization of Constant-time-maintainability for BCNF Database Schemes	1988	SIGMOD	4.613363e-05
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
7,979	Independence-reducible Database Schemes	1988	PODS	4.613363e-05
6,603	Properties Of Database Schemata With Functional Dependencies	1984	PODS	4.9971153e-05
135	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00042421957
6,168	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.1716335e-05
1,320	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB	0.0001261772
12,950	Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction	1988	PODS	4.1945683e-05
2,318	Efficient Query Answering in the Representative Instance Approach	1985	PODS	9.0400919e-05