research-article

Design and Implementation of a Semantic Query Optimizer

Authors:

Z. M. OzsoyogluAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 1, Issue 3

Pages 344 - 361

https://doi.org/10.1109/69.87980

Published: 01 September 1989 Publication History

Abstract

The authors describe a scheme to utilize semantic knowledge in optimizing a user-specified query. The semantics is represented as function-free clauses in predicate logic. The scheme uses a graph-theoretic approach to identify redundant joins and restrictions present in a given query while adding additional profitable specifications to it. Dynamic and heuristic interaction of three entities-schema, semantics, and query-forms the basis of the algorithm. The implementation architecture of the algorithm and test results on a representative set of data are presented. Issues associated with updating of semantic constraints are addressed, and an algorithm for semantic maintenance is introduced.

References

[1]

{1} A. V. Aho, Y. Sagiv, and J. D. Ullman, "Equivalences among relational expressions," SIAM J. Comput., vol. 8, pp. 218-246, 1979.

Digital Library

[2]

{2} M. M. Astrahan et al., "SYSTEM R: A relational approach to database management," ACM TODS, vol. 1, June 1976.

Digital Library

[3]

{3} P. A. Bernstein et al., "Query processing in systems for distributed databases (SDD-1)," ACM TODS, vol. 6, pp. 602-625, Dec. 1981.

Digital Library

[4]

{4} M. W. Blasgen and K. P. Eswaran, "Storage access in relational databases," IBM Syst. J., vol. 16, no. 4, 1977.

Digital Library

[5]

{5} U. S. Chakravarthy, D. H. Fishman, and J. Minker, "Semantic query optimization in expert systems and database systems," in Proc. 1st Int. Conf. Expert Database Syst., Kiawah Isl., SC, Oct. 1984, pp. 326-341.

[6]

{6} U. S. Chakravarthy and J. Minker, "Multiple query processing in deductive databases," Univ. Maryland, Tech. Rep. TR-1154, Aug. 1985.

[7]

{7} U. S. Chakravarthy, J. Minker, and J. Grant, "Semantic query optimization: Additional constraints and controil strategies," in Proc. 1st Int. Conf. Expert Database Syst., Charleston, SC, L. Kershberg, Ed., Apr. 1986, pp. 259-269.

[8]

{8} R. Epstein, M. Stonebraker, and E. Wong, "Distributed query processing in database systems," in Proc. ACM SIGMOD, Austin, TX, June 1978, pp. 169-180.

[9]

{9} G. Gentzen, "Untersuchugen über das logische schliessen," in The Collected Papers of Gerhard Gentzen, M. E. Szabo, Ed. Amsterdam; The Netherlands: North-Holland, 1934, pp. 68- 132.

[10]

{10} J. Grant and J. Minker, "Optimization in deductive and conventional database systems," in Advances in Database Theory, VoI. 1, H. Gallaire, J. Minker, and J. M. Nicolas, Eds. New York: Plenum, 1980.

[11]

{11} L. R. Gotlieb, "Computing joins of relations," ACM SIGMOD Int. Symp. Management Data, 1975, pp. 55-63.

[12]

{12} M. Hammer and S. B. Zdonik, Jr., "Knowledge based query processing," in Proc. VLDB, 1980, pp. 137-147.

[13]

{13} H. B. Hunt and D. J. Rosenkrantz, "The complexity of testing predicate locks," in Proc. ACM SIGMOD, 1979, pp. 127-133.

[14]

{14} A. R. Hevner and S. B. Yao, "Query processing in distributed database systems," IEEE Trans. Software Eng., vol. 5, pp, 177-187, May 1979.

Digital Library

[15]

{15} M. Jarke, "External semantic query simplification: A graph-theoretic approach and its implementation in Prolog," in Proc. 1st Int. Conf. Expert Database Syst., Kiawah, Isl., SC, Oct. 1984, pp. 467-482.

[16]

{16} M. Jarke, J. Clifford, and Y. Vassiliou, "An optimizing Prolog front end to a relational query system," in Proc. ACM SIGMOD, Boston, 1984, pp. 296-306.

[17]

{17} W. Kim, "Relational database systems," ACM Comput. Surveys, vol. 3, pp. 185-212, Sept. 1979.

[18]

{18} J. J. King, "QUIST: A system for semantic query optimization in relational databases," in Proc. VLDB, 1981, pp. 510-517.

[19]

{19} A. Klug, "On conjunctive queries containing inequalities," JACM, vol. 35, pp. 146-160, Jan. 1988.

Digital Library

[20]

{20} R. Kowalski, "Logic for problem solving," Artificial Intelligence Series , The Computer Science Library, 1983.

[21]

{21} R. Krishnamurthy, H. Boral, and C. Zaniolo, "Efficient optimization of nonrecursive queries," in Proc. VLDB, 1986.

[22]

{22} R. Kung, E. Hanson, Y. Ioannidis, T. Sellis, L. Shapiro, and M. Stonebraker, "Heuristic search in database systems," in Proc. 1st Int. Conf. Expert Database Syst., Kiawah Isl., SC, Oct. 1984, pp. 96-107.

[23]

{23} D. Maier, The Theory of Relational Databases. New York: Computer Science, 1983.

[24]

{24} Z. Manna, Mathematical Theory of Computation. New York: McGraw-Hill, 1974, pp. 109-111.

[25]

{25} E. Mendelson, Introduction to Mathematical Logic. Princeton, NJ: Van Nostrand, 1964.

[26]

{26} M. Morgenstern, "The role of constraints in database, expert systems, and knowledge representation," in Proc. 1st Int. Conf. Expert Database Syst., Kiawah Isl., SC, Oct. 1984, pp. 207-223.

[27]

{27} F. P. Palermo, "A database search problem," in Information Systems COINS IV, J. T. Tou, Ed. New York: Plenum.

[28]

{28} J. M. Nicholas and K. Yazdanian, "Integrity checking in deductive databases," in Logic and Databases, H. Galliere and J. Minker, Eds. New York: Plenum, 1978.

[29]

{29} X. Qian and D. R. Smith, "Reformulation: an approach to efficient constraint validation," in Proc. VLDB, 1987.

[30]

{30} D. J. Rosenkrantz and H. B. Hunt, "Processing conjunctive predicates and queries," in Proc. VLDB, 1980, pp. 64-72.

[31]

{31} T. K. Sellis, "Global query optimization," in Proc. ACM SIGMOD, May 1986, pp. 191-205.

[32]

{32} S. T. Shenoy and Z. M. Ozsoyoglu, "A system for semantic query optimization," in Proc. ACM SIGMOD, May 1987, pp. 181-195.

[33]

{33} S. Shekar, J. Srivastava, and S. Dutta, "A formal model of trade-off between optimization and execution costs in semantic query optimization," in Proc. VLDB, Aug. 1988, pp. 457-467.

[34]

{34} M. Siegel, "Automatic rule derivation for semantic query optimization," Boston Univ., Tech. Rep. 87-012, 1987.

[35]

{35} M. Siegel, "Automatic rule derivation for semantic query optimization," in Proc. 2nd Int. Conf. Expert Database Syst., Tysons Corners, VA, 1988, pp. 371-385.

[36]

{36} M. R. Stonebraker, E. Wong, P. Kreps, and G. Held, "The design and implementation of INGRES," ACM TODS, vol. 1, Sept. 1976, pp. 189-222.

Digital Library

[37]

{37} L. Sterling and E. Shapiro, The Art of Prolog. Cambridge, MA: M.I.T. Press, 1986.

[38]

{38} X. Sun, N. Kamel, and L. M. Ni, "Solving implication problems in database applications," in Proc. ACM SIGMOD, May 1989, pp. 185- 192.

[39]

{39} J. D. Ullman, Principles of Database Systems, 2nd ed. New York: Computer Science, 1978.

[40]

{40} E. Wong and K. Youssefi, "Decomposition: A strategy for query processing," ACM TODS, vol. 1, pp. 223-241, Sept. 1976.

Digital Library

[41]

{41} S. B. Yao, "Optimization of query evalulation algorithms," ACM TODS, vol. 4, no. 2, pp. 133-155.

Digital Library

[42]

{42} T. C. Yu and Z. M. Ozsoyoglu, "On determining tree query membership of a distributed query," in Proc. INFOR, Aug. 1983, pp. 261-281.

Cited By

Le DBressan SPardede ETaniar DRahayu W(2010)A utilization of schema constraints to transform predicates in XPath queryProceedings of the 21st international conference on Database and expert systems applications: Part I10.5555/1881867.1881903(331-339)Online publication date: 30-Aug-2010
https://dl.acm.org/doi/10.5555/1881867.1881903
Le DBressan STaniar DRahayu W(2007)Semantic XPath query transformationProceedings of the 12th international conference on Database systems for advanced applications10.5555/1783823.1783941(994-1000)Online publication date: 9-Apr-2007
https://dl.acm.org/doi/10.5555/1783823.1783941
Gryz JLiang D(2006)Holes in joinsJournal of Intelligent Information Systems10.1007/s10844-006-0368-226:3(247-268)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1007/s10844-006-0368-2
Show More Cited By

Design and Implementation of a Semantic Query Optimizer
1. Theory of computation
  1. Semantics and reasoning

Recommendations

Query evaluation in deductive databases with alternating fixpoint semantics

First-order formulas allow natural descriptions of queries and rules. Van Gelder's alternating fixpoint semantics extends the well-founded semantics of normal logic programs to general logic programs with arbitrary first-order formulas in rule bodies. ...
Making the Knowledge Base Systems More Efficient: A Method to Detect Inconsistent Queries

The processing cost of queries with an empty answer, both in the database and knowledge base context, is usually high. One purpose of semantic query optimization methods in the database context is to use semantic knowledge to detect such types of ...
Query containment theory and its relevance to secure query processing

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 1, Issue 3

September 1989

117 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 1989 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 September 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Le DBressan SPardede ETaniar DRahayu W(2010)A utilization of schema constraints to transform predicates in XPath queryProceedings of the 21st international conference on Database and expert systems applications: Part I10.5555/1881867.1881903(331-339)Online publication date: 30-Aug-2010
https://dl.acm.org/doi/10.5555/1881867.1881903
Le DBressan STaniar DRahayu W(2007)Semantic XPath query transformationProceedings of the 12th international conference on Database systems for advanced applications10.5555/1783823.1783941(994-1000)Online publication date: 9-Apr-2007
https://dl.acm.org/doi/10.5555/1783823.1783941
Gryz JLiang D(2006)Holes in joinsJournal of Intelligent Information Systems10.1007/s10844-006-0368-226:3(247-268)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1007/s10844-006-0368-2
Beneventano DBergamaschi SGelati GGuerra FVincini M(2003)MIKSIntelligent information agents10.5555/1809359.1809363(22-49)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/1809359.1809363
Beneventano DBergamaschi SSartori C(2003)Description logics for semantic query optimization in object-oriented database systemsACM Transactions on Database Systems10.1145/762471.76247228:1(1-50)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1145/762471.762472
Lowden BRobinson J(2002)Constructing Inter-relational Rules for Semantic Query OptimisationProceedings of the 13th International Conference on Database and Expert Systems Applications10.5555/648315.756174(587-596)Online publication date: 2-Sep-2002
https://dl.acm.org/doi/10.5555/648315.756174
Gryz JLiang D(2002)Query Optimization via Empty JoinsProceedings of the 13th International Conference on Database and Expert Systems Applications10.5555/648315.756028(710-720)Online publication date: 2-Sep-2002
https://dl.acm.org/doi/10.5555/648315.756028
Giannella CDalkilic MGroth DRobertson E(2002)Improving Query Evaluation with Approximate Functional Dependency Based DecompositionsProceedings of the 19th British National Conference on Databases: Advances in Databases10.5555/646104.681206(26-41)Online publication date: 17-Jul-2002
https://dl.acm.org/doi/10.5555/646104.681206
Hsu CKnoblock C(2000)Semantic Query Optimization for Query Plans of Heterogeneous Multidatabase SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/69.89580412:6(959-978)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.1109/69.895804
Grant JGryz JMinker JRaschid L(2000)Logic-Based Query Optimization for Object DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/69.86890612:4(529-547)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1109/69.868906
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents