On the Space Requirements of Navigational Relationship Representations

Summary: Analyzes space cost of navigational relationship representations; defines the class and surveys baseline techniques. Proposes companionship-based compact representations and the powerset representation, the latter delivering a worst-case lower bound on navigational relation size. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2137
Venue: SIGMOD
Year: 1981
Pagerank: -
Overall Rank: 14,341 | 0.24%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Don Swartwout
2. J. C. Lagarias

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
302	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00028316973
12,603	Symmetric Relations and Cardinality-Bounded Multisets in Database Systems	2004	VLDB	4.1945683e-05
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
3,879	Applying Approximate Order Dependency to Reduce Indexing Space	1982	SIGMOD	6.6710739e-05
123	A Decomposition Storage Model	1985	SIGMOD	0.00045255007
13,058	High-Level Navigational Facilities for Network and Relational Databases	1983	VLDB	4.1945683e-05
5,303	The Partial Normalized Storage Model of Nested Relations	1988	VLDB	5.5779667e-05
13,023	An Efficient Implementation Of A Relational Data Base	1985	VLDB	4.1945683e-05
441	Computing Joins Of Relations	1975	SIGMOD	0.00023058395