On the Power of Algebras with Recursion

Summary: Explores recursion and negation in algebraic query languages, extending beyond fixed-point algebras and stratified deductive programs. Shows that queries expressible by general deduction with negation under valid semantics are captured by algebras with recursive definitions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2720
Venue: SIGMOD
Year: 1993
Pagerank: 5.6612789e-05
Overall Rank: 7,260 | 50.20%
DOI: 10.1145/170035.170090

Incoming Non-self Citations Over Time

Authors

1. Catriel Beeri (Hebrew University)
2. Tova Milo (INRIA; University of Toronto)

BibTeX Citation

@inproceedings{beeri_sigmod93,
        title = {{On the Power of Algebras with Recursion}},
        author = {Beeri, Catriel and Milo, Tova},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170090},
        url = {https://dl.acm.org/doi/10.1145/170035.170090},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.550394e-05
7,196	Typed Query Languages for Databases Containing Queries	1998	PODS	5.6764289e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,522	Unfounded Sets and Well-Founded Semantics for General Logic Programs	1988	PODS	0.00010502706
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.550394e-05
2,986	Tractable Query Languages for Complex Object Databases	1991	PODS	7.8912631e-05
4,422	Functional and Predicative programming in OODB's	1992	PODS	6.7128479e-05
8,083	The Valid Model Semantics for Logic Programs	1992	PODS	5.4911506e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	8,120	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
3	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
4	4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB
5	2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
6	6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
7	312	A Graphical Query Language Supporting Recursion	1987	SIGMOD
8	7,654	Positive Higher-Order Queries	2010	PODS
9	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
10	6,814	Expressive Power of Linear Algebra Query Languages	2021	PODS