Bounds in the propagation of selection into logic programs. (English) Zbl 0796.68054

Summary: We consider the problem of propagating selections into logic programs (i.e., recursive Horn clause programs). In particular, we study the class of chain programs and formalize selection propagation on such a logic programs as: the task of finding an equivalent program containing only monadic derived predicates. Selection propagation is always possible for database programs (i.e., first-order formula programs) and is often a desirable optimization. We show that the situation is qualitatively different for logic programs. We associate a context-free language \(L(H)\) with every chain program \(H\). We show that, given \(H\), propagating a selection involving some constant is possible iff \(L(H)\) is regular and therefore undecidable. We also show that propagating a selection of the form \(p(X,X)\) is possible iff \(L(H)\) is finite and therefore decidable. We demonstrate the connection of these two cases, respectively, with the weak monadic second-order theory of one successor and with monadic generalized spectra. We further clarify the analogy between chain programs and context-free languages from the point of view of program equivalence, first-order expressibility over finite structures, and selection propagation heuristics.


68N17 Logic programming
68P15 Database theory
68Q45 Formal languages and automata
68N01 General topics in the theory of software
Full Text: DOI


[1] Afrati, F.; Papadimitridu, C., The parallel complexity of simple chain queries, (Proceedings, 6th PODS (1987), ACM), 210-214
[2] Aho, A. V.; Ullman, J. D., Universality of data retrieval languages, (Proceedings, 6th POPL (1979), ACM), 110-117
[3] Ajtai, M.; Fagin, R., Reachability is harder for directed than for undirected graphs, (Proceedings, 29th FOCS. Proceedings, 29th FOCS, IEEE (1988)), 358-367 · Zbl 0708.03016
[4] Apt, K. R.; van Emden, M. H., Contributions to the theory of logic programming, Assoc. Comput. Mach., 29, No. 4, 841-862 (1982) · Zbl 0483.68004
[5] Bancilhon, F.; Maier, D.; Sagiv, Y.; Ullman, J. D., Magic sets and other strange ways to implement logic programs, (Proceedings, 5th PODS (1986), ACM), 1-14
[6] Bancilhon, F.; Ramakrishnan, R., An amateur’s introduction to recursive query processing strategies, (Proceedings, 86 Sigmod (1986), ACM), 16-52
[7] Beeri, C.; Ramakrishnan, R., On the power of magic, (Proceedings, 6th PODS (1987), ACM), 269-283
[8] Blattner, M., The unsolvability of the equality problem for sentential forms of context free grammars, J. Comput. System Sci., 7, No. 5, 463-468 (1973) · Zbl 0273.68054
[9] Buchi, J. T., Weak second order arithmetic and finite automata, Z. Math. Logik, 6, 66-92 (1960) · Zbl 0103.24705
[10] Chandra, A. K.; Harel, D., Horn clause programs and generalizations, J. Logic Programm., 2, 1-15 (1985) · Zbl 0583.68058
[11] Chandra, A. K.; Harel, D., Structure and complexity of relational queries, J. Comput. System Sci., 25, No. 1, 99-128 (1982) · Zbl 0511.68073
[12] Cosmadakis, S.; Kanellakis, P., Parallel evaluation of recursive rule queries, (Proceedings, 5th PODS (1986), ACM), 280-293
[13] Cosmadakis, S. S.; Gaifman, H.; Kanellakis, P. C.; Vardi, M. Y., Decidable optimization problems for database logic programs, (Proceedings, 20th STOC (1988), ACM), 477-490
[14] Derougemont, M., Uniform definability of finite structures with successor, (Proceedings, 16th STOC (1984), ACM), 409-417
[15] Elgot, C., Decision problems of finite automaton design and related arithmetics, Trans. Amer. Math. Soc., 98, 21-51 (1961) · Zbl 0111.01102
[16] Fagin, R., Monadic generalized spectra, Z. Math. Logik, 21, 89-96 (1975) · Zbl 0317.02054
[17] Gaifman, H.; Mairson, H.; Sagiv, Y.; Vardi, M. Y., Undecidable optimization problems for database logic programs, (Proceedings, 2nd LICS (1987), IEEE), 106-115 · Zbl 0785.68021
[18] Gaifman, H.; Vardi, M. Y., A simple proof that connectivity of finite graphs is not first order definable, Bulletin EATCS, 26, 44-45 (1985)
[19] Henschen, L. J.; Naqvi, S. A., On compiling queries in recursive first-order databases, Assoc. Comput. Mach., 31, No. 1, 47-85 (1984) · Zbl 0629.68095
[20] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[21] Moschovakis, Y. N., Elementary Induction on Abstract Structures (1974), North-Holland: North-Holland Amsterdam · Zbl 0307.02003
[22] Naughton, J. F., One-sided recursions, (Proceedings, 6th PODS (1987), ACM), 340-349
[23] Sacca, D.; Zaniolo, C., On the implementation of a simple class of logic queries for databases, (Proceedings, 5th PODS (1986), ACM), 16-23
[24] Sagiv, Y., Optimizing datalog programs, (Proceedings, 6th PODS (1987), ACM), 349-362
[25] Shmueli, O., Decidability and expressiveness aspects of logic queries, (Proceedings, 6th PODS (1987), ACM), 237-249
[26] Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem of second order logic, Math. Systems Theory, 2, No. 1, 57-81 (1968) · Zbl 0157.02201
[27] Ullman, J. D., Principles of Database Systems (1983), Cpmput. Sci. Press: Cpmput. Sci. Press Rockville, MD
[28] Ullman, J. D., Implementation of logical query languages for databases, ACM Trans. Database Systems, 10, 289-321 (1985) · Zbl 0573.68060
[29] Ullman, J. D.; Van Gelder, A., Parallel complexity of logical query programs, Algorithmica, 3, No. 1, 5-42 (1988) · Zbl 0646.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.