DBScholar

Back to papers

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
732
Venue
PODS
Year
1985
Pagerank
0.00010839353
Overall Rank
1,417 | 90.28%
DOI
10.1145/325405.325427

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sagiv_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{On Computing Restricted Projections of Representative Instances}},
        url = {https://dl.acm.org/doi/10.1145/325405.325427},
        doi = {10.1145/325405.325427},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sagiv, Yehoshua},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
616 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015712636
1,173 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011822695
1,788 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.7653696e-05
1,856 Automata Theory for Database Theoreticians 1989 PODS 9.6053834e-05
2,904 Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases 1989 PODS 7.9757931e-05
5,351 Constant Time Maintenance or The Triumph of the fd. 1986 PODS 6.2533477e-05
6,077 Safety of Datalog Queries over Infinite Databases 1989 PODS 5.9850223e-05
7,972 On the First-Order Expressibility of Recursive Queries 1989 PODS 5.5160399e-05
9,706 Understanding the implications of view update policies 1985 VLDB 5.2351259e-05
13,121 Efficient Updates to Independent Schemes in the Weak Instance Model 1990 SIGMOD 5.093636e-05
13,173 A New Basis for the Weak Instance Model 1987 PODS 5.093636e-05
Previous Page 1 / 1 Next

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
40 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00046918506
97 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00034574497
266 Can We Use The Universal Instance Assumption Without Using Nulls? 1981 SIGMOD 0.00022823892
742 Independent Database Schemas (Extended Abstract) 1982 PODS 0.00014426824
3,551 Efficient Query Answering in the Representative Instance Approach 1985 PODS 7.3196924e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,241 A Less Costly Constraints Checking for Join Dependency 1984 VLDB
2 8,298 A Characterization of Constant-time-maintainability for BCNF Database Schemes 1988 SIGMOD
3 97 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD
4 8,297 Independence-reducible Database Schemes 1988 PODS
5 6,698 Properties Of Database Schemata With Functional Dependencies 1984 PODS
6 266 Can We Use The Universal Instance Assumption Without Using Nulls? 1981 SIGMOD
7 7,132 Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions 1984 SIGMOD
8 2,894 The Size of Projections of Relations Satisfying a Functional Dependency 1982 VLDB
9 13,145 Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction 1988 PODS
10 3,551 Efficient Query Answering in the Representative Instance Approach 1985 PODS