Diego Calvanese
Giuseppe De Giacomo
Moshe Y. Vardi
ABSTRACT
If the only information we have on a certain database is through a set of views, the question arises of whether this is sufficient to answer completely a given query. We say that the set of views is lossless with respect to the query, if, no matter what the database is, we can answer the query by solely relying on the content of the views. The question of losslessness has various applications, for example in query optimization, mobile computing, data warehousing, and data integration. We study this problem in a context where the database is semistructured, and both the query and the views are expressed as regular path queries. The form of recursion present in this class prevents us from applying known results to our case.We first address the problem of checking losslessness in the case where the views are materialized. The fact that we have the view extensions available makes this case solvable by extending known techniques. We then study a more complex version of the problem, namely the one where we abstract from the specific view extension. More precisely, we address the problem of checking whether, for every database, the answer to the query over such a database can be obtained by relying only on the view extensions. We show that the problem is solvable by utilizing, via automata-theoretic techniques, the known connection between view-based query answering and constraint satisfaction. We also investigate the computational complexity of both versions of the problem.
- 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
- S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: from Relations to Semistructured Data and XML. Morgan Kaufmann, Los Altos, 2000.]] Google ScholarDigital Library
- S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'98), pages 254-265, 1998.]] Google ScholarDigital Library
- P. Buneman. Semistructured data. In Proc. of the. 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'97), pages 117-121, 1997.]] Google ScholarDigital Library
- D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In Proc. of the 18th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'99), pages 194-204, 1999.]] Google ScholarDigital Library
- 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), pages 389-398, 2000.]] Google ScholarDigital Library
- D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Query processing using views for regular path queries with inverse. In Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2000), pages 58-66, 2000.]] Google ScholarDigital Library
- D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. View-based query processing and constraint satisfaction. In Proc. of the 15th IEEE Symp. on Logic in Computer Science (LICS 2000), pages 361-371, 2000.]] Google ScholarDigital Library
- R. Chirkova, A. Y. Halevy, and D. Suciu. A formal perspective on the view selection problem. In Proc. of the. 27th Int. Conf. on Very Large Data Bases (VLDB 2001), pages 59-68, 2001.]] Google ScholarDigital Library
- O. M. Duschka and M. R. Genesereth. Answering recursive queries using views. In Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'97), pages 109-116, 1997.]] Google ScholarDigital Library
- T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction. SIAM J. on Computing, 28:57-104, 1999.]] Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability A guide to NP-completeness. W. H. Freeman and Company, San Francisco (CA, USA), 1979.]] Google ScholarDigital Library
- 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, 1999.]] Google ScholarDigital Library
- S. Grumbach and L. Tininini. On the content of materialized aggregate views. In Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2000), pages 47-57, 2000.]] Google ScholarDigital Library
- A. Y. Halevy. Theory of answering queries using views. SIGMOD Record, 29(4):40-47, 2000.]] Google ScholarDigital Library
- A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proc. of the 14th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database System (PODS'95), pages 95-104, 1995.]] Google ScholarDigital Library
- C. Li, M. Bawa, and J. D. Ullman. Minimizing view sets without loosing query-answering power. In Proc. of the 8th Int. Conf. on Database Theory (ICDT 2001), pages 99-103, 2001.]] Google ScholarDigital Library
- C. Li and E. Chang. On answering queries in the presence of limited access patterns. In Proc. of the 8th Int. Conf. on Database Theory (ICDT 2001), pages 219-233, 2001.]] Google ScholarDigital Library
- T. D. Millstein, A. Y. Levy, and M. Friedman. Query containment for data integration systems. In Proc. of the 19th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2001), pages 67-75, 2000.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- W. Thomas. Languages, automata, and logic, In Handbook of Formal Language Theory, volume III, pages 389-455. 1997.]] Google ScholarDigital Library
- 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, 1997.]] Google ScholarDigital Library
- P. van Emde Boas. The convenience of tilings. In A. Sorbi, editor, Complexity, Logic, and Recursion Theory, volume 187 of Lecture Note in Pure and Applied Mathematics, pages 331-363. Marcel Dekker Inc., 1997.]]Google Scholar
Index Terms
- Lossless regular views
Recommendations
Answering Regular Path Queries Using Views
ICDE '00: Proceedings of the 16th International Conference on Data EngineeringQuery answering using views amounts to computing the answer to a query having information only on the extension of a set of views. This problem is relevant in several fields, such as information integration, data warehousing, query optimization, mobile ...
Query containment and rewriting using views for regular path queries under constraints
PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsIn this paper we consider general path constraints for semistructured databases. Our general constraints do not suffer from the limitations of the path constraints previously studied in the literature. We investigate the containment of regular path ...
Rewriting queries on SPARQL views
WWW '11: Proceedings of the 20th international conference on World wide webThe problem of answering SPARQL queries over virtual SPARQL views is commonly encountered in a number of settings, including while enforcing security policies to access RDF data, or when integrating RDF data from disparate sources. We approach this ...
Comments