Querying Weak Instances

Summary: Defines "weak instances": all universal relations that extend incomplete base relations and satisfy dependencies, with certain answers as the intersection across these instances (relaxing the pure universal assumption). Proposes building a finite representative by padding tuples with distinct nulls and chasing total dependencies to evaluate monotonic queries correctly, and analyzes chase inconsistency and limits of projection-based methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 707
Venue: PODS
Year: 1984
Pagerank: 5.2970277e-05
Overall Rank: 9,259 | 36.48%
DOI: 10.1145/588011.588051

Incoming Non-self Citations Over Time

Authors

1. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{yannakakis_pods84,
        address = {New York, NY, USA},
        series = {{PODS} '84},
        title = {{Querying Weak Instances}},
        url = {https://dl.acm.org/doi/10.1145/588011.588051},
        doi = {10.1145/588011.588051},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Yannakakis, Mihalis},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,132	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.694968e-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
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
1,111	The U. R. Strikes Back	1982	PODS	0.00012131168
2,289	Windows On The World	1983	SIGMOD	8.7994393e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,648	A Universal Relation Database System Implemented Via the Network Model	1982	PODS
2	1,537	Assumptions in Relational Database Theory	1982	PODS
3	3,750	Dependency Satisfaction in Databases with Incomplete Information	1984	VLDB
4	4,115	Incomplete Information and Dependencies in Relational Databases	1983	SIGMOD
5	742	Independent Database Schemas (Extended Abstract)	1982	PODS
6	8,970	Understanding Queries by Conditional Instances	2022	SIGMOD
7	3,551	Efficient Query Answering in the Representative Instance Approach	1985	PODS
8	13,121	Efficient Updates to Independent Schemes in the Weak Instance Model	1990	SIGMOD
9	266	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD
10	13,173	A New Basis for the Weak Instance Model	1987	PODS