Lossless regular views

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.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 3: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 4: Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263675]
• 5: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 6: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 7: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 8: Diego Calvanese , Giuseppe de Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Processing and Constraint Satisfaction, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.361, June 26-29, 2000
• 9: Rada Chirkova , Alon Y. Halevy , Dan Suciu, A Formal Perspective on the View Selection Problem, Proceedings of the 27th International Conference on Very Large Data Bases, p.59-68, September 11-14, 2001
• 10: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 11: Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Gösta Grahne , Alberto O. Mendelzon, Tableau Techniques for Querying Information Sources through Global Schemas, Proceeding of the 7th International Conference on Database Theory, p.332-347, January 10-12, 1999
• 14: Stéphane Grumbach , Leonardo Tininini, On the content of materialized aggregate views, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.47-57, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335174]
• 15: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 16: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 17: Chen Li , Mayank Bawa , Jeffrey D. Ullman, Minimizing View Sets without Losing Query-Answering Power, Proceedings of the 8th International Conference on Database Theory, p.99-113, January 04-06, 2001
• 18: Chen Li , Edward Y. Chang, On Answering Queries in the Presence of Limited Access Patterns, Proceedings of the 8th International Conference on Database Theory, p.219-233, January 04-06, 2001
• 19: Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335208]
• 20: 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.
• 21: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 22: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 23: 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.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages, Performance, Theory