On implicate discovery and query optimization
Tóm tắt
Boolean expression simplification is a well-known problem in the history of computer science. The problem of determining prime implicates from an arbitrary Boolean expression has been mostly studied in the contexts of hardware design and automated reasoning. While many of the same principles can be applied to the simplification of search conditions in ANSI SQL queries, the richness of its language and SQL's three-valued logic present a number of challenges. We propose a modified version of a matrix-based normalization algorithm suitable for normalizing SQL search conditions in constrained-memory environments. In particular we describe a set of tradeoffs that enable our algorithm to discover a useful set of implicates without requiring a complete conversion of the input condition to a normal form, preventing a combinatorial explosion in the number of terms.
Từ khóa
#Query processing #History #Computer science #Logic #Relational databases #Hardware #Explosions #Minimization #Boolean functions #Switching circuitsTài liệu tham khảo
zhang, 1996, SQL Predicate Conversion in Multidatabase Systems, 20
wang, 1992, Transforming normalized Boolean expressions into minimal normal forms
vorwerk, 2000, Implicate discovery and query optimization in SQL Anywhere Studio, Technical report iAnywhere Solutions
1999, Transaction Processing Performance Council, San Jose California TPC Benchmark H (Decision Support) Standard Specification
10.1145/131214.131223
10.1007/3-540-55602-8_170
10.1007/3-540-52885-7_113
10.1109/TCE.1953.6371932
10.1016/S0747-7171(08)80029-6
levy, 1994, Query optimization by predicate move-around, Proceedings of the 20th International Conference on Very Large Data Bases, 96
10.1007/BFb0022162
10.1145/174130.174135
o'neil, 1994, Database Principles Programming Performance
o'neil, 1993, The set query benchmark, The Benchmark Handbook for Database and Transaction Processing Systems, 359
10.1007/BF00249017
10.1145/240518.240555
slagle, 1970, a new algorithm for generating prime implicants, IEEE Transactions on Computers, c 19, 304, 10.1109/T-C.1970.222917
10.1016/0012-365X(78)90168-1
garcia-molina, 2000, Database System Implementation
10.1109/PGEC.1967.264648
10.1109/DAC.1992.227866
hwa, 1974, a method for generating prime implicants of a boolean expression, IEEE Transactions on Computers, c 23, 637, 10.1109/T-C.1974.224003
10.1145/375663.375706
10.1145/304182.304201
1999, International Standards Organization. (ANSI/ISO), 9075–2 SQL Foundation
aho, 1986, Compilers Techniques and Tools
10.1016/S0004-3702(99)00035-1
10.2307/2307285
10.2307/2308219
10.1023/A:1005721905269
10.2307/2310460
shekhar, 1988, A formal model of trade-off between optimization and execution costs in semantic query optimization, Proceedings of the 14th International Conference on Very Large Data Bases, 457
10.1007/3-540-56944-8_60