The Monadic Second-order Logic Evaluation Problem on Finite Colored Trees: a Database-theoretic Approach

• Autorzy: Foustoucos E. , Kalantzi L.
• Języki publikacji: EN

Abstrakty

EN

We model the monadic second-order logic (MSO) evaluation problem on finite colored trees in a purely database theoretic framework, based on the well-known MSO-automata connection: we reduce the problem to an acyclic conjunctive query evaluation problem on the one hand and to a monadic datalog evaluation problem on the other hand. This approach offers the possibility to solve the MSO problem using optimized evaluation methods for relational algebra expressions and for datalog programs (such as Yannakakis algorithm [27] and the rewriting method using resolutionbased filtering referred to as "magic sets" method in [3]): we use these methods for evaluating our queries and giving estimates of their complexity. This is the first time, to our knowledge, that a solution to the MSO evaluation problem related to relational algebra is given; furthermore, thanks to this reduction, we prove that the automata-based algorithm given in [8] constitutes a particular "instance" of Yannakakis algorithm. Besides the optimized database methods that we propose for solving the MSO evaluation problem, our results prove that MSO-definable queries over colored trees are datalog-definable; this result subsumes the corresponding result in [12] which states that unary MSO queries are monadic datalog-definable and it also subsumes the well-known result that any MSO-definable class of trees is monadic datalog-definable.

Słowa kluczowe

EN

Monadic second-order logic (MSO) evaluation problem; MSO queries; tree automata; datalog queries; acyclic conjunctive queries; Yannakakis algorithm; datalog rewriting algorithms; definability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 3
• Strony: 193--231
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Foustoucos E.

autor

Kalantzi L.

• MPLA, Department of Mathematics National and Capodistrian University of Athens Panepistimiopolis, 15784 Athens, Greece,

Bibliografia

• [1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases, Addison-Wesley, 1995.
• [2] Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs, Journal of Algorithms, 12, 1991, 308-340.
• [3] Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.: Magic sets and other strange ways to implement logic programs, Proc. 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, ACM Press, 1986.
• [4] Bidoit, N.: Negation in rule-based database languages: a survey, Theoretical Computer Science, 78(1), 1991, 3-83.
• [5] Courcelle, B.: Graph Rewriting: An Algebraic and Logic Approach, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier Science Publishers, 1990, 193-242.
• [6] Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, 109, 1993, 49-82.
• [7] Doner, J.: Tree Acceptors and some of their Applications, Journal of Computer and System Sciences, 4, 1970, 406-451.
• [8] Flum, J., Frick, M., Grohe,M.: Query Evaluation via tree decompositions, Journal of the ACM, 49(6), 2002, 716-752.
• [9] Foustoucos, E., Kalantzi, L.: MSO querying over trees via datalog evaluation, Proc. 5th Panhellenic Logic Symposium, July 2005.
• [10] Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited, Annals of Pure and Applied Logic, 130(1-3), 2004, 3-31.
• [11] Frick, M., Grohe, M., Koch, C.: Query Evaluation on Compressed Trees, Proc. 18th Annual IEEE Symposium on Logic in Computer Science (LICS'03), June 2003.
• [12] Gottlob, G., Koch, C.: Monadic datalog and the Expressive Power of Web Information Extraction Languages, Journal of the ACM, 51(1), 2004, 74-113.
• [13] Gottlob, G., Pichler, R., Wei, F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning, Proc. AAAI 2006, AAAI Press, 2006.
• [14] Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures with bounded treewidth, Proc. 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2007.
• [15] Gottlob, G., Pichler, R., Wei, F.: Abduction with bounded treewidth: from theoretical tractability to practically efficient computation, Proc. AAAI 2008, AAAI Press, 2008.
• [16] Grohe,M., Schweikardt, N.: Comparing the succinctness of monadic query languages over finite trees, Proc. 12th Annual Conference of the European Association for Computer Science Logic (CSL'03), volume 2803 of Lecture Notes in Computer Science, Springer, 2003.
• [17] Gurevitch, Y.: Monadic Second-Order Theories, in: Model-Theoretics Logics (J. Barwise, S. Feferman, Eds.), Springer-Verlag, 1985, 479-506.
• [18] Makowsky, J. A.: Algorithmic uses of the Feferman-Vaught theorem, Annals of Pure and Applied Logic, 126(1-3), 2004, 59-213.
• [19] Neven, F., Schwentick, T.: Query Automata, Proc. 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1999.
• [20] Neven, F., Schwentick, T.: Automata- and logic-based pattern languages for tree-structured data, in: Semantics in Databases, volume 2582 of Lecture Notes in Computer Science, Springer, 2001, 160-178.
• [21] Niehren, J., Planque, L., Talbot, J., Tison, S.: N-ary queries by tree automata, Proc. 10th International Symposium on Database Programming Languages (DBPL'05), volume 3774 of Lecture Notes in Computer Science, Springer, 2005.
• [22] Reinhardt, K.: The complexity of translating logic to finite automata, in: Automata, Logics, and Infinite Games (E. Gradel, W. Thomas, T. Wilke, Eds.), volume 2500 of Lecture Notes in Computer Science, Springer-Verlag, 2002, 235-242.
• [23] Thatcher, J., Wright, J.: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-order Logic, Mathematical Systems Theory, 2(1), 1968, 57-81.
• [24] Thomas, W.: Ehrenfeucht Games, the Composition Method, and the Monadic Theory of Ordinal Words, in: Structures in Logic and Computer Science, A Selection of Essays in Honor of Andrzej Ehrenfeucht (J. Mycielski, G. Rozenberg, A. Salomaa, Eds.), volume 1261 of Lecture Notes in Computer Science, Springer, 1997, 118-143.
• [25] Thomas,W.: Languages, Automata, and Logic, in: Handbook of Formal Languages (G.Rozenberg, A. Salomaa, Eds.), vol. 3, chapter 7, Springer-Verlag, 1997, 386-455.
• [26] Ullman, J.: Principles of database and knowledge-base systems, vol. I and II, Computer Science Press, 1989.
• [27] Yannakakis, M.: Algorithms for acyclic database schemas, Proc. 7th International Conference on Very Large Data Bases, IEEE Press, 1981.