Regular Path Queries with Constraints

The World Wide Web Consortium (W3C)'s XML Web Page, http://www.w3.org/XML/. S. Abiteboul, Querying semistructured data, in, Proceedings of the International Conference on Database Theory, Delphi, Greece, 1997. Abiteboul, 1997, Querying documents in object databases, J. Digital Libraries, 1 Abiteboul, 1995 Abiteboul, 1997, The Lorel query language for semistructured data, J. Digital Libraries, 1 S. Abiteboul and V. Vianu, Queries and computation on the Web, in Proc. of Intl. Conf. on Database Theory, 1997, pp. 262–275. S. Abiteboul and V. Vianu, Regular path queries with constraints, in Proc. ACM Symp. on Principles of Database Systems, 1997, pp. 122–133. Buchsbaum, 1991, A data structure for arc insertion and regular path finding, Ann. Math. and AI, 3, 187 F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman, Magic sets and other strange ways to implement logic programs, in Proc. ACM Symp. on Principles of Database Systems, 1986, pp. 1–15. C. Beeri, P. C. Kanellakis, F. Bancilhon, and R. Ramakrishnan, Bounds on the propagation of selection into logic programs, in Proc. ACM Symp. on Principles of Database Systems, 1987, pp. 214–226. P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu, A query language and optimization techniques for unstructured data, in Proc. of the ACM SIGMOD Conf. on Management of Data, 1996, pp. 505–516. M. Consens and A. Mendelzon, Graphlog: a visual formalism for real life recursion, in Proc. ACM Symp. on Principles of Database Systems, 1990, pp. 404–416. J. Van den Bussche and G. Vossen, An extension of path expressions to simplify navigation in object-oriented queries, in Proc. of Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), 1993, pp. 267–282. Dershowitz, 1990, Rewrite systems, 243 Garey, 1979 E. Graedel, P. Kolaitis, and, M. Y. Vardi, On the complexity of the decision problem for two-variable first-order logic, to appear. E. Graedel, M. Otto, and E. Rosen, Undecidability results for two-variable logics, extended abstract, in STACS'97, pp. 249–260. Hopcroft, 1979 Kanellakis, 1991, Elements of relational database theory M. Kifer, W. Kim, and Y. Sagiv, Querying object-oriented databases, in Proc. of the ACM SIGMOD Conf. on Management of Data, 1992, pp. 393–402. D. Konopnicki and O. Shmueli, W3QS: A query system for the World Wide Web, in Proc. Int. Conf. on Very Large Data Bases (VLDB), 1995, pp. 54–65. A. Mendelzohn, G. A. Mihaila, and, T. Milo, Querying the World Wide Web, in, Proc. PDIS, 1996. G. Mecca, A. Mendelzon, and P. Merialdo, Efficient queries over Web views, in Proc. EDBT, 1998, pp. 72–86. Mendelzon, 1995, Finding regular simple paths in graph databases, SIAM J. Comp., 24, 10.1137/S009753979122370X Mortimer, 1975, On languages with two variables, Z. Math. Logik Grundl. Math., 21, 135, 10.1002/malq.19750210118 J. F. Naughton, One-sided recursions, in Proc. ACM Symp. on Principles of Database Systems, 1987, pp. 340–348. Y. Papakonstantinou, S. Abiteboul, and, H. Garcia-Molina, Object fusion in mediator systems, in, Proceedings of the Twenty-Second International Conference on Very Large Data Bases, Bombay, India, 1996. Y. Papakonstantinou, H. Garcia-Molina, and J. Widom, Object exchange across heterogeneous information sources, in Proceedings of the Eleventh International Conference on Data Engineering, Taipei, Taiwan, March 1995, pp. 251–260. Salomaa, 1966, Two complete axiom systems for the algebra of regular events, J. Assoc. Comput. Mach., 13, 158, 10.1145/321312.321326 D. Suciu, Query decomposition and view maintenance for query languages for unstructured data, in Proc. of Intl. Conf. on Very Large Data Bases, 1996, pp. 227–238. Vieille, 1987, Recursive query processing: the power of logic, Theoret. Comput. Sci., 69, 1, 10.1016/0304-3975(89)90088-1 M. Yannakakis, Graph-theoretic methods in database theory, in Proc. ACM Symp. on Principles of Database Systems (invited talk), 1990, pp. 230–242.