An Extended Relational Algebra with Control Over Duplicate Elimination

Summary: Extends relational algebra to multiset relations with explicit control over duplicate elimination, and frames queries in extended algebra, tableaux, and DAPLEX. Proves conjunctive-equivalence decidable via tableaux but NP-complete, and shows extended algebra and DAPLEX have essentially the same conjunctive expressiveness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 618
Venue: PODS
Year: 1982
Pagerank: 0.00016097758
Overall Rank: 837 | 94.18%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
51	Including Group-By in Query Optimization	1994	VLDB	0.00067123727
100	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00049624696
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
975	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00014893961
1,313	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.0001263831
2,391	Processing Queries Over Generalization Hierarchies in a Multidatabase System	1983	VLDB	8.9022915e-05
2,395	Algebraic Properties of Bag Data Types	1991	VLDB	8.8998019e-05
2,426	Towards an Effective Calculus for Object Query Languages	1995	SIGMOD	8.8375297e-05
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
3,364	Multirelations - Semantics and Languages	1985	VLDB	7.1731086e-05
4,134	Query Optimization for CODASYL Database Systems	1982	SIGMOD	6.4191992e-05
4,319	SIM: A Database System Based on the Semantic Data Model	1988	SIGMOD	6.2885419e-05
6,837	The Generalized Pre-Grouping Transformation: Aggregate-Query Optimization in the Presence of Dependencies	2003	VLDB	4.9111342e-05
12,901	A Uniform Approach to Processing Temporal Queries	1992	VLDB	4.1945683e-05
12,990	Query Optimization By Stored Queries	1987	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	The Functional Data Model and the Data Language DAPLEX	1979	SIGMOD	0.0011248121
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
12,847	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1945683e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
12,861	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD	4.1945683e-05
445	The Magic of Duplicates and Aggregates	1990	VLDB	0.0002294367
12,935	A Sound and Complete Query Evaluation Algorithm for Relational Databases with Disjunctive Information (Extended Abstract)	1989	PODS	4.1945683e-05
3,364	Multirelations - Semantics and Languages	1985	VLDB	7.1731086e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446