Skip to main content
Top

2015 | OriginalPaper | Chapter

Eliminating Recursion from Monadic Datalog Programs on Trees

Authors : Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study the problem of eliminating recursion from monadic datalog programs on trees with labels taken from an infinite alphabet. We show that the boundedness problem, i.e., determining whether a datalog program is equivalent to some nonrecursive one is undecidable but the decidability is regained if the descendant relation is disallowed. Under similar restrictions we obtain decidability of the problem of equivalence to a given nonrecursive program. We investigate the connection between these two problems in more detail.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
One could consider a definition allowing additionally nodes connected by the equality relation but we expect that this would be as hard as the disconnected case e.g. the main problem we leave open in Sect. 3, the equivalence of child-only non-linear programs, becomes undecidable by the results of [18] for boolean queries.
 
2
In [18] the non-linear case required an additional exponential blow-up. However, the improvement of complexity is not caused by considering unary instead of boolean queries. It is easy to see that Theorem 1 holds also in the boolean case.
 
3
Indeed, the main idea of the undecidability proof is to use the UCQ \(\mathcal Q\) to find errors in the run of a Turing machine encoded by the program \(\mathcal P\). If the nonrecursive query \(\mathcal Q\) is unary it can only find errors close to the node X, such that \(\mathcal P(X)\).
 
4
Observe that we are only interested in the output on the goal predicate. This is why the property we consider is sometimes called the predicate boundedness [17].
 
Literature
1.
go back to reference Abiteboul, S., Bourhis, P., Muscholl, A., Wu, Z.: Recursive queries on trees and data trees. In: ICDT, pp. 93–104 (2013) Abiteboul, S., Bourhis, P., Muscholl, A., Wu, Z.: Recursive queries on trees and data trees. In: ICDT, pp. 93–104 (2013)
2.
go back to reference Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Boston (1995)MATH Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Boston (1995)MATH
3.
go back to reference Bancilhon, F., Ramakrishnan, R.: An amateur’s introduction to recursive query processing strategies. In: ACM SIGMOD, pp. 16–52 (1986) Bancilhon, F., Ramakrishnan, R.: An amateur’s introduction to recursive query processing strategies. In: ACM SIGMOD, pp. 16–52 (1986)
4.
go back to reference Benedikt, Michael, Bourhis, Pierre, Senellart, Pierre: Monadic Datalog Containment. In: Czumaj, Artur, Mehlhorn, Kurt, Pitts, Andrew, Wattenhofer, Roger (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 79–91. Springer, Heidelberg (2012) CrossRef Benedikt, Michael, Bourhis, Pierre, Senellart, Pierre: Monadic Datalog Containment. In: Czumaj, Artur, Mehlhorn, Kurt, Pitts, Andrew, Wattenhofer, Roger (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 79–91. Springer, Heidelberg (2012) CrossRef
5.
go back to reference Björklund, Henrik, Martens, Wim, Schwentick, Thomas: Optimizing Conjunctive Queries over Trees Using Schema Information. In: Ochmański, Edward, Tyszkiewicz, Jerzy (eds.) MFCS 2008. LNCS, vol. 5162, pp. 132–143. Springer, Heidelberg (2008) CrossRef Björklund, Henrik, Martens, Wim, Schwentick, Thomas: Optimizing Conjunctive Queries over Trees Using Schema Information. In: Ochmański, Edward, Tyszkiewicz, Jerzy (eds.) MFCS 2008. LNCS, vol. 5162, pp. 132–143. Springer, Heidelberg (2008) CrossRef
6.
go back to reference Bojańczyk, Mikołaj, Murlak, Filip, Witkowski, Adam: Containment of Monadic Datalog Programs via Bounded Clique-Width. In: Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki, Speckmann, Bettina (eds.) ICALP 2015. LNCS, vol. 9135, pp. 427–439. Springer, Heidelberg (2015) CrossRef Bojańczyk, Mikołaj, Murlak, Filip, Witkowski, Adam: Containment of Monadic Datalog Programs via Bounded Clique-Width. In: Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki, Speckmann, Bettina (eds.) ICALP 2015. LNCS, vol. 9135, pp. 427–439. Springer, Heidelberg (2015) CrossRef
7.
go back to reference Bonatti, P.: On the decidability of containment of recursive datalog queries - preliminary report. In: PODS, pp. 297–306 (2004) Bonatti, P.: On the decidability of containment of recursive datalog queries - preliminary report. In: PODS, pp. 297–306 (2004)
8.
go back to reference Calvanese, D., De Giacomo, G., Vardi, M.: Decidable containment of recursive queries. Theor. Comput. Sci. 336(1), 33–56 (2005)CrossRefMATH Calvanese, D., De Giacomo, G., Vardi, M.: Decidable containment of recursive queries. Theor. Comput. Sci. 336(1), 33–56 (2005)CrossRefMATH
9.
go back to reference Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases. Springer-Verlag, New York Inc (1990)CrossRef Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases. Springer-Verlag, New York Inc (1990)CrossRef
10.
go back to reference Chandra, A., Lewis, H., Makowsky, J.: Embedded implicational dependencies and their inference problem. In: STOC, pp. 342–354 (1981) Chandra, A., Lewis, H., Makowsky, J.: Embedded implicational dependencies and their inference problem. In: STOC, pp. 342–354 (1981)
11.
go back to reference Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977) Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977)
12.
go back to reference Chaudhuri, S., Vardi, M.: On the equivalence of recursive and nonrecursive datalog programs. In: PODS, pp. 55–66 (1992) Chaudhuri, S., Vardi, M.: On the equivalence of recursive and nonrecursive datalog programs. In: PODS, pp. 55–66 (1992)
13.
go back to reference Cosmadakis, S., Gaifman, H., Kanellakis, P., Vardi, M.: Decidable optimization problems for database logic programs (preliminary report). In: STOC, pp. 477–490 (1988) Cosmadakis, S., Gaifman, H., Kanellakis, P., Vardi, M.: Decidable optimization problems for database logic programs (preliminary report). In: STOC, pp. 477–490 (1988)
14.
go back to reference Cosmadakis, S., Kanellakis, P.: Parallel evaluation of recursive rule queries. In: PODS, pp. 280–293 (1986) Cosmadakis, S., Kanellakis, P.: Parallel evaluation of recursive rule queries. In: PODS, pp. 280–293 (1986)
15.
go back to reference Frochaux, A., Grohe, M., Schweikardt, N.: Monadic datalog containment on trees. In: Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management (2014) Frochaux, A., Grohe, M., Schweikardt, N.: Monadic datalog containment on trees. In: Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management (2014)
16.
go back to reference Gaifman, H., Mairson, H., Sagiv, Y., Vardi, M.: Undecidable optimization problems for database logic programs. J. ACM 40(3), 683–713 (1993)MathSciNetCrossRefMATH Gaifman, H., Mairson, H., Sagiv, Y., Vardi, M.: Undecidable optimization problems for database logic programs. J. ACM 40(3), 683–713 (1993)MathSciNetCrossRefMATH
17.
go back to reference Hillebrand, G., Kanellakis, P., Mairson, H., Vardi, M.: Undecidable boundedness problems for datalog programs. J. Log. Program. 25(2), 163–190 (1995)MathSciNetCrossRef Hillebrand, G., Kanellakis, P., Mairson, H., Vardi, M.: Undecidable boundedness problems for datalog programs. J. Log. Program. 25(2), 163–190 (1995)MathSciNetCrossRef
18.
go back to reference Mazowiecki, Filip, Murlak, Filip, Witkowski, Adam: Monadic Datalog and Regular Tree Pattern Queries. In: Csuhaj-Varjú, Erzsébet, Dietzfelbinger, Martin, Ésik, Zoltán (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 426–437. Springer, Heidelberg (2014) Mazowiecki, Filip, Murlak, Filip, Witkowski, Adam: Monadic Datalog and Regular Tree Pattern Queries. In: Csuhaj-Varjú, Erzsébet, Dietzfelbinger, Martin, Ésik, Zoltán (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 426–437. Springer, Heidelberg (2014)
20.
go back to reference Naughton, J., Sagiv, Y.: A simple characterization of uniform boundedness for a class of recursions. J. Log. Program. 10, 232–253 (1991)MathSciNetCrossRef Naughton, J., Sagiv, Y.: A simple characterization of uniform boundedness for a class of recursions. J. Log. Program. 10, 232–253 (1991)MathSciNetCrossRef
21.
go back to reference Sagiv, Y.: Optimizing datalog programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 659–698. Morgan Kaufmann, Los Altos (1988) Sagiv, Y.: Optimizing datalog programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 659–698. Morgan Kaufmann, Los Altos (1988)
23.
go back to reference Vardi, M.: The complexity of relational query languages (extended abstract). In: STOC, pp. 137–146 (1982) Vardi, M.: The complexity of relational query languages (extended abstract). In: STOC, pp. 137–146 (1982)
Metadata
Title
Eliminating Recursion from Monadic Datalog Programs on Trees
Authors
Filip Mazowiecki
Joanna Ochremiak
Adam Witkowski
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-48057-1_31

Premium Partner