Iryna Glushko



Generalization of the Classical Result of Codd-Lacroix-Pirotte

pdf PDF


The paper is focused on some theoretical questions of the Database Theory. The result which concerns equivalence of table algebra for infinite tables and corresponding relational calculi is presented. This result generalizes the classical result about the equivalence of Codd’s relational algebra and tuple (domain) relation calculus. Concept of table (relation) is considered in terms of nominal sets. Under relation is understood any set of tuples (with common scheme), in particular infinite. Furthermore only one universal domain is considered. The classical relational calculi are filled up by functional and predicate signatures on the universal domain (while usually consider only binary predicates and functional signature is generally empty).


Relation databases, tuple relation calculus, domain relation calculus, table algebra, nominal sets


[1] E.F. Codd, A Relational Model of Data for Large Shared Data Banks, Comm. of ACM, 13(6), 1970, рр. 377-387.

[2] E.F. Codd, Relational Сompleteness of Data Base Sublanguages, Data Base Systems, Proceedings of 6th Courant Computer Science Symposium, 1972, рр. 65-93.

[3] M. Lacroix, A. Pirotte, Domain-oriented Relational Languages, Proceedings of 3rd Int. Conf. on Very Large Data Bases, 1977, рр. 370-378.

[4] A. Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, J. ACM, 29(3), 1982, рр. 699-717.

[5] J.D. Ullman, Principles of database systems, Rockville, Maryland: Computer Science Press, 1982.

[6] D. Maier, The theory of relational databases, Rockville, Maryland: Computer Science Press, 1983.

[7] V.N. Redko, Yu.J. Borona, D.B. Buy, S.A. Poliakov, Reliatsiini bazy danykh: tablychni alhebry ta SQL-podibni movy, Kyiv, Vydavnychyi dim «Akademperiodyka», 2001. (in Ukrainian)

[8] D. Buy, I. Glushko, Generalized Table Algebra, Generalized Tuple Calculus and Theirs Equivalence, Proceedings of CSE 2010 International Scientific Conference on Computer Science and Engineering, 2010, pp. 231-238.

[9] E. Mendelson, Introduction to mathematical logic, Chapman & Hall, London, 1997.

Cite this paper

Iryna Glushko. (2016) Generalization of the Classical Result of Codd-Lacroix-Pirotte. International Journal of Computers, 1, 112-119


Copyright © 2017 Author(s) retain the copyright of this article.
This article is published under the terms of the Creative Commons Attribution License 4.0