Diego Calvanese
Moshe Y. Vardi
Giuseppe de Giacomo
ABSTRACT
View-based query processing is the problem of computing the answer to a query based on a set of materialized views, rather than on the raw data in the database. The problem comes in two different forms, called query rewriting and query answering, respectively. In the first form, we are given a query and a set of view definitions, and the goal is to reformulate the query into an expression that refers only to the views. In the second form, besides the query and the view definitions, we are also given the extensions of the views and a tuple, and the goal is to check whether the knowledge on the view extensions logically implies that the tuple satisfies the query.
In this paper we address the problem of view-based query processing in the context of semistructured data, in particular for the case of regular-path queries extended with the inverse operator. Several authors point out that the inverse operator is one of the fundamental extensions for making regular-path queries useful in real settings. We present a novel technique based on the use of two-way finite-state automata. Our approach demonstrates the power of this kind of automata in dealing with the inverse operator, allowing us to show that both query rewriting and query answering with the inverse operator has the same computational complexity as for the case of standard regular-path queries.
- 1.S. Abiteboul. Querying semi-structured data. In Proc. of the 6th Int. Conf. on Database Theory (ICDT'97), pages 1-18, 1997.]] Google Scholar
Digital Library
- 2.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 of Database Systems (PODS'98), pages 254-265, 1998.]] Google ScholarDigital Library
- 3.S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.]]Google ScholarCross Ref
- 4.S. Adali, K. S. Candan, Y. Papakonstantinou, and V. S. Subrahmanian. Query caching and optimization in distributed mediator systems. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 137-148, 1996.]] Google ScholarDigital Library
- 5.F. N. Afrati, M. Gergatsoulis, and T. Kavalieros. Answering queries using materialized views with disjunction. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 435-452. Springer-Verlag, 1999.]] Google ScholarDigital Library
- 6.C. Beeri, A. Y. Levy, and M.-C. Rousset. Rewriting queries using views in description logics. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'97), pages 99-108, 1997.]] Google ScholarDigital Library
- 7.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
- 8.P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization technique for unstructured data. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 505-516, 1996.]] Google ScholarDigital Library
- 9.D. Calvanese, G. De Giacomo, and M. Lenzerini. Answering queries using views in description logics. In Proc. of the 1999 Description Logic Workshop (DL '99), pages 9-13. CEUR Electronic Workshop Proceedings http://sunsite.informatik.rwthaachen, de / Pub licat ions / CE UR-WS/Vol- 22/, 1999.]]Google Scholar
- 10.D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In Proc. of the 18th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'99), pages 194-204, 1999.]] Google ScholarDigital Library
- 11.D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Answering regular path queries using views. In Proc. of the 16th IEEE Int. Conf. on Data Engineering (ICDE 2000), 2000. To appear.]] Google ScholarDigital Library
- 12.D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In Proc. of the 7th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2000), 2000. To appear.]]Google Scholar
- 13.S. Chaudhuri, S. Krishnamurthy, S. Potarnianos, and K. Shim. Optimizing queries with materialized views. In Proc. of the 11th IEEE Int. Conf. on Data Engineering (ICDE'95), Waipei (Waiwan), 1995.]] Google ScholarDigital Library
- 14.J. Clark and S. Deach. Extensible Stylesheet Language (XSL). Technical report, World Wide Web Consortium, 1999. Available at http://www.w3.org/WR/WD-xsl.]]Google Scholar
- 15.S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In Proc. of the 18th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'99), pages 155-166, 1999.]] Google ScholarDigital Library
- 16.O. M. Duschka and M. R. Genesereth. Answering recursive queries using views. In Proc. of the 16th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'97), pages 109-116, 1997.]] Google ScholarDigital Library
- 17.O. M. Duschka and A. Y. Levy. Recursive plans for information gathering. In Proc. of the 15th Int. Joint Conf. on Artificial Intelligence (IJCAI'97), pages 778-784, 1997.]]Google Scholar
- 18.M. F. Fernandez, D. Florescu, J. Kang, A. Y. Levy, and D. Suciu. Catching the boat with strudel: Experiences with a web-site management system. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 414-425, 1998.]] Google ScholarDigital Library
- 19.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
- 20.M. L. Ginsberg, editor. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, Los Altos, 1987.]] Google ScholarDigital Library
- 21.G. Grahne and A. O. Mendelzon. Tableau techniques for querying information sources through global schemas. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 332-347. Springer-Verlag, 1999.]] Google ScholarDigital Library
- 22.J. Gryz. Query folding with inclusion dependencies. In Proc. of the l~th IEEE Int. Conf. on Data Engineering (ICDE'98), pages 126-133, 1998.]] Google ScholarDigital Library
- 23.J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley Publ. Co., Reading, Massachussetts, 1979.]] Google ScholarDigital Library
- 24.A. Y. Levy. Obtaining complete answers from incomplete databases. In Proc. of the 22nd Int. Conf. on Very Large Data Bases (VLDB'96), pages 402-412, 1996.]] Google ScholarDigital Library
- 25.A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proc. of the l~th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'95), pages 95-104, 1995.]] Google ScholarDigital Library
- 26.T. Milo and D. Suciu. Index structures for path expressions. In Proc. of 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
- 27.Y. Papakonstantinou and V. Vassalos. Query rewriting using semistructured views. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, 1999.]] Google ScholarDigital Library
- 28.A. Rajaraman, Y. Sagiv, and J. D. Ullman. Answering queries using templates with binding patterns. In Proc. of the l~th A CM SIGA CT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'95), 1995.]] Google ScholarDigital Library
- 29.R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 119-140. Plenum Publ. Co., New York, 1978. Republished in {20}.]]Google ScholarCross Ref
- 30.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'96), pages 318-329, 1996.]] Google ScholarDigital Library
- 31.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
- 32.J. D. Ullman. Information integration using logical views. In Proc. of the 6th Int. Conf. on Database Theory (ICDT'97), volume 1186 of Lecture Notes in Computer Science, pages 19-40. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 33.R. van der Meyden. Logical approaches to incomplete information. In J. Chomicki and G. Saake, editors, Logics for Databases and Information Systems, pages 307-356. Kluwer Academic Publishers, 1998.]] Google ScholarDigital Library
- 34.M. Y. Vardi. The complexity of relational query languages. In Proc. of the l~th A CM SIGA CT Sym. on Theory of Computing (STOC'82), pages 137-146, 1982.]] Google ScholarDigital Library
- 35.M. Y. Vardi. A note on the reduction of two-way automata to one-way automata. Information Processing Letters, 30(5):261-264, 1989.]] Google ScholarDigital Library
Index Terms
- View-based query processing for regular path queries with inverse
Recommendations
View-based query processing: On the relationship between rewriting, answering and losslessness
As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
View-based query processing: on the relationship between rewriting, answering and losslessness
ICDT'05: Proceedings of the 10th international conference on Database TheoryAs a result of the extensive research in view-based query processing, three notions have been identi.ed as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases ...
View-based query containment
PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsQuery containment is the problem of checking whether for all databases the answer to a query is a subset of the answer to a second query. In several data management tasks, such as data integration, mobile computing, etc., the data of interest are only ...
Comments