Abstract
We propose a technique for handling recursive axioms in deductive databases. More precisely, we solve the following problem:
Given a relational query including virtual relations defined from axioms (Horn clauses, with variables in the conclusion predefined in the hypotheses), which can be recursive, how to translate this query into arelational program, i. e. a set of relational operations concerning only real relations (not virtual). Our solution has the following properties:
-
• the program to evaluate the query always terminates,
-
• the relational program is produced by a pure compilation of a source query and of the axioms, and is independent of the data values (there is no run-time),
-
• the relational operations are optimized: theyfocus towards the computation of the query, without needless computations.
As far as we know, the Alexander Method is the first solution exhibiting all these properties. This work is partly funded by Esprit Project 112 (KIMS).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bancilhon, Maier, Sagiv, Ullman, “Magic Sets and other strange ways to implement Logic Programming,” MCC Technical Report number DB 121–85, Oct., 1985.
Chakravarthy, U. S., Minker J. and Tran D., “Interfacing predicate logic languages and relational,” Proc. 1st Int. Conf. on Logic Programming, Marseille, 1982.
Chang, “Deduce 2. Further investigations of deduction in Relational Databases,” in Ref. 4), pp. 201–236.
Gallaire, H. and Minker, J. (eds.),Logic and Databases, Plenum Press New York, 1978.
Henschien, L. J. and Naqui, S. A., “On compiling queries in Recursive first order Databases,”CACM, Jan., 1984.
Kerisit, “Preuve de la Methode d’Alexander par une approche algébrique,” BULL rapport interne, May 1986.
Lozinskii, “Evaluating queries in Deductive Databases by generating” IJCAI, 1985.
Marque-Pucheux, G., “Interfacing Prolog and Relational Data Base Management System,”ICOD-2, Sept. 1983.
Nicolas, J. M. and Yazdanian, K., “An outline of B.D.G.E.N.: a deductive DBMS,”Information Processing, IFIP, 1983.
Pugin, J. M. and Jamier, R., “Le Moteur d’Inférence BOUM,”Rapport de DEA, Ecole Centrale de Paris, Juin, 1983.
Reiter, R., “Deductive Question-Answering on relational Databases,” inLogic and Databases, Plenum Press, pp 149–177, 1978.
Shapiro, J. D.,Principles of Database Systems — 2nd Edition, Computer Science Press, 1982.
Vieille, L., “Recursive Axioms in Deductive Databases. The Query-Subquery approach,” Expert Database System Conference, Charleston, Apr. 1986.
Author information
Authors and Affiliations
Additional information
This work is partly funded by Esprit Project 112 (KIMS).
About this article
Cite this article
Rohmer, J., Lescoeur, R. & Kerisit, J.M. The Alexander Method — A technique for the processing of recursive axioms in deductive databases. New Gener Comput 4, 273–285 (1986). https://doi.org/10.1007/BF03037407
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03037407