Expressiveness of structured document query languages based on attribute grammars

ABSTRACT

Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.

REFERENCES

• 1: Serge Abiteboul , Sophie Cluet , Tova Milo, A logical view of structured files, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.2, p.96-114, May 1998 [doi>10.1007/s007780050056]
• 2: Serge Abiteboul , Victor Vianu, Computing with first-order logic, Journal of Computer and System Sciences, v.50 n.2, p.309-335, April 1995
• 3: Roderick Bloem , Joost Engelfriet, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Journal of Computer and System Sciences, v.61 n.1, p.1-50, August.1.2000 [doi>10.1006/jcss.1999.1684]
• 4: B. Courcelle , P. Deransart, Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming, Information and Computation, v.78 n.1, p.1-55, July 1988 [doi>10.1016/0890-5401(88)90002-8]
• 5: Pierre Deransart , Martin Jourdan , Bernard Lorho, Attribute grammars: definitions, systems and bibliography, Springer-Verlag New York, Inc., New York, NY, 1988
• 6: DONER, J. 1970. Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4, 406-451.
• 7: EBBINGHAUS, H.-D., AND FLUM, J. 1995. Finite Model Theory. Springer-Verlag, New York.
• 8: EBBINGHAUS, H.-D., FLUM, J., AND THOMAS, W. 1994. Mathematical Logic (second ed.). In Undergraduate Texts in Mathematics. Springer-Verlag, New York.
• 9: ENDERTON, H. 1972. A Mathematical Introduction to Logic. Academic Press, Orlando, Fla.
• 10: FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, Volume 7 of SIAM-AMS Proceedings, R. Karp, Ed. pp. 43-73.
• 11: GECSEG, M., AND STEINBY, M. 1984. Tree Automata. Akademia Kiad~, Budapest, Hungary.
• 12: Ferenc Gécseg , Magnus Steinby, Tree languages, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 13: Charles F. Goldfarb, The SGML handbook, Oxford University Press, Inc., New York, NY, 1991
• 14: Gaston H. Gonnet , Frank Wm. Tompa, Mind Your Grammar: a New Approach to Modelling Text, Proceedings of the 13th International Conference on Very Large Data Bases, p.339-346, September 01-04, 1987
• 15: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Neil Immerman, Expressibility and parallel complexity, SIAM Journal on Computing, v.18 n.3, p.625-638, June 1989 [doi>10.1137/0218043]
• 17: KNUTH, D. 1968. Semantics of context-free languages. Math. Syst. Theory 2, 2, 127-145. See also Math. Syst. Theory 5, 2, 95-96, 1971.
• 18: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 19: KOLAITIS, P. 1990. Implicit definability on finite structures and unambiguous computations. In Proceedings of the 5th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 168-180.
• 20: Phokion G. Kolaitis , Moshe Y. Vardi, Infinitary logics and 0–1 laws, Information and Computation, v.98 n.2, p.258-294, June 1992 [doi>10.1016/0890-5401(92)90021-7]
• 21: G. Mecca , P. Atzeni , A. Masci , G. Sindoni , P. Merialdo, The Araneus Web-based management system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.544-546, June 01-04, 1998, Seattle, Washington, United States
• 22: Etsuro Moriya, On two-way tree automata, Information Processing Letters, v.50 n.3, p.117-121, May 9, 1994 [doi>10.1016/0020-0190(94)00022-0]
• 23: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• 24: PAPADIMITRIOU, C. 1994. Computational Complexity. Addison-Wesley, Reading, Mass.
• 25: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 26: THATCHER, J., AND WRIGHT, J. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2, 1, 57-81.
• 27: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 28: VALIANT, L. G. 1976. Relative complexity of checking and evaluating. Inf. Proc. Lett. 5, 1 (May), 20-23.
• 29: M. Y. Vardi, Invited talk: automata theory for database theoreticians, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.83-92, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73729]
• 30: WOOD, D. 1995. Standard generalized markup language: Mathematical and philosophical issues. In Computer Science Today. Recent Trends and Developments, J. van Leeuwen, Ed. Lecture Notes in Computer Science, vol. 1000. Springer-Verlag, New York, pp. 344-365.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages; Data manipulation languages (DML)

General Terms:
Languages, Theory

Keywords:
Attribute grammars, automata, complexity, logic, structured documents