Answering queries using views with arithmetic comparisons

ABSTRACT

We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons (CQACs) over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We have developed a novel algorithm to obtain maximally-contained rewritings (MCRs) for queries having left (or right) semi-interval-comparison predicates. For semi-interval queries, we show that the language of finite unions of CQAC rewritings is not sufficient to find a maximally-contained solution, and identify cases where datalog is sufficient. Finally, we show that it is decidable to obtain equivalent rewritings for CQAC queries.

REFERENCES

• 1: 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]
• 2: F. Afrati, C. Li, and P. Mitra. Answering queries using views with arithmetic comparisons (full version). Technical report, Information and Computer Science, UC Irvine, 2002.
• 3: Foto N. Afrati , Chen Li , Jeffrey D. Ullman, Generating efficient plans for queries using views, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.319-330, May 21-24, 2001, Santa Barbara, California, United States
• 4: R. J. Bayardo, Jr. , W. Bohrer , R. Brice , A. Cichocki , J. Fowler , A. Helal , V. Kashyap , T. Ksiezyk , G. Martin , M. Nodine , M. Rashid , M. Rusinkiewicz , R. Shea , C. Unnikrishnan , A. Unruh , D. Woelk, InfoSleuth: agent-based semantic integration of information in open and dynamic environments, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.195-206, May 11-15, 1997, Tucson, Arizona, United States
• 5: Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset, Rewriting queries using views in description logics, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.99-108, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263673]
• 6: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Answering Queries Using Views over Description Logics Knowledge Bases, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.386-391, July 30-August 03, 2000
• 7: Ashok K. Chandra , Harry R. Lewis , Johann A. Makowsky, Embedded implicational dependencies and their inference problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.342-354, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802488]
• 8: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 9: Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
• 10: Surajit Chaudhuri , Moshe Y. Vardi, On the equivalence of recursive and nonrecursive datalog programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.55-66, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137109]
• 11: S. S. Chawathe et al. The TSIMMIS project: Integration of heterogeneous information sources. IPSJ, pages 7-18, 1994.
• 12: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• 13: Oliver Michael Duschka , Michael R. Genesereth, Query planning and optimization in information integration, 1998
• 14: 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]
• 15: Daniela Florescu , Alon Y. Levy , Dan Suciu , Khaled Yagoub, Optimization of Run-time Management of Data Intensive Web-sites, Proceedings of the 25th International Conference on Very Large Data Bases, p.627-638, September 07-10, 1999
• 16: 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
• 17: Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
• 18: Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang, Optimizing Queries Across Diverse Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.276-285, August 25-29, 1997
• 19: 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]
• 20: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 21: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 22: Phokion G. Kolaitis , David L. Martin , Madhukar N. Thakur, On the complexity of the containment problem for conjunctive queries with built-in predicates, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.197-204, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275510]
• 23: A. Levy. Answering queries using views: A survey. Technical report, Computer Science Dept., Washington Univ., 2000.
• 24: 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]
• 25: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 26: Chen Li , Jeffrey D. Ullmann, Query processing and optimization in information-integration systems, 2001
• 27: 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
• 28: Prasenjit Mitra, An algorithm for answering queries efficiently using views, Proceedings of the 12th Australasian database conference, p.99-106, January 29-February 01, 2001, Queensland, Australia
• 29: Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
• 30: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 31: Dimitri Theodoratos , Timos K. Sellis, Data Warehouse Configuration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.126-135, August 25-29, 1997
• 32: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 33: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 34: J. D. Ullman. Personal communication, 2001.
• 35: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
• 36: Xubo Zhang , Z. Meral Ozsoyoglu, Implication and Referential Constraints: A New Formal Reasoning, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.894-910, November 1997 [doi>10.1109/69.649315]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

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

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

General Terms:
Design, Languages, Theory