article

Free access

Towards an algebraic theory of recursion

Authors:

Yannis E. Ioannidis,

Eugene WongAuthors Info & Claims

Journal of the ACM (JACM), Volume 38, Issue 2

Pages 329 - 381

https://doi.org/10.1145/103516.103521

Published: 01 April 1991 Publication History

PDF eReader

Abstract

An algebraic framework for the study of recursion has been developed. For immediate linear recursion, a Horn clause is represented by a relational algebra operator. It is shown that the set of all such operators forms a closed semiring. In this formalism, query answering corresponds to solving a linear equation. For the first time, the query answer is able to be expressed in an explicit algebraic form within an algebraic structure. The manipulative power thus afforded has several implications on the implementation of recursive query processing algorithms. Several possible decompositions of a given operator are presented that improve the performance of the algorithms, as well as several transformations that give the ability to take into account any selections or projections that are present in a givin query. In addition, it is shown that mutual linear recursion can also be studied within a closed semiring, by using relation vectors and operator matrices. Regarding nonlinear recursion, it is first shown that Horn clauses always give rise to multilinear recursion, which can always be reduced to bilinear recursion. Bilinear recursion is then shown to form a nonassociative closed semiring. Finally, several sufficient and necessary-and-sufficient conditions for bilinear recursion to be equivalent to a linear one of a specific form are given. One of the sufficient conditions is derived by embedding to bilinear recursion in an algebra.

References

[1]

AGRAWAL, R., AND DEVANBU., P. Moving selections into hnear least fixpoint queries. IEEE Trans. Knowl. Data Eng 1, 4 (Dec. i989), 424-432.

Crossref

Google Scholar

[2]

AHO, A., HOPCROFT, J., AND ULLMAN, J. D. The Design and Analysls of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

Crossref

Google Scholar

[3]

AHO, A., AND ULLMAN, J. Universality of data retrieval languages. In Proceeding of the 6th A CM Symposium on Prbwiples of Programming Languages (San Antonio, Tex., Jan. ). ACM, New York, 1979, pp. ll0-117.

Crossref

Google Scholar

[4]

APT, K. R., AND VANEMDEN, M. H. Contributions to the theory of Iogm programming. JA CM 29, 3 (July 1982), 841-862.

Crossref

Google Scholar

[5]

BACKHOUSE, R, C., AND CARRE, B. A. Regular algebra applied to path-finding problems. J. Inst. Math. Appl. 15, 2 (Apr. 1975), 161-186.

Google Scholar

[6]

BANCILHON, F. Noise evaluauon of recurswely defined relations. In M. Brodie and J. Mylopoulos, eds., On Knowledge Base Management: Integrated Artifictal bTtelligence and Database Technologies. Springer-Verlag, New York, 1986.

Crossref

Google Scholar

[7]

BANCILHON, F. MAIER, D., SAGIV, Y., AND ULLMAN., J. D. Magic sets and other strange ways to implement logic programs. In Proceedings of the 5th A CM SIGMOD-SIGA CT Symposium on Principles of Database System (Cambridge, Mass., Mar.). ACM, New York, 1986, pp. 1-15.

Crossref

Google Scholar

[8]

BANCILHON, F. AND RAMAKRISHNAN, R. An amateur's introduction to recursive query processing strategies. In Proceedings of the 1986 A CM-SIGMOD Conference on the Management of Data (Washington, D.C., May). ACM, New York, 1986, pp. 16-52.

Crossref

Google Scholar

[9]

BANCILHON, F. AND RAMAKRISHNAN, R. Performance evaluauon of data mtenswe logic proo grams, In J. Mmker, ed., Foundations of Deductive Databases and Logic Programming, Morgan-Kaufmann, San Mateo, Calif., 1988, pp. 439-517.

Crossref

Google Scholar

[10]

BEERI, C., KANELLAKIS P., BANCILHON, F., AND RAMAKRISHNAN, R. Bounds on the propagation of selection in logic programs. In Proceedings of the 6th A CM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (San Diego, Callf., Mar.). ACM, New York, 1987, pp. 214- 226.

Crossref

Google Scholar

[11]

BEERI, C., AND RAMAKRISHNAN, R. On the power of magic. In Proceedings of the 6th A CM SIGMOD-SIGACT-SIGART Symposium on Prlneiplog of Databago Sygtomg (gan Diego, Calif., Mar.). ACM, New York, 1987, pp. 269-283.

Crossref

Google Scholar

[12]

CARRE, B., Graphs and Networks, Oxford Umversity Press, Oxford, England, 1979.

Google Scholar

[13]

CERI. S., GOTTLOB, G., AND LAVAZZA, L. Translation and optimization of logic queries: The algebraic approach. In Proceedings of the 12th International VLDB Conference (Kyoto, Japan, Aug.). Morgan Kaufmann, San Mateo, Calif., 1986, pp. 395-402.

Crossref

Google Scholar

[14]

CERI, S., AND TANCA, L. Optimization of systems of algebraic equanons for evaluating datalog queries. In Proceedings 13th International VLDB Conference (Brighton, England, Sept ). Morgan Kaufmann, San Mateo, Calif., 1987, pp. 31-41

Crossref

Google Scholar

[15]

CHANDRA, A. K., AND MERLIN, P M. Optimal implementation of conjunctive queries In relational data bases. In Proceedings of the 9th Annual A CM Symposium of Theory of Computing (Boulder, Colo, May). ACM, New York, 1977, pp. 77-90.

Crossref

Google Scholar

[16]

CLOCKSIN. W. F., AND MELLISH, C. S. Programming in Prolog. Sprmger-Verlag, New York, 1981

Crossref

Google Scholar

[17]

CODD, E F. A relanonal model of data for large shared data banks. Commun. A CM 13, 6 (1970), 377-387.

Crossref

Google Scholar

[18]

COSMADAKIS, S., AND KANELLAKIS, P.arallel evatuataon of recursive rule queries. In Proceedings of the 5th ACM SIGMOD-SIGACT Symposium on Principles of Database Systems (Cambridge, Mass, Mar.) ACM, New York, 1986, pp. 280-293

Crossref

Google Scholar

[19]

DONG, G. On the Composition of Datalog Program Mappings. Unpublished Manuscript, Univ. Southern California, Nov., 1988

Google Scholar

[20]

EILENBERG, S. Autonlata, Languages, and Machines. Acedamic Press, New York, i974.

Crossref

Google Scholar

[21]

G~IFMAN, H, MAIRSON, H, SAGIV, Y., AND V&RDI, M Undecidable optlmlzanon problems for database togm programs. In Proceedings of the 2nd A CM Symposium on Logic in Computer Science (Ithaca, NY, June). ACM, New York, 1987, pp. 106-115

Google Scholar

[22]

GARDARIN, G, AND DE MAINDREVILLE, C. Evaluation of database recurswe logic programs as recurrent funcnon series In Proceedings of the 1986 A CM-SIGMOD Conference of the Management of Data (Washington, D.C., May). ACM, New York, 1986, pp. 177-186.

Crossref

Google Scholar

[23]

GARD4RIN, G.Magic funcnons: A technique to optimize extended datalog recursxve programs. In Proceedings of the 13th Internanonal VLDB Conference (Brighton, England, Sept.). Morgan Kaufmann, San Mateo, Calif., 1987, pp. 21-30.

Crossref

Google Scholar

[24]

H aN, J, ~ND Lu, HSome performance results on recursive query, processing m retatxonal database s)stems In Proceedings of the 2nd International Conference on Data Engineering (Los Angeles, Calif., Jan.). IEEE Computer Society Press, Washington, D C, 1986. pp. 533-539

Crossref

Google Scholar

[25]

HENSCHEN, L., AND NAQVI, S. On compiling queries in recurswe first-order databases JACM 31, 1 (Jan. 1984), 47-85

Crossref

Google Scholar

[26]

HERSTEIN, I N. Topics ltl Algebra. Wiley, New York, N Y., 1975.

Google Scholar

[27]

IOANNID{S, Y. E.On the computation of the transitive closure of relational operators. In Proceedings of the 12th Internanonal VLDB Conference (Kyoto, Japan, Aug ). Morgan Kaufmann, San Mateo, Calif., 1986, pp. 403-411

Crossref

Google Scholar

[28]

IOANNIDIS, Y. E. A time bound on the materlahzatlon of some recursively defined views. Algorlthmtca 1, 4 (Oct. 1986), 361-385.

Google Scholar

[29]

IOANNIDIS. Y.E. Commutatlvlty and its role in the processing of Imear recurslon. J. Logic Prog., to appear.

Crossref

Google Scholar

[30]

IOANNIDIS. Y. E, AND WONG, E An algebraic approach to recurslve inference. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S.C., Apr.). BenJamin/Cummings, Redwood City, Calif., 1987, pp. 295-309.

Google Scholar

[31]

IO&NNIDIS, Y. E., AND WONG, E. Query optimization by simulated annealxng. In Proceedings of the 1987 ACM-SIGMOD Conference on the Management of Data (San Francisco, Calif., May). ACM, New York, 1987, pp. 9-22

Crossref

Google Scholar

[32]

KIFER, M., AND LOZINSKII, E.On compile time query optimization in deductive databases by means of static filtering AC~t Trans. Datab. S;y6t. I5, 3 ~Sept. 1990), 385-420.

Crossref

Google Scholar

[33]

LASSEZ, J L. &ND MAHER, M. J.Closures and fairness in the semantics of programming logm Theoret. Comput. Scl. 29 (1984), 167-184.

Google Scholar

[34]

LEHMANN, D J Algebraic structures for transitive closure. Theoret. Cornput. Scl. 4 (1977), 59-76.

Google Scholar

[35]

MAHER, M. J Semantics of Logic Program. Ph D dissertation. Dep. Comput. Sci., Univ Melbourne, Parkville, Australia (also available as Tech. Rep No. M85/I4), 1985.

Google Scholar

[36]

NAUGHTON, J.Compiling separable recur,~lonb. In Proceedings of the 1988 A CM-SIGMOD Conference on the Management of Data (Chicago, Ill, June). ACM, New York, 1988, pp 312-319.

Crossref

Google Scholar

[37]

NAUGHTON, J. Minimizing function-free recursive inference rules. JACM 36, 1 (Jan. 1989), 69-91

Crossref

Google Scholar

[38]

NAUGHTON, J. Data independent recursion in deductive databases. J. Cornput. Syst. Sci. 38, 2 (Apr. 1989), 259-289.

Google Scholar

[39]

NAUGHTON, J. F., RAMAKRISHNAN, R., SAGIV, Y., AND ULLMAN, J. D. Factoring can reduce arguments. In Proceedings of the 15th International VLDB Conference (Amsterdam, The Netherlands, Aug.). Morgan Kaufmann, San Mateo, Calif., 1989, pp. 173-182

Crossref

Google Scholar

[40]

RAMAKRISHNAN, R., BEERI, C., AND KRISHNAMURTHY, R. Optimizing existential datalog queries. In Proceedings of the 7th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Austin, Tex., Mar.). ACM, New York, 1988, pp. 89-102.

Crossref

Google Scholar

[41]

RAMAKRISHNAN, R., SAGlV, Y, ULLMAN, J. D., AND VARDI, M. Proof tree transformation theorems and their applications Proceedings of the 8th A CM SIGACT-SIGMOD-SIGART Symposium on Pnnciples of Database Systems (Philadelphia, Pa., Mar.). ACM, New York, 1989, pp. 172-181.

Crossref

Google Scholar

[42]

ROSENTHAL, A., HEILER, S., DAYAL, U., AND MANOLA, F. Traversal recursion: A pracncal approach to supporting recursive applications. In Proceedings of the 1986 A CM-SIGMOD Conference on the Management of Data (Washington, DC, May). ACM, New York, t986, pp. 166-176.

Crossref

Google Scholar

[43]

SAcca, D., AND ZANIOLO, C. On the implementation of a simple class of togac queries for databases. In Proceedings of the 5th A CM SIGMOD-SIGACT Symposium on Principles of Database Systems (Cambridge, Mass., Mar.) ACM, New York, 1986, pp. 16-23.

Crossref

Google Scholar

[44]

SACCA, D., AND ZANIOLO, C. The generalized counting method for recurswe logic queries. In Proceedings of the International Conference on Database Theory (Rome, Italy, Oct.). Springer-Verlag, Berlin, 1986, pp. 31-53.

Crossref

Google Scholar

[45]

SAGIV, Y Optimizing datalog programs. In Proceedings of the 6th A CM SIGACT- SIGMOD-SIGART Symposium on Prmctples of Database System (San Daego, Calif., Mar.). ACM, New York, 1987, pp. 349-362.

Crossref

Google Scholar

[46]

SAGIV, Y., AND YANNAKAKIS, M. Equivalences among relanonal expressions with the union and difference operator. JACM 27, 4 (Oct. 1980), pp. 633-655.

Crossref

Google Scholar

[47]

S&R~IYA, Y. P.Lmearizing nonlinear recursions in polynomial time In Proceedings of the 8th A CM SIGACT-SIGMOD-StGART Symposium on Principles of Database Systems (Philadelphia, Pa., Mar.). ACM, New York, 1989, pp. 182-189.

Crossref

Google Scholar

[48]

SCHAFER, R. D. An Introduction to Nonassociative Algebras. Academic Press, Orlando, Fla., 1966.

Google Scholar

[49]

SHAPIRO, S., AND McKAY, D. Inference with recursive rules. In Proceedings of the 1st Annual National Conference on Artificial intelhgence (Palo Alto, Calif., Aug.). 1980, pp. 151-153.

Google Scholar

[50]

SHMUELI, O. Decidability and expressiveness aspects of logic queries. In Proceedings of the 6th A CM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (San Diego, Calif., Mar ). ACM, New York, 1987, pp. 237-249.

Crossref

Google Scholar

[51]

T~,RSKI, A. A lattice theoretical fixpomt theorem and its applications. Pacific d. Math. 5 (1955), pp. 285-309.

Google Scholar

[52]

VALDURIEZ, P. AND BORAL, H. Evaluation of recursive queries using join indices. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S.C., Apr.). Benjamin/Cummings, Redwood City, Calif., 1987, pp. 271-293.

Google Scholar

[53]

VALDURIEZ, P., AND KHOSHAFIAN, S. Transitive closure of transitively closed relations, in Proceedings of the 2nd International Conference on Expert Database Systems (Tysons Corner, Va., Apr.). Benjamin/Cummings, Redwood City, Calif., 1989, pp. 377-400.

Google Scholar

[54]

M. H. VANEMDEN, AND KOWALSKI, R. A. The sematics of predicate logic as a programming language. JACM 23, 4 (Oct. 1976). 733-742.

Crossref

Google Scholar

[55]

VIEILLE, L. Recurslve axioms in deductive databases: The query/subquery approach. In Proceedings of the 1st International Conference on Expert Database Systems (Charleston, S.C., Apr.) Benjamin/Cummings, Redwood City, Calif., 1987, pp. 253-267.

Google Scholar

[56]

ZHANG, W., AND YU, C. T. A necessary con&tion for a doubly recursive rule to be equivalent to a linear recursive rule. In Proceedings of the 1987 ACM-SIGMOD Conference on the Management of Data (San Francisco, Calif., May). ACM, New York, 1987, pp. 345-356.

Crossref

Google Scholar

[57]

ZHANG, W., Yu, C. T., AND TROY, D. A necessary and sufficient condition to linearize doubly recursive programs in logic databases. ACM Trans. Datab. Syst. 15, 3 (Sept, 1990). 459-482.

Crossref

Google Scholar

Cited By

View all

Marcinkowski JOrda M(2024)Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.Proceedings of the ACM on Management of Data10.1145/36516042:2(1-24)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651604
Antić C(2024)Sequential composition of propositional logic programsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-024-09925-x92:2(505-533)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10472-024-09925-x
Chen Y(2023)Graph traversal and top-down evaluation of logic queriesJournal of Computer Science and Technology10.1007/BF0294662013:4(300-316)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02946620
Show More Cited By

Index Terms

Towards an algebraic theory of recursion

Recommendations

Towards a Behavioral Algebraic Theory of Logical Valuations
Logic, Language, Information and Computation

Logical matrices are widely accepted as the semantic structures that most naturally fit the traditional approach to algebraic logic. The behavioral approach to the algebraization of logics extends the applicability of the traditional methods of ...
Monteiro's algebraic notion of maximal consistent theory for Tarskian logics
Abstract
Antonio Monteiro gave a characterization of maximal congruences in certain semisimple varieties in order to present a representation theorem for them. Under specific conditions, this theorem can be presented with the same proof for ...
The Recursion Scheme from the Cofree Recursive Comonad

We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on the cofree comonad on F in a similar fashion, this scheme allows ...

Reviews

Reviewer: Pradip K. Srimani

Two distinct approaches to designing queries and investigating their implementation and optimization in relational database systems exist: relational calculus and relational algebra. These two approaches are equivalent in their expressive power (that is, both are complete), but each has distinct advantages and disadvantages. Normally recursion is not allowed in relational algebra. Recursion and consequently optimization of recursive queries are studied mostly under the formalism of relational calculus (first-order logic). On the other hand, algebraic manipulation of queries offers useful insights into different inherent properties of queries and alternative query processing strategies. Recent studies show that recursion can be handled in the framework of relational algebra, and in some cases we get optimizations that cannot be trivially obtained in a logic-based setting. The purpose of this paper is to develop a detailed and rigorous algebraic theory of recursive queries and their optimization. The authors consider Horn clause programs and provide an abstract model of the query optimization process to discuss their results. They have developed a number of important, deep mathematical results. They show that all relational algebra operators form a closed semiring and that an immediate linear recursive query is answered by solving an equation in an explicit form. They consider mutual linear recursion, bilinear recursion, and multilinear recursion in great detail and develop different interesting mathematical properties related to optimization of these kinds of queries. They compare the algebraic and the calculus-based approaches in the light of their new results and discuss some new directions for further research. The paper is detailed and mathematical but self-contained. It also contains an impressive list of references to most of the recent works in related areas. You need to be mathematically sophisticated to make complete sense of this paper, but if you are a database theorist and interested in query optimization in an algebraic setting, this paper is a must read.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 38, Issue 2

April 1991

260 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/103516

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1991

Published in JACM Volume 38, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
668
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Marcinkowski JOrda M(2024)Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.Proceedings of the ACM on Management of Data10.1145/36516042:2(1-24)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651604
Antić C(2024)Sequential composition of propositional logic programsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-024-09925-x92:2(505-533)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10472-024-09925-x
Chen Y(2023)Graph traversal and top-down evaluation of logic queriesJournal of Computer Science and Technology10.1007/BF0294662013:4(300-316)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02946620
Chen Y(2023)Magic sets revisitedJournal of Computer Science and Technology10.1007/BF0294315412:4(346-365)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02943154
Sato TInoue KSakama C(2018)Abducing relations in continuous spacesProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304930(1956-1962)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304930
Christiansen HMartinenghi D(2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/2369336.236933871:4(371-417)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.5555/2369336.2369338
Christiansen HMartinenghi D(2006)On Simplification of Database Integrity ConstraintsFundamenta Informaticae10.5555/1227517.122751971:4(371-417)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.5555/1227517.1227519
Du XIshii N(2006)An algebraic rewriting theorem of multiple linear recursions and its applicationsDatabase and Expert Systems Applications10.1007/BFb0049129(313-322)Online publication date: 1-Feb-2006
https://doi.org/10.1007/BFb0049129
Zurek TThanisch P(2005)Strategies for parallel linear recursive query processingRules in Database Systems10.1007/3-540-60365-4_129(211-229)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-60365-4_129
Feder TSaraiya Y(2005)Decidability and undecidability of equivalence for linear Datalog, with applications to normal-form optimizationsDatabase Theory — ICDT '9210.1007/3-540-56039-4_49(297-311)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-56039-4_49
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Towards a Behavioral Algebraic Theory of Logical Valuations

Monteiro's algebraic notion of maximal consistent theory for Tarskian logics

The Recursion Scheme from the Cofree Recursive Comonad

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations