ACM SIGMOD Anthology VLDB dblp.uni-trier.de

QUIST: A System for Semantic Query Optimization in Relational Databases.

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517
@inproceedings{DBLP:conf/vldb/King81,
  author    = {Jonathan J. King},
  title     = {QUIST: A System for Semantic Query Optimization in Relational
               Databases},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {510-517},
  ee        = {db/conf/vldb/King81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Semanfic query ophizotion is an approach to query optimization that uses knowledge of the semantics of the data to transform a query into another query that has the same answer but can be processed more efficiently. However, the indiscriminate application of semantic transformations can itself be excessively costly when there are many semantic rules upon which transformations can be based. This paper describes a semantic query optimization system called QUIST (Query lmprovement through Semantic Transformation). QUIST demonstrates significant cost reductions for a class of relational database queries. At the same time, QUIST uses knowledge about relational database structures and processing methods to insure that semantic transformations are applied selectively. This knowledge reflects cost models and optimization techniques developed in recent query optimization research. To integrate semantic, structure, and processing knowledge, QUIST analyzes a query at several levels of detail, along the lines of the plan-generate-test paradigm of artificial intelligence systems.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX

References

[Buchanan76]
...
[Carlson76]
C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154 BibTeX
[Couper72]
...
[Feigenbaum71]
...
[Gotlieb75]
Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX
[Hammer80]
Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX
[Hendrix78]
Gary G. Hendrix, Earl D. Sacerdoti, Daniel Sagalowicz, Jonathan Slocum: Developing a Natural Language Interface to Complex Data. ACM Trans. Database Syst. 3(2): 105-147(1978) BibTeX
[King79]
...
[King81a]
...
[King81b]
...
[Lenat76]
...
[Moore79]
...
[Sagalowicz77]
Daniel Sagalowicz: IDA: An Intelligent Data Access Program. VLDB 1977: 293-302 BibTeX
[Selinger79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Stonebraker75]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX
[Teitelman78]
...
[Wilson80]
Gerald A. Wilson: A Conceptual Model for Semantic Integrity Checking. VLDB 1980: 111-125 BibTeX
[Yao79]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX
[Youssefi79]
...

Referenced by

  1. Qi Cheng, Jarek Gryz, Fred Koo, T. Y. Cliff Leung, Linqi Liu, Xiaoyan Qian, K. Bernhard Schiefer: Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. VLDB 1999: 687-698
  2. Mitch Cherniack, Stanley B. Zdonik: Inferring Function Semantics to Optimize Queries. VLDB 1998: 239-250
  3. Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
  4. John Grant, Jarek Gryz, Jack Minker, Louiqa Raschid: Semantic Query Optimization for Object Databases. ICDE 1997: 444-453
  5. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
  6. Roberta Cochrane, Hamid Pirahesh, Nelson Mendonça Mattos: Integrating Triggers and Declarative Constraints in SQL Database Sytems. VLDB 1996: 567-578
  7. Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995)
  8. Edward Sciore, Michael Siegel, Arnon Rosenthal: Using Semantic Values to Falilitate Interoperability Among Heterogeneous Information Systems. ACM Trans. Database Syst. 19(2): 254-290(1994)
  9. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  10. Martin Buchheit, Manfred A. Jeusfeld, Werner Nutt, Martin Staudt: Subsumption between Queries to Object-Oriented Databases. EDBT 1994: 15-22
  11. Shashi Shekhar, Babak Hamidzadeh, Ashim Kohli, Mark Coyle: Learning Transformation Rules for Semantic Query Optimization: A Data-Driven Approach. IEEE Trans. Knowl. Data Eng. 5(6): 950-964(1993)
  12. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
  13. Michael Siegel, Stuart E. Madnick: A Metadata Approach to Resolving Semantic Conflicts. VLDB 1991: 133-145
  14. Beat Wüthrich: Semantic Improvement of Deductive Databases. MFDBS 1991: 216-229
  15. HweeHwa Pang, Hongjun Lu, Beng Chin Ooi: An Efficient Semantic Query Optimization Algorithm. ICDE 1991: 326-335
  16. Stefan W. Joseph, Romas Aleliunas: A Knowledge-Based Subsystem for a Natural Language Interface to a Database that Predicts and Explains Query Failures. ICDE 1991: 80-87
  17. Wesley W. Chu, Rei-Chi Lee, Qiming Chen: Using Type Inference and Induced Rules to Provide Intensional Answers. ICDE 1991: 396-403
  18. Jong-Jin Sung, Jong-Tae Park: Semantic Query Processing in Object-Oriented Database Systems. DASFAA 1991: 11-20
  19. HweeHwa Pang, Hongjun Lu, Beng Chin Ooi: Query Processing in OODB. DASFAA 1991: 1-10
  20. Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990)
  21. T. Y. Cliff Leung, Richard R. Muntz: Query Processing for Temporal Databases. ICDE 1990: 200-208
  22. Jean Philippe Lagrange: A Knowledge-Based System and an ER Query Language for Accessing Relational Databases. ER 1990: 157-170
  23. Clement T. Yu, Wei Sun: Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization. IEEE Trans. Knowl. Data Eng. 1(3): 362-375(1989)
  24. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  25. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  26. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  27. Shashi Shekhar, Jaideep Srivastava, Soumitra Dutta: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988: 457-467
  28. Sanggoo Lee, Jiawei Han: Semantic Query Optimization in Recursive Databases. ICDE 1988: 444-451
  29. Xiaolei Qian, Douglas R. Smith: Integrity Constraint Reformulation for Efficient Validation. VLDB 1987: 417-425
  30. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195
  31. W. S. Luk, Steve Kloster: ELFS: English Language From SQL. ACM Trans. Database Syst. 11(4): 447-472(1986)
  32. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
  33. Tim Sheard, David W. Stemple: Coping with Complexity in Automated Reasoning about Database Systems. VLDB 1985: 426-435
  34. Kazuhiro Satoh, Masashi Tsuchida, Fumio Nakamura, Kazuhiko Oomachi: Local and Global Query Optimization Mechanisms for Relational Databases. VLDB 1985: 405-417
  35. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  36. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  37. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  38. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
  39. Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:14 2009