- Abi97.S. Abiteboul. Querying semi-structured data. In Proc. of the 6th Int. Conf. on Database Theory (ICDT-g7), pages 1-18, 1997.]] Google ScholarDigital Library
- ACPS96.S. Adali, K. S. Candan, Y. Papakonstantinou, and V. S. Subrahmanian. Query caching and optimization in distribul~ed mediator systems. In Proc. o} the ACM SIGMOD Int. Conf. on Management of Data, pages 137-148, 1996.]] Google ScholarDigital Library
- AD98.S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In Proc. of the 17th A CM SIGA CT SIGMOD SIGART Sym. on Principles o} Database Systems (PODS-98), pages 254- 265, 1998.]] Google ScholarDigital Library
- AQM+97.S. Abiteboul, D. Quass, J. McHugh, J. Widom, aad J. L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.]]Google ScholarCross Ref
- AV97.S. Abiteboul and V. Vianu. Regular path queries with constra.ints. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS-97), pages 122-133, 1997.]] Google ScholarDigital Library
- BDFS97.P. Buneman, S. Davidson, M. Ferna.ndez, and D. Suciu. Adding structure to unstructured data. In Proc. of the 6th Int. Conf. on Database Theory (ICDT-97), pages 336-350, 1997.]] Google ScholarDigital Library
- BDHS96.P. Buneman, S. Da.vidson, G. Hillebrand, and D. Suciu. A query language and optimization technique for unstructured data. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 505-516, 1996.]] Google ScholarDigital Library
- BFW98.P. Buneman, W. Fan, and S. Weinstein. Path constraints on semistructured and structured data.. In Proc. of the 17th A CM SIGACT SIGMOD SIGART Sym. on Principles o.f Database Systems (PODS- 98), pages 129-138, 1998.]] Google ScholarDigital Library
- BLR97.C. Beeri, A. Y. Levy, and M.-C. Rousset. Rewriting queries using views in description logics. In Proc. of the 16th A CM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS- 97), pages 99-108, 1997.]] Google ScholarDigital Library
- Bun97.P. Buneman. Semistructured data. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS-97), pages 117-121, 1997.]] Google ScholarDigital Library
- CACS94.V. Christophides, S. Abiteboul, S. Cluet, and M. Scholl. From structured documents to novel query facilities. In R. T. Snodgrass and M. Winslett, editors, Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 313-324, Minneapolis (Minnesota, USA), 1994.]] Google ScholarDigital Library
- CDGL98.D. Calvanese, G. De Giacomo, and M. Lenzerini. On the decidability of query containment under constraints. In Proc. of the 17th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS-98), pages 149-158, 1998.]] Google ScholarDigital Library
- CDGLV99.D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Answering regular path queries using views. Technical report, Dipartimento di Informatica e Sistemistica, Universith. di Roma "La Sapienza", 1999.]]Google Scholar
- CKPS95.S. Chaudhuri, S. Krishnamurthy, S. Potarnianos, and K. Shim. Optimizing queries with materialized views. In Proc. of the 11th IEEE Int. Con}. on Data Engineer' ing (ICDE-95), Taipei, Taiwan, 1995.]] Google ScholarDigital Library
- CM90.M.P. Consens and A. O. Mendelzon. Graphlog: a visual formalism for real life recursion. In Proc. of the 9th A CM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS- gO), pages 404-416, Atlantic City (N J, USA), 1990.]] Google ScholarDigital Library
- CMW87.I.F. Cruz, A. O. Mendelzon, and P. T. Wood. A graphical query language supporting recursion. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 323-330, San Francisco (CA, USA), 19s7.]] Google ScholarDigital Library
- CNS99.S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In Proc. of the 18th A CM SIGACT SIG- MOD SIGART Sym. on Principles of Database Systems (PODS-g9), 1999.]] Google ScholarDigital Library
- DG97.O.M. Duschka and M. R. Genesereth. Answering recursive queries using views. In Proc. of the 16th A CM SIGA UT SIGMOD SIGART Sym. on Principles o} Database Systems (PODS-97), pages 109-116, 1997.]] Google ScholarDigital Library
- FFK+98.M.F. Fernandez, D. Florescu, J. Kang, A. Y. Levy, and D. Suciu. Catching the boat with strudel: Experiences with a. website management system. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 414-425, 1998.]] Google ScholarDigital Library
- FFLS97.M.F. Fernandez, D. Florescu, A. Y. Levy, and D. Suciu. A query language for a web-site management system. SIGMOD Record, 26(3):4-11, 1997.]] Google ScholarDigital Library
- FLS98.D. Florescu, A. Levy, and D. Suciu. Query containment for conjunctive queries with regular expressions. In Proc. of the 17th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS- 98), pages 139-148, 1998.]] Google ScholarDigital Library
- FS98.M.F. Fernandez and D. Suciu. Optimizing regular path expressions using graph schemas. In Proc. of the l~th IEEE Int. Conf. on Data Engineering (ICDE-98), pages 14-23, 1998.]] Google ScholarDigital Library
- Jon75.N.D. Jones. Space..bounded reducibility among combinatorial problems. J. of Computer and System Sciences, 11:68-75, 1975.]]Google ScholarDigital Library
- LMSS95.A.Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views, fin Proc. of the 14th A CM SIGACT SIGMOD SIGART Sym. on Principles of Databa,~e Systems (PODS-95), pages 95- 104, 1995.]] Google ScholarDigital Library
- MMM97.A. Mendelzon, G. A. Mihaila, a.nd T. Milo. Querying the World Wide Web. Int..1. on Digital Libraries, 1(1):54-67, 1997.]]Google Scholar
- MS99.T. Milo and D. Suciu. index structures for path expressions. In Proc. o/the 7th Int. Conf. on Database Theory (ICDT-99), volume 1540 of Lecture Notes in Computer Science, pages 277-295. Springer-Verlag, 1999.]] Google ScholarDigital Library
- QRS+95.D. Qu~ss, A. Rajaraman, I. Sagiv, J. Ullman, arid J. Widom. Querying semistructured heterogeneous information. In Proc. of the ~th Int. Conf. on Deductive and O~ject-Oriented Databases (190019- 95), pages 319-344. Springer-Verlag, 1995.]] Google ScholarDigital Library
- RS59.M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:115-125, 1959.]]Google ScholarDigital Library
- RSU95.A. Rajaraman, Y. Sagiv, and j. D. Ullman. Answering queries using templates with binding patterns. In Proc. of the l~th A CM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS- 95), 199,5.]] Google ScholarDigital Library
- Sav70.W.J. S;~vitch. Relationship between nondetermi~xistic and deterministic tape complexities'.. J. of Computer and System Sciences, 4:177-192, 1970.]]Google ScholarDigital Library
- SDJL96.D. Srivastava, S. Dar~ H. V. Jagadish, and A. Levy. Answering queries with aggregation using views. In Proc. of the 22nd Int. Conf. on Very Large Data Bases (VLDB- g6), pages 318-329, 1996.]] Google ScholarDigital Library
- TSI96.O.G. Tsatalos, M. H. Solomon, and Y. E. Ioannidis. The GMAP: A versatile tool for phyisical data independence. Very Large Database J.. 5(2):101-118~ 1996.]] Google ScholarDigital Library
- Ull97.J.D. Ullman. Information integration using logical views. In Proc. of the 6th Int. Conf. on Database Theory (ICDT- 97), number 1186 in Lecture Notes in Computer Science, pages 19-40. Springer- Verlag, 1997.]] Google ScholarDigital Library
Index Terms
- Rewriting of regular expressions and regular path queries
Recommendations
Regular Transducer Expressions for Regular Transformations
LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer ScienceFunctional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show that every regular function, either on finite words or on infinite words, ...
Rewriting of Regular Expressions and Regular Path Queries
Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a path conforming to a certain specification, in particular to a regular expression. ...
Closure properties and descriptional complexity of deterministic regular expressions
We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of ...
Comments