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
h4e1b51c2c8b2fae4
Venue
PODS
Year
1985
Pagerank
0.00010599099
Overall Rank
1,455 | 90.22%
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
633 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015380574
1,201 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011560838
1,830 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.5498891e-05
1,908 Automata Theory for Database Theoreticians 1989 PODS 9.3940283e-05
2,965 Horn Tables - An Efficient Tool For Handling Incomplete Information In Databases 1989 PODS 7.8051404e-05
5,480 Constant Time Maintenance or The Triumph of the fd. 1986 PODS 6.1130394e-05
6,201 Safety of Datalog Queries over Infinite Databases 1989 PODS 5.8507344e-05
8,136 On the First-Order Expressibility of Recursive Queries 1989 PODS 5.3925529e-05
9,880 Understanding the implications of view update policies 1985 VLDB 5.1176637e-05
13,411 Efficient Updates to Independent Schemes in the Weak Instance Model 1990 SIGMOD 4.9793485e-05
13,463 A New Basis for the Weak Instance Model 1987 PODS 4.9793485e-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
41 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00045899672
102 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00033914384
278 Can We Use The Universal Instance Assumption Without Using Nulls? 1981 SIGMOD 0.00022313978
769 Independent Database Schemas (Extended Abstract) 1982 PODS 0.00014104125
3,619 Efficient Query Answering in the Representative Instance Approach 1985 PODS 7.1558272e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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