Logical definability and query languages over ranked and unranked trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Logical definability and query languages over ranked and unranked trees

Full text

Pdf (602 KB)

Source

ACM Transactions on Computational Logic (TOCL) archive
Volume 8 , Issue 2 (April 2007) table of contents

Article No. 11

Year of Publication: 2007

ISSN:1529-3785

Authors

Michael Benedikt	Bell Laboratories, Naperville, IL
Leonid Libkin	University of Edinburgh and University of Toronto
Frank Neven	Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 69, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1227839.1227843 What is a DOI?

ABSTRACT

We study relations on trees defined by first-order constraints over a vocabulary that includes the tree extension relation T ≺ T′ (holding if and only if every branch of T extends to a branch of T′), unary node-tests, and a binary relation checking whether the domains of two trees are equal. We consider both ranked and unranked trees. These are trees with and without a restriction on the number of children of nodes. We adopt the model-theoretic approach to tree relations and study relations definable over the structure consisting of the set of all trees and the aforementioned predicates. We relate definability of sets and relations of trees to computability by tree automata. We show that some natural restrictions correspond to familiar logics in the more classical setting where every tree is a structure over a fixed vocabulary, and to logics studied in the context of XML pattern languages. We then look at relational calculi over collections of trees, and obtain quantifier-restriction results that give us bounds on the expressive power and complexity. As unrestricted relational calculi can express problems that are complete for each level of the polynomial hierarchy, we look at their restrictions, corresponding to the restricted logics over the family of all unranked trees, and find several calculi with low (NC¹) data complexity which still express properties important for database and document applications. We also give normal forms for safe queries in the calculus.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Alexander Aiken, Set Constraints: Results, Applications, and Future Directions, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.326-335, May 02-04, 1994
	3	Angluin, D. and Hoover, D. N. 1984. Regular prefix relations. Math. Syst. Theory 17, 3, 167--191.
	4	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	5	Michael Benedikt , Leonid Libkin, Relational queries over interpreted structures, Journal of the ACM (JACM), v.47 n.4, p.644-680, July 2000 [doi>10.1145/347476.347477]
	6	Michael Benedikt , Leonid Libkin , Thomas Schwentick , Luc Segoufin, Definable relations and first-order query languages over strings, Journal of the ACM (JACM), v.50 n.5, p.694-751, September 2003 [doi>10.1145/876638.876642]
	7	Achim Blumensath , Erich Grädel, Automatic Structures, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.51, June 26-29, 2000
	8	Börger, E., Grädel, E., and Gurevich, Y. 1997. The Classical Decision Problem. Springer Verlag.
	9	Bray, T., Paoli, J., Sperberg-McQueen, C. M., and Maler, E. 2000. Extensible Markup Language (XML) 1.0, 2nd ed. W3C recommendation. http://www.w3.org/XML.
	10	Brüggemann-Klein, A., Murata, M., and Wood, D. 2001. Regular tree and regular hedge languages over unranked alphabets: Version 1. Tech. Rep. HKUST-TCSC-2001-0, The Hongkong University of Science and Technology.
	11	Bruyère, V., Hansel, G., Michaux, C., and Villemaire, R. 1994. Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1, 191--238.
	12	Luca Cardelli , Giorgio Ghelli, TQL: a query language for semistructured data based on the ambient logic, Mathematical Structures in Computer Science, v.14 n.3, p.285-327, June 2004 [doi>10.1017/S0960129504004141]
	13	Chamberlin, D., Clark, J., Florescu, D., Robie, J., Simeon, J., and Stefanascu, M. 2002. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery/.
	14	Clark, J. 1999. XSL transformations version 1.0. http://www.w3.org/TR/WD-xslt.
	15	Clark, J. and DeRose, S. 1999. XML path language (XPath). http://www.w3.org/TR/xpath.
	16	Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. 1997. Tree automata techniques and applications. http://www.grappa.univ-lille3.fr/tata.
	17	Evgeny Dantsin , Andrei Voronkov, Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.157-165, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335218]
	18	Doner, J. 1970. Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4, 406--451.
	19	Jochen Dörre, Feature logic with weak subsumption constraints, Proceedings of the 29th annual meeting on Association for Computational Linguistics, p.256-263, June 18-21, 1991, Berkeley, California [doi>10.3115/981344.981377]
	20	Ebbinghaus, H.-D. and Flum, J. 1999. Finite Model Theory, 2nd ed. Springer Verlag.
	21	Jacob Elgaard , Nils Klarlund , Anders Møller, MONA 1.x: New Techniques for WS1S and WS2S, Proceedings of the 10th International Conference on Computer Aided Verification, p.516-520, June 28-July 02, 1998
	22	Zoltán Ésik, Axiomatizing the Equational Theory of Regular Tree Languages (Extended Anstract), Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.455-465, February 25-27, 1998
	23	Flum, J. and Ziegler, M. 1999. Pseudo-Finite homogeneity and saturation. J. Symb. Logic 64, 1689--1699.
	24	Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005 [doi>10.1145/1059513.1059520]
	25	Hodges, W. 1993. Model Theory. Cambridge University Press, New York.
	26	Hodgson, B. 1983. Décadabilité par automate fini. Ann. Sci. Math. Québec 7, 39--57.
	27	Immerman, N. 1998. Descriptive Complexity. Springer Verlag.
	28	Bakhadyr Khoussainov , Anil Nerode, Automatic Presentations of Structures, Selected Papers from the International Workshop on Logical and Computational Complexity, p.367-392, October 13-16, 1994
	29	Kolb, H.-P. and Mönnich, U. 1999. The Mathematics of Syntactic Structure: Trees and Their Logics. Walter De Gruyter, Hawthorne, NY.
	30	O. Kupferman , S. Safra , M. Y. Vardi, Relating word and tree automata, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.322, July 27-30, 1996
	31	Laskowski, M. C. 1992. Vapnik-Chervonenkis classes of definable sets. J. London Math. Soc. 45, 377--384.
	32	Markus Lohrey, On the Parallel Complexity of Tree Automata, Proceedings of the 12th International Conference on Rewriting Techniques and Applications, p.201-215, May 22-24, 2001
	33	Maarten Marx, Conditional XPath, the first order complete XPath dialect, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055562]
	34	Martin Müller , Joachim Niehren, Ordering constraints over feature trees expressed in second-order monadic logic, Information and Computation, v.159 n.1-2, p.22-58, May 25/June 25 2000 [doi>10.1006/inco.2000.2878]
	35	Martin Müller , Joachim Niehren , Andreas Podelski, Ordering Constraints over Feature Trees, Constraints, v.5 n.1-2, p.7-41, January 2000 [doi>10.1023/A:1009866317252]
	36	Müller, M., Niehren, J., and Treinen, R. 2001. The first-order theory of ordering constraints over feature trees. Discrete Math. Theor. Comput. Sci. 4, 2, 193--234.
	37	Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
	38	Frank Neven , Thomas Schwentick, Query automata over finite trees, Theoretical Computer Science, v.275 n.1-2, p.633-674, March 28 2002 [doi>10.1016/S0304-3975(01)00301-2]
	39	Damian Niwinski , Igor Walukiewicz, Relating Hierarchies of Word and Tree Automata, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.320-331, February 25-27, 1998
	40	Andreas Potthoff , Wolfgang Thomas, Regular Tree Languages Without Unary Symbols are Star-Free, Proceedings of the 9th International Symposium on Fundamentals of Computation Theory, p.396-405, August 23-27, 1993
	41	Rabin, M. 1969. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soci. 141, 1--35.
	42	Gert Smolka, The Oz Programming Model (Extended Abstract), Proceedings of the First International Euro-Par Conference on Parallel Processing, p.5-8, August 29-31, 1995
	43	Smolka, G. and Treinen, R. 1994. Records for logic programming. J. Logic Program. 18, 229--258.
	44	Alexei P. Stolboushkin , Michael A. Taitslin, Finite queries do not have effective syntax, Information and Computation, v.153 n.1, p.99-116, Aug. 25, 1999 [doi>10.1006/inco.1999.2792]
	45	Zhendong Su , Alexander Aiken , Joachim Niehren , Tim Priesnitz , Ralf Treinen, The first-order theory of subtyping constraints, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.203-216, January 16-18, 2002, Portland, Oregon
	46	Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
	47	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.
	48	Wolfgang Thomas, Logical aspects in the study of tree languages, Proc. of the conference on Ninth colloquium on trees in algebra and programming, p.31-49, September 1984, Bordeaux, France
	49	Thomas, W. 1987. On chain logic, path logic, and first-order logic over infinite trees. In Symposium on Logic in Computer Science. 245--256.
	50	Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
	51	Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	52	Sergei Vorobyov , Andrie Voronkov, Complexity of nonrecursive logic programs with complex values, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-253, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275515]
	53	Thomas Wilke, An algebraic characterization of frontier testable tree languages, Theoretical Computer Science, v.154 n.1, p.85-106, Jan. 22, 1996