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: haaec488e4be3c6ea
Venue: PODS
Year: 1984
Pagerank: 5.1781766e-05
Overall Rank: 9,433 | 36.58%
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,279	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.5671882e-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
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
1,138	The U. R. Strikes Back	1982	PODS	0.00011865234
2,346	Windows On The World	1983	SIGMOD	8.6020356e-05

Semantically Similar Papers

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