Stavros Cosmadakis
Moshe Vardi
ABSTRACT
Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program Π, then Π is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show here that boundedness is decidable for monadic programs, i.e., programs where the recursive predicates are monadic (the non-recursive predicates can have arbitrary arity). Underlying our results are new tools for the optimization of Datalog programs based on automata theory and logic. In particular, one of the tools we develop is a theory of two-way alternating tree automata. We also use our techniques to show that containment for monadic programs is decidable.
- AP87.Afrati, F., Papadimitriou, C.H.: The parallel complexity of simple chain queries. Proc. t;th A UM Syrup. on Principles of Database Systems, San Diego, 1987, pp. 210-213. Google Scholar
Digital Library
- ASU79.Aho, V.tI., Sagiv, Y., tJll{{}an, .!.!).: l,;r ficient optimization or a class of relational exprcsslons. A CM 7Yans. on Database Systems 4(I979), l'P. ,135-454. Google ScholarDigital Library
- AU79.Aho, V.II., l. Jllman, J.D.: Universality of data retrieval languages, l'roc. 6th AUM Syrup. on Principles of Programming Lan- .quages, 1979, pp. 110 117. Google ScholarDigital Library
- BKBR87.Beeri, C., Kancllakis, l'.C., Bancilhon, F., Ramakrishnan, R.: Bounds on the propagation of selection into logic programs, l'roc. 6th A CM Sltmp. on Principles of Database Systems, San Diego, 1987, pp. 214-226. Google ScholarDigital Library
- BL80.Brzozowski, J.A., Leiss, E.: On equations for regular languages, finite automata, and sequential networks. Theoretical Computer Science 10(1980), pp. 19-35.Google ScholarCross Ref
- BR86.Bancilhon, F., Ramakrishnan, R.: An amateur's introduction to recursive query processing strategies. Proc. A CM Conf. on Management of Data, Washington, 1986, pp. 16-52. Google ScholarDigital Library
- Ch81.Chandra, A.K.: Programming primitives for database languages, l'roc. 8th A UM Syrup. on Principles of Pro~ramminq Languages, Williamsburg, 1981, pp. 50 62. Google ScholarDigital Library
- CH80.Chandra, A.K., Harel, D.: Computable queries for rclati(,nal databases. J. Computer and Systems Sciences21(1980), pp. 156 178.Google Scholar
- CH82.Chandra, A.K., llarel, I).: Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99- 128.Google ScholarCross Ref
- CH85.Chandra, A.K., Hard, D.: ltorn-clause queries and generalizations. J. Logic Programmint? 1(1985), pp. 1-15.Google Scholar
- CK86.Cosmadakis, S.S., Kanellakis, P.C.: Parallel evaluation of recursive rule queries. Proc. 5th A CM Syrup. on Principles o} Database Systems, Cambridge, 1986, pp. 280-293. Google ScholarDigital Library
- CKS81.Chandra, A.K., Kozen, D.C., Stockmeyer, {,.J.: Alternation. J. ACM 28(1981), pp. 114--133. Google ScholarDigital Library
- CM77.Chandra, A.K., Merlin, I'.M.: Optimal implementation of conjunctive queries in relational databases. Proc. 9th A CM Syrup. on Theory of Computing, Boulder, 1977, pp. 77- 90. Google ScholarDigital Library
- Co74.Cook, S.A.: An observation on timestorage trade off. J. Computer and System Sciences 9(1974), pp. 308-316.Google ScholarDigital Library
- Fa75.Fagin, R.: Monadlc generalized spectra. Zeitschr. J. math. Logik und Grunlagen d. Math. 21(1975), pp. 89-96.Google Scholar
- Ga82.Gaifman, H.: On local and non-local properties. Proc. Logic Colloquium (J. Sterne, ed.), North-llolland, 1981, pp. 105--132.Google Scholar
- GM78.Ga!laire, II., Minker, J.: Logic and Databases. Plenum I'ress, 1978. Google ScholarDigital Library
- GMSV87.Gaifman, II., Mairson, II., Sagiv, Y., Vardl M.Y.: Undecidable optimization problems for database logic programs. Proc. ~nd IEEE Syrup. on LotTic in Computer Science, Ithaca, 1987, pp. 106-115.Google Scholar
- GR82.Gurevich, Y., Harrington, L.: Trees, automata, and games. Proc. Idth ACM Syrup. on Theory of Computing, San Francisco, 1982, pp. 60-65. Google ScholarDigital Library
- HN84.I{enschen, L.J., Naqvi, S.A.: On compiling queries in recursive first-order databases. J. A CM 31 (1984), pp. 4 7-85. Google ScholarDigital Library
- Im86.immerman, N.: Relational queries computable in polynomial time. Information and Control 68(1986), pp. 86-104. Google ScholarDigital Library
- Io85.loannidis, Y.E.: A time bound on the materialization of some recursively defined views. Proc. l ! th lnt 'i Conf. on Very Large Data Bases, Stockholm, 1985, i)i). 219226.Google Scholar
- Ka86.Kanellakis, P.C.: Logic programming and parallel complexity, in Foundations o! Deductive Databases and Logic Programming, J. Minker ed., (to appear). Google ScholarDigital Library
- Mo74.Moschovakis, Y.N.: Elementary induction on Abstract Structures. North Holland, 1974. Google ScholarDigital Library
- MS87.Muller, D.E., Schupp, P.E.: Alternating automata on infinite trees. Theoretical Corn. puter Science 54(1987), pp. 267-276. Google ScholarDigital Library
- MUV84.Maler, D., Ullman, J.D., Vardl, M.Y.: On the foundations of the universal relation model. A CM Trans. on Database Systems 9(1984), pp. 283-308. Google ScholarDigital Library
- MW88.Mater, D., Warren, D.S.: Computing with Logic' Logic Programming with Prolog, Benjamin Cummings, 1988. Google ScholarDigital Library
- Na86.Naughton, J.F.: I)ata independent recursion in deductive databases. Proc. 5th A CM Syrup. on Principles of Database Systems, Cambridge, 1986, pp. 267-279. Full version - Stanford University Technical Report STAN- CS-86-1102, to appear in J. Computer and System Sciences. Google ScholarDigital Library
- NS87.Naughton, J.F., Sagiv, Y.: A decidable class of bounded recursions. Proc. 6th A UM Syrup. on Principles of Database Systems, San Diego, 1987, pp. 227-236. Google ScholarDigital Library
- RS59.R~bin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Research and Development, 3(1959), Pl:'. 114-125.Google Scholar
- Sa85.Saglv, Y.' On computing restricted projections of representative instances. Proc. 4th ACM Syrup. on Principles of Database Systems, Portland, 1985, pp. 171-180. Google ScholarDigital Library
- Sh59.Shepherdson, J.C.: The reduction o{ twoway automata to one-way automata. IBM d. Research and Development, 3(1959), pp. 199- 201.Google ScholarDigital Library
- Sh87.Shmueli, O.: Decidability and expressiveness aspects of logic queries. Proc. 6th ACM Syrup. on Principles o} Database Systems, San Diego, 1987, pp. 237-249. Google ScholarDigital Library
- St82.Streett, R.S.: Propositional dynamic logic of looping and converse is elementarily decidable. Information and Contro~ 54(1982), pp. 121-141.Google ScholarCross Ref
- Ul85.unman, J.D.: Implementation of logical query languages for databases. A CM Trans. on Database Systems 10(1985), pp. 289-321. Google ScholarDigital Library
- UV86.Ullman, J.D., Van GeldLer, A.: Parallel complexity of logical query programs. Proc. ~7th IEEE Syrup. on Foundations of Computer Science, ~}'oronto, 1986, pp. 438 454.Google ScholarDigital Library
- Va82.Vardi, M.Y.: '!~he complexity of relati<~nal query languages. Proc. Idlh A CM .qy,~p. o~ Theory of Computing, San Francisco, 1982, pp. 137-146. Google ScholarDigital Library
- Va88.Vardi, M.Y.: Decidability and Undecidablity Results for Boundedness of Linear Recursive Queries. Proc. 7th A CM Sym,p. on Principles of Database Systems, Austin, March 1988. Google ScholarDigital Library
- Zl76.Zloof, M.: Query-by-Example: Operations on the Transitive Closure. IBM Research Report RC5526, 1976.Google Scholar
Index Terms
- Decidable optimization problems for database logic programs
Recommendations
Decidable fragments of many-sorted logic
Many natural specifications use types. We investigate the decidability of fragments of many-sorted first-order logic. We identified some decidable fragments and illustrated their usefulness by formalizing specifications considered in the literature. ...
Comments