United States Patent
`5,584,024
`{11} Patent Number:
`Dec. 10, 1996
`[45] Date of Patent:
`Shwartz
`
`
`19;
`
`00
`
`[54]
`
`INTERACTIVE DATABASE QUERY SYSTEM
`AND METHOD FOR PROHIBITING THE
`SELECTION OF SEMANTICALLY
`INCORRECT QUERY PARAMETERS
`
`FOREIGN PATENT DOCUMENTS
`0287310
`10/1988 European Pat. Off.
`........ GO6F 15/40
`0387226
`9/1990 European Pat. Off.
`........
`
`
`Japan secsssessessssccccssssenseensee GO6F 7/28
`63-219034
`9/1988
`
`[75]
`
`Inventor: Steven P. Shwartz, Orange, Conn.
`
`OTHER PUBLICATIONS
`
`.
`[73] Assignee: Software AG, Germany
`
`[21] Appl. No.: 217,099
`[22]
`Filed:
`Mar. 24, 1994
`[51]
`Int. Choeen GO6F 17/30; GO6F 17/27
`[52] US. Che cccccccscsusecsecce 395/604; 395/922; 395/757;
`364/274.2; 364/275.4; 364/283.3; 364/DIG. 1;
`364/972.2; 364/974.6; 364/DIG. 2
`[58] Field of Search ou... 395/600, 922;
`364/419.01, 419.07, 974.6, 972.2, 274.2,
`974.7. 275.1. 275.4, 283.3. 282.1
`”
`”
`™
`~
`.
`
`[56]
`
`.
`References Cited
`
`U.S. PATENT DOCUMENTS
`3/1985 Shaw et al. sasscssssscsereresenee 364/300
`4,506,326
`.. 364/300
`8/1987 Thompsonetal. ..
`4,688,195
`
`.. 3647200
`8/1987 Grant
`rssssssseeen
`4,689,737
`5/1988 Katayamaetal........
`"364/419
`4.736.296
`
`3/1989 Hikita et al. wu.
`.. 364/200
`4,811,207
`... 364/200
`5/1989 Tennantetal.......
`4,829,423
`
`.. 364/900
`6/1989 Deerwesteret al.
`.
`4,839,853
`
`3/1990 Loatmanetal. .
`«. 364/419
`4,914,590
`... 364/300
`5/1990 Touetal.......
`4,930,071
`
`
`w 364/419
`5/1990 Ohiiraetal.......
`4,931,935
`7/1990 Miyamotoetal...
`.. 364/513
`4,943,933
`-- 364/900
`11/1990 Amirghodsietal.
`4,974,191
`. 364/419
`2/1991 Asakawa...
`4,994,967
`
`
`
`-- 364/419
`3/1992 Carlgren et al
`5,099,426
`......
`w+ 395/161
`ooreos 0toes ouck et al.
`ee“71993 5 oe et a
`™ soe
`
`”
`al.
`3237502
`81993 White ein ef
`5237,
`ite et al.
`......
`.. 364/419
`
`5,255,386
`10/1993 Prager..........
`... 395/600
`"364/419
`5,265,014
`11/1993 Haddock et al
`.. 395/600
`5,265,065
`11/1993 Turtle ........
`
`.
`5,349,526
`9/1994 Potts, Sr. et al.
`364/419.1
`....essesssseesesses 395/600
`5,386,556
`1/1995 Hedim et al.
`
`
`
`Wu, “A Knowledge-Based Database Assistant With A Menu
`Based Natural Language User—Interface” 10 Oct. 1993,
`JEICI: Trans. Inf. & Syst. V. E76-D N. 10 pp. 1276-1287.
`(List continued on next page.)
`Primary Examiner—Wayne Amsbury
`Assistant Examiner—Jack M. Choules
`.
`.
`:
`Auomey,Agent,orFirmHowrey & Simon; C. Scott
`,
`,
`[57]
`ABSTRACT
`th
`:
`A datab
`tem
`includ
`that
`atabase query system includes a query assistant
`permits the user to enter only queries that are both syntac-
`tically and semantically valid (and that can be processed by
`an SQL generator to produce semantically valid SQL).
`Through the use of dialog boxes, a user enters a query in an
`intermediate English-like language which is easily under-
`stood by the user. A query expert system monitors the query
`asitis meine built, and using information apoee structure
`OF
`the database,it prevents the user
`trom building seman-
`tically incorrect queries by disallowing choicesin the dialog
`boxes which would create incorrect queries. An SQL gen-
`«erator is also provided which uses a set of transformations
`and pattern substitutions to convert the intermediate lan-
`guage into a syntactically and semantically correct SQL
`query.
`
`The intermediate language can represent complex SQL
`queries while at the same time being easy to understand. The
`intermediate language is also designed to be easily con-
`verted into SQL queries. In addition to the query assistant
`and the SQL generator, an administrative facility is provided
`which allows an administrator to add a conceptual layer to
`the underlying database makingit easier for the user to query
`the database. This conceptual layer may contain alternate
`ae
`names for columnsand tables, paths specifying standard and
`.
`ve
`:
`complex joins, definitions for virtual tables and columns,
`and limitations on user access.
`
`27 Claims, 26 Drawing Sheets
`
`User
`
`
`
`
`
`3
`
`Database
`
`A
`d
`m
`1
`a
`i
`s
`t
`
`F°
`
`°
`r
`
`
`
`10
`
`Query
`Assistant
`
`Q
`u
`e
`r
`Esperant
`y
`Language
`Query
`s
`,
`20
`t
`SQL
`e
`Generator
`m
`
`
`
`Page | of 63
`
`GOOGLEEXHIBIT 1022
`
`GOOGLE EXHIBIT 1022
`
`Page 1 of 63
`
`

`

`5,584,024
`Page 2
`
`OTHER PUBLICATIONS
`
`Wu et al, “KDA: A Knowledge-Based Database Assistant
`With Query Guiding Facility” 5 Oct. 1992, pp. 443-453,
`IEEE Transactions On Knowledge & Data Eng. V. 4 N. 5.
`Cha, “Kaleidoscope: A Cooperative Menu Guided Query
`Inerface (SQL Version),” 1990, IEEE, Artifical Intelligence
`Applications.
`Whitaker and Bonnell “Functional Modelling Of Intelligent
`Systems Using A Blackboard Model” 1992, pp. 1 to 12, The
`Journal Of Knowledge Eng. V 5, N. 1.
`Winston, P., “Language Understanding,” Artificial Intelli-
`gence, 9:291-334 (1984).
`Rich, E., “Natural Lanugage Interfaces,” Computer, pp.
`39-47 (Sep. 1984).
`Manferdelli, J. L., “Natural Language Interfaces: Benefits,
`Requirements, State of the Art and Applications,” A/ East,
`Oct. 1987.
`Schank, R. C., et al, “Inside Computer Understanding: Five
`Programs Plus Miniatures,” 14:354-372, LEA, Publishers,
`Hillsdale, NJ (1981).
`Hendrix, G., “The Lifer Manual: A Guide to Building
`Practical Natural Language Interfaces” (Technical Note
`138); SRI International, Feb. 1977.
`
`Hendrix, G., “Human Engineering for Applied Natural Lan-
`guage Processing” (Technical Note 139); SRI International,
`SRI Project 740D32 CTC, Feb 1977.
`Kao, M., et al, “Providing Quality Responses with Natural
`Language Interfaces: The Null Value Problem,” JEEE 14:7,
`959-984,Jul., 1988.
`
`Chapter 6, “Queries,” Building Access Z Applications, 1995.
`Chapter 8, “Using Query by Example,” Using Access 2 for
`Windows, Sp. Ed.
`Chapter 9, “Querying Your Data,” Inside Paradox 5 for
`Windows, 1994.
`
`Cinque,L., et al, “An Expert Visual Query System,” J. Vis.
`Lang. and Comp., 2:101-113 (1991).
`
`Meng,W., et al. “A Theory of Translation From Relational
`Queries to Hierarchial Queries,” JEEE Transactions on
`Knowledge and Data Engineering, 7:2, 228-245, Apr. 1995.
`Jakobson, G., et al, “CALIDA: A System for Integrated
`Retrieval from Multiple Heterogeneous Databases,” Pro-
`ceedings of the 3rd Int'l] Conf. on Data and Knowledge
`Bases:
`Improving Usability and Responsiveness,
`Jun.
`28-30, Jerusalem, Israel.
`
`Page 2 of 63
`
`Page 2 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 1 of 26
`
`5,584,024
`
`
`
`
`
`USTO- STATE| ZIP_|SALESNAME CITY |CREDIT_|BALANCE
`
`
`
`
`
`
`OQ
`
`|TBterertoa[MBFT fTSmse
`
`
`2|Barn Door
`Furniture
`
`[Boston
`| 3iBond Dinettes
`22827|~~ 4f_—«50000
`500
`| {Carroll Cut-Rate |Los Angeles
`23019
`50000
`|
`
`
`pemaetaeparece eee
`5
`
`
`eeEeSalvage
`
`Ce,
`Furniture
`
`/—GiistaDesigns—[StamfordJOT|2es6]5] —soanoa0
`
`
`
`zeaeo]|so000[
`FIG. 1A
`
`1]American
`
`New Haven
`
`|CT
`
`16516
`
`1]
`
`65000
`
`85000
`
`New York
`
`NY
`
`1101
`
`co
`
`50000
`
`75000
`
`Showrooms
`
`
`
`PRODUCTS
`PRO- GROUP_|TYPE_} ABC_}PRICE |VENDOR|NAME ALT_
`
`
`
`
`
`
`
`DUCT# ID)|CODID # |VENDOR
`
`
`#
`
`|____ColonialBedroomSet|100]600jB_s|Save]]SCS
`
`
`
`
`
`Set
`|___4{5Pc.LivingRoomSet]100]500/As[|4805|tC
`|___5\Crib/DresserSet__[100]400[B_[oes]Ssi]si(itisCd
`
`|BunkBed_|100] 00|r]SC
`
`|7)3Pe.DiningRoomSei100_s00|A___|005]al!——*d
`
`
`|84Po.OfficeSet_—|200300fB_|005]
`[achitsDesk[___t00fooo|_a0gf_——sfSS
`
` a
`
`
`Tables Set
`
`Page 3 of 63
`
`Page 3 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 2 of 26
`
`5,584,024
`
`
`
`po VENDORS
`
`
`
`CODE_TEXT
`-
`| 100/Home Furnishings
`Office Furnishings
`
`|@wmNT”n
`
`
`uvenile Furnishings
`Occasional Furnishings
`
`
`Page 4 of 63
`
`Page 4 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 3 of 26
`
`5,584,024
`
`Oo:
`
`ooooo1}
`
`USTO
`FREIGHT_
`SHIP_
`STATUS
`O
`MER#
`PERSON
`
`DOLLARS=-)
`DATE
`
`i
`aa}1992-41-15]
`pe
`
`
`
`
` [COysryMmkeOaoDhb™NPh|CO[COJ[xSINheONETRON2OOR1pseePSSAESooPSEP[SOPTTleoTEPTFSISLAPoLUELTarEONTED?|DP[OP[SSES|aePP[DPLyPIDQP(OleIPI[OmpSESay[OeWi}WuNIPONE|oe1T'1vryONyoTINYPENTPODPONJOINTSTLOLNTPONTOTOLocaD>{|SD?D/|am/H|ari~mawefmEm|OD1OD|GD|Od|OD|OD|[OD|ODJFDIDFf—|[|—1D[HDMH|HDLDID[D/H|-—1HJINIeINTPeUTNyctOla=D2DIDININAUNIQUIQNNTODEQNUIONIIONION
`
`
`O}1|Oweeeeoeeeii—I1o—_—1HI—a—~[7
`
`aoOo|[LOTTLO[eeILO|O[LO|SD/OtO[OO[LOTANTOITNFloLO|eLON|TICOFCOLL<Gwolrcoce|N[09[I[ONPCOTRENFLOF<CVO][COFCO
`
`
`
`lOspOlOlae/[SlOlOlqofjosolololaojoxfeemwefelefeeeeeeeeeeeeeieeeeieenenmemeeePISPOPEJOSSJOJOOOO[SO[OSsOjOsolfojsOlololjolojol|oloDB11S[CO[SO[ONS[OLS[OOOlS[SPJOlOl/Sslaol/Olql/Olsiqgloso/oelcoiaINIAINS[OO[OE[SO[OfSl[OlClOJOlOl/Sl[Sl[OsOl[OSslol/OSsljolOoiol/oloclosjoloals|oSOOO[SOOlOOslOEJlOse[Os[OPO 1aLo[=LoIO|oOLCO(MILOj[LOfLOl/mIaIloiqWOlOlO/Ol(/Cl/oO!oO[Od|D>1S?|D>[DID[D/HIDD|/DIDIDIMD/[DIN|[DHIDIN([D!IDIN1Di
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`<——WD——|YKLO[COPTIT[MOLO
`
`TIN[OOPSPOLOIRM[DWIDLOl[THINl[oOlplolOlrRlO!HD/O[—IN/eolst[tojoo[rm[a[amSPSJOlSlOQliQlpCpePosel(TPoCICINININAINENQIAIN
`
`
`
`
`
`
`
`=r—N+NSNScoNNS—_——_bheed
`
`
`|6B
`
`O
`pe
`
`|||p
`
`e
`Pe
`
`|B
`
`o
`
`1992-2-24
`
`1992-3-27
`
`39540] 124
`47320| 124
`
`6010] 124
`3225
`12005] 124
`36240]
`
`25110
`
`1992-3-22
`1992-6-28
`1992-10-10
`
`124
`1992-4-10
`4
`124, 4]--1992-7-29
`124
`1) 1992-11-12
`1244 st} 1992-5-15
`124
`1
`1992-8-22
`a)
`
`1992-6-25
`
`1992-8-25
`
`2 1
`
`24
`3} 1992-11-24
`1244 3]: 1992-1-24
`1244 3}: 1992-4-26
`3]
`1992-7-29
`124
`
`62
`
`1992-2-27
`
`1992-5-26
`
`6150
`
`—_——
`
`<<|
`
`FIG. 1F
`
`Page 5 of 63
`
`Page 5 of 63
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 4 of 26
`
`5,584,024
`
`LINE_ITEMS
`
`ORDER#
`
`Qo.
`
`CmcoLL~GO
`
`<a©WwW
`
`10000
`
`—)
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`100000
`
`FIG. 1G
`
`Page 6 of 63
`
`thTONEeepmERNEEOD[PLOF<TN09[et[00Pe[eeeeeRPeIe
`Te.=—_!
`
`lacWWCerOHeTNTOTTo~~oO
`eeetO~OQ©ao
`stSTToeoPmIONTC
`oOl™NNonNN
`TINOPS[LS[alSISOL/LO[wofro|w[rnfolml(o
`Seeeeeiefieeeeeeme
`
`
`spojpoloasloqojolo|l|c!|coPIOPOLO[OPOLOlSOjoVGiololselol/olqclJoloClOlOlO/OjOslOliel/@lWVsIoClolol/os/ol/ol[ol|oSIOlOlOlOsOlOloleo{CIOOOfoo/OsOJOOsoOiql/ol/elolioljo!lco
`
`
`
`
`
`DjlOlO(OOJeeerecyeae
`TTIONODO09109[OO(OOPtPSstpt[se
`_—
`
`a>OocLum<==
`
`woTesNoo[9[REN
`
`4
`
`—_——
`
`2
`
`4
`
`1 N
`
`3
`
`Page 6 of 63
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 5 of 26
`
`5,584,024
`
`
`
`LINE_ITEMS
`
`|aF
`T||[
`
`
`
`tooooze]foSC
`ee
`of
`eySC~—~SYSC“‘CSSC~*
`
`
`
`FIG. 1G (Continued)
`
`Page 7 of 63
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ORDERED}
`ORDERED
`roo,tCCSC~‘“S
`Proooor)atSSCSCCSSCS
`FC
`a|
`0|
`iooooie]af
`
`aAt
`
`o000g]a]ofTF
`2|
`tooo]fCSSCS
`
`Ai
`
`oooaza]a]CSCC
`tooooz|afCSCSCiYSC;C;*~CS
`rroooaas|ifCi
`Ftooon2e)af
`
`Page 7 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 6 of 26
`
`5,584,024
`
`Query Builder
`
`Tables
`
`pst|DBooOrder
`
`—
`Conditions
`
`Figure 2A
`
`Tables
`
`CUSTOMER.DB
`
`Query Builder
`
`Sort Order
`
`NAME
`STATE
`
`Figure 2B
`
`Page 8 of 63
`
`Page 8 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 7 of 26
`
`5,584,024
`
`SELECT
`NAME
`STATE
`BALANCE
`
`FROM
`
`CUSTOMER.DB
`ORDER BY
`NAME
`
`Figure 2C
`
`Conditions
`CREDIT > 50000
`
`STATE
`
`
`
`
`Connector Operator—ExpressionField
`
`Co CT
`
`Figure 2D
`
`Page 9 of 63
`
`Page 9 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 8 of 26
`
`5,584,024
`
`
`
`Query Builder
`
`|
`
`Tables
`CUSTOMER.DB
`
`
`
`Fields
`
`NAME
`
`
`STATE
`BALANCE
`
`
`NAME
`
`STATE
`
`Conditions
`
`
`
`CREDIT > 50000
`
`
`Sort Order
`
`
`
`
`
`Figure 2E
`
`
`
`AME
`STATE {BALANCE
`
`I
`CT
`85000
`>3 @m =O°om S oO=.QO=a © =S
`
`
`Block
`|CD
`
`
`
`orch And Patio
`Figure 2F
`
`Page 10 of 63
`
`Page 10 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 9 of 26
`
`5,584,024
`
`Tables
`CUSTOMER.DB
`
`Query Builder
`Fields
`
`Sort Order
`
`NAME
`STATE
`
`Conditions
`
`CREDIT > 50000
`
`
`
`Group B
`SALESPERSON#
`
`Having
`SUM(BALANCE)> $80,000
`
`Figure 2G
`
`
`
`Join Tables
`
`
`
`ORDER.DB
`CUSTOMER.DB
`
`
`
`
`
`ORDER#
`CUSTOMER#
`
`CUSTOMER#
`NAME
`
`
`
`
`
`
`ORDER_DATE
`CITY
`
`
`
`
`ORDER_DOLLARS
`STATE
`
`
`
`FREIGHT_DOLLARS
`ZIP_CODE
`
`
`
`SALESPERSON#
`SALESPERSON#
`
`
`
`
`SHIP_DATE
`CREDIT
`
`
`
`STATUS
`BALANCE
`
`
`
`
`Figure 2H
`
`Page 11 of 63
`
`Page 11 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 10 of 26
`
`5,584,024
`
`order by 2 desc;
`
`Natural Language
`File Questions Report Column/Table Configure Query Graph Help
`Natural Language
`: What were the 5 most commondefects last month?
`Whatwere the 5 defects that occurred the most in June, 1991
`Defect
`Count
`Contamination
`1213
`Damagein handling
`516
`Surfacefinish
`423
`Bad soldering
`315
`Cracked board
`273
`: Show the SQL
`List the query.
`Query for: What were the 5 most commondefects last month?
`select repair.def_cd, count(repair.mod_pn)
`from repair
`where repair.tstr_strt>='6/1/1991'
`and repair.tstr_strt<'7/1/1991'
`group by repair.def_cd
`
`Figure 3A
`
`Page 12 of 63
`
`Page 12 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 11 of 26
`
`5,584,024
`
`File Edit Questions Notes Topics Configure
`Questions
`Edit Question
`
`Showall
`Questions
`
`Hel
`
`Browse
`Questions
`
`eachfactory.
`
`Which products are manufacturedin Biloxi?
`How manyrepairs did we perform last week?
`List the top 5 defects last month.
`Comparetotal defects this month to last month.
`Whichstation performed the most repairs?
`List all the sourcesof bolts.
`Whosupplies the best panels?
`Whenwascontrolplan z-557 updated?
`How many units were producedafter 6/1/91
`When is xz989 duefor calibration?
`Showtheyields for each factory.
`Pie chart the total units produced by
`
`Figure 3B
`
`Page 13 of 63
`
`Page 13 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 12 of 26
`
`5,584,024
`
`Administrator
`
`
`
`“7
`!
`
`
`
`
`moment
`Natural
`Developer
`
`
`
`
`
`System
`Language
`Toolkit
`
`
`
`
`Interface
`
`
` Oracle
`Meaning
`DBMS
`Representatiion
`Tables
`
`
`
`
`Database
`Expert
`System
`
` Retrieval
`!
`Generator
`Generator
`
`
`Specification
`
`Navigator/
`MQL
`
`MQL
`
`Oracle SQL
`
`SQL
`
`Fig. 4
`
`Page 14 of 63
`
`Page 14 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 13 of 26
`
`5,584,024
`
`User
`
` 10
`
`Q
`u
`e
`r
`y
`
`S
`
`y
`
`S
`t
`©
`m
`
`A
`d
`m
`i
`n > [Conceptual
`Layer
`
`2
`
`Ss
`
`2
`
`t
`0
`r
`
`FIG. 5
`
`Page 15 of 63
`
`°
`Assistant
`
`Esperant
`Language
`Query
`
`|
`
`
`
`SQL
`Generator
`
`
`
`3
`
`Database
`
` Query
`
`Page 15 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 14 of 26
`
`5,584,024
`
`SALESPEOPLE
`
`VENDORS
`
`CODES
`
`CUSTOMERS
`
`@
`
`@
`
`PRODUCTS
`
`ORDERS
`
`LINE_ITEMS
`
`FIG. 6
`
`Page 16 of 63
`
`Page 16 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 15 of 26
`
`5,584,024
`
`Query Assistant Expert System 12 Query Assistant 10
`
`Blackboard
`
`13
`
`Query Assistant
`User Interface
`(QAUI)
`
`(QAES)
`
`FIG. 7
`
`Page 17 of 63
`
`Page 17 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 16 of 26
`
`5,584,024
`
`50
`
`User Initiates
`Query
`
`|
`
`52
`
`Blackboard is
`initialized
`
`
`
`
` QAESprovides
`a list of all selectable
`
`tables, columns, and/or
`
`
`
`Intermediate Lang.
`operationsto the
`
`representation is
`
`
`updated
`64
`
`
`
`Intermediate Lang.
`
`
`
`QAUI
`representation is
`
`
`distinguishes
`
`cleared
`
`nonselectables
`
`
`
`QAUI creates the correct
`
`dialog box and requestslist
`of selectable, tables,
`columns and/or operations
`
`
` Blackboardis
`
`
`updated with
`user's choice
`
`
` Did
`
`
`
`user select
`
`to clear the
`query?
`
`
`FIG. 8
`
` Did
`
`user select to
`
`
`Page 18 of 63
`
`Page 18 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 17 of 26
`
`5,584,024
`
`File Que
`
`Options Window Help
`
`SQL Query
`
`User Query
`
`Fig. 9
`
`Page 19 of 63
`
`Page 19 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 18 of 26
`
`-—
`
`5,584,024
`
`121d
`
`121a
`
`121
`
`EE
`
`
`
`120
`
`
`
`
`
`
`"Show|Template . 122a
`
`@| Show...
`© For... © SortedBy...
`Run Query
`122b
`
`
`
`
`0) With % ofTotal... NY
`[Cancet|
`129
`
`
`
`
`121c
`121b
`
`
`
` Computation...
`Select Items For Show Clause
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Min|None|
`[ff|ffPOSH
`128
`124
`430h
`
`130c
`
`fi
`
`129
`
`FIG. 10A
`
`Page 20 of 63
`
`
`
`127b
`
`
`
`
` 125
`
`
`
`
`a30¢
`190d 130g
`
`123
`
`126
`
`130a
`
`130b
`
`an
`
`SelectAll
`Columns
`Tables
`
`
`
`MLRe HE COUNT OF CUSTOMERS
`
`
`CREDIT LIMIT
`CUSTOMER BALANCE
`
`CUSTOMERCITY
`CUSTOMER NAME
`
`Description
`
`a M
`
`odify Selected Columns
`
`—
`
`elete All
`
`Count
`
`Ave
`
`Page 20 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 19 of 26
`
`5,584,024
`
`121
`
`120
`
`Grate Show.Che|
`"Show ..."" Template[RunQuery_|122a
`© For... © Sorted By ...
`Run Query
`@ Show...
`
`CO With % of Total...
`
`Select Items For Show Clause
`
`Tables
`
`Columns
`
`Select All
`
`HE COUNT OF CUSTOMERS
`
`Min
`
`Description
`
`Customer Records.
`
`Modify Selected Columns
`CUSTOMERBA
`
`sy
`
`130
`
`129
`
`FIG. 10B
`
`Page 21 of 63
`
`Page 21 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 20 of 26
`
`5,584,024
`
`Create "Show..." Clause
`"Show..." Template
`@ Show...
`© For... © Sorted By...
`
`C) With % of Total...
`
`Select Items For Show Clause
`
`Tables
`
`Columns
`
`420
`
`a
`
`y
`
`130b
`
`CUSTOMER BALANCE
`CUSTOMER CITY
`
`USTOMER NAME
`
`
`
`Description
`
`The Customer's credit limit.
`
`Modify Selected Columns
`
`THE AVERAGE CUSTOMER BALAN
`
`FIG 10C
`
`Page 22 of 63
`
`Page 22 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 21 of 26
`
`5,584,024
`
`Computation
`
`|
`
`Mini
`O Intimum
`
`
`
`Select a column
`
`
`oO Total
`
`
`
`© Average O Maximum
`
`
`
`Tables
`Columns
`THE COUNT OF CUSTOMERS|
`
`USTOMERBALANCE
`
`
`USTOMER CITY
`YUSTOMER NAME
`
`,USTOMER NUMBER
`
` PRODUCTS
`
` Computation:
`
`135
`
`FIG 10D
`
`Page 23 of 63
`
`Page 23 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 22 of 26.
`
`5,584,024
`
`
`
`Create "Sorted By..." Clause
`
`
`
`R
`
`"Show ..." Template
`© Show...
`© For...
`@ Sorted By...
`un Query
`
`
`
`C1) With % of Total...
`
` Columns
`
` USTOMERCITY
`
`USTOMER NAME
`
`
`Select Items Already in the Show Clause
`
`
`THE AVERAGE CUSTOMER BALANCE
`
`
`
`
`
`
`
`Modify Selected Columns
`
`
`
`
`
`
`we
`
`140
`
`FIG 10E
`
`Page 24 of 63
`
`Page 24 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 23 of 26
`
`5,584,024
`
`Create "For..." Clause
`
`@ For...
`C1 With % of Total...
`
`O Sorted By .
`
`Run Query
`
`Backup
`
`Choose one of the following
`
`THAT HAVE
`THAT DO NOT HAVE
`
`select
`
`151
`
`FIG 10F
`
`Page 25 of 63
`
`Page 25 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 24 of 26
`
`5,584,024
`
`Create "For..." Clause
`
`"Show ..."" Template
`
`2 Ouer
`
`
`© Show... O Sorted By...[RunQuery|Query@ For...
`
`
`
`
`
`
`
` C] With % of Total...
`
`
`© Minimum
`
`
`
`
`
`
`PRODUCTS
`
`
`
`Description
`
`
`O Total
`
`Back
`
` .
`
`© Average O Maximum
`
`Columns
`
` Customer Records.
`
`FIG 10G
`
`160
`
`Page 26 of 63
`
`Page 26 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 25 of 26
`
`5,584,024
`
`402
`
`404
`
`Tokenize Word List }<——— Intermediate
`Language Query
`
`Convert by
`pattern substitution
`
`410
`
`Generate
`CREATE VIEW
`
`
`406
`
`matched patterns?
` YES
`
`NO
`
`
`Recursively call
`
`SQL generator
`for each view
`
`A Generator
` Convert to internal
`
`412
`
`£3
`
`format
`
`Convert WHEREby 416
`pattern subsitution
`
`
`
`YES
`
`
`matched patterns?
`
`NO
`
`418
`
`
`
`Convert table
`references
`
`Add ORDER BYcol.
`to SELECT
`
`Convert dates
`
`420
`
`422
`
`424
`
`FIG. 141A
`
`Page 27 of 63
`
`Page 27 of 63
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 26 of 26
`
`5,584,024
`
`FIG. 11B
`
`426
`
`y
`Expand virtual
`columns
`
`428
`
`Create FROM Clause
`
`4
`
`30
`
`Convert ORDER BY
`to positional notation
`
`4
`
`32
`
`Compute joins paths
`
`434
`
`436
`
`FROM clause
`
`Add tables to
`
` 438
`
`440
`
`Add SELECT DISTINCT
`if necessary
`
`442
`Add GROUP BYand
`SUM if necessary
`
`Add COUNT(*)
`if necessary
`
`644
`
`Convert internal
`format to SQL
`
`————& SQL QUERY
`
`Page 28 of 63
`
`Page 28 of 63
`
`

`

`5,584,024
`
`1
`INTERACTIVE DATABASE QUERY SYSTEM
`AND METHOD FOR PROHIBITING THE
`SELECTION OF SEMANTICALLY
`INCORRECT QUERY PARAMETERS
`
`2
`In this example, the SELECT command defines which
`fields to use, the WHERE command defines a condition by
`which database records are selected, and ORDER BY key-
`5 words define how the output should be sorted. The FROM
`keyword defines in which tables the fields are located.
`Unfortunately, only a relatively small percentage of infor-
`mation required can besatisfied with such simple SQL
`BACKGROUND OF THE INVENTION
`The invention relates to a database querying tool, and 10 Most information needs, even very simple queries, require
`specifically to a database querying tool which will guide a
`complex SQL queries. For example,
`the SQL statement
`
`user to interactively create syntactically and semantically required to generatealist of orders that have more than two
`correct queries.
`products on backorder,is:
`
`
`(2)
`
`SELECT T1.ORDER#, TI.ORDER_DATE, T1.ORDER_DOLLARS
`FROM ORDERS T1
`WHERE 2 <(
`SELECT COUNT(*)
`FROM PRODUCTS T2, LINE_ITEMS T3
`WHERE T3.QTY_BACKORDERED> 0
`AND T2.PRODUCT# = T3.PRODUCT#
`AND T1.ORDER# = T3.ORDER#)
`
`30
`
`3
`
`This SQL statement contains two SELECTclauses, one
`End user workstations are being physically connected to 25
`nested with the other. For a user to know thatthis informa-
`central databases at an ever increasing rate. However, to
`tonaaet needs an sol eeinvolving this type of
`access the information contained in those databases, users
`nesting (known as a correlated
`subquery) implies some
`must create queries using a standardized query language
`understanding by the user of the relational calculus. How-
`hich j
`:
`is
`S
`4
`L
`which
`in most
`instances is
`Structured Query
`Language ,, ever, except for mathematiciansand peoplein the computer
`(SQL). Mostinformation system organizations considerit lo
`field, few users have this skill. The following are some
`unproductive to try and teach their users SQL. Asa result
`examples of database queries that require more complex
`there is an increasing interest in tools that create SQL for the
`SQL constructs:
`user using more intuitive methods of designating the infor-
`GROUP BY: Approximately 75% of all ad hoc queries
`mation desired from the database. These tools are generally 35 Tequire a GROUP BYstatement in the SQL. Examples
`called SQL Generators.
`include:
`Show total sales by division.
`Most SQLG
`t
`the market tod
`ear to hid
`
`
`
`
`
`ost Generators onthemarketSQL today app ° Show January sales of bedroom sets to Milford Furniture.
`the complexities of SQL from theuser. In reality, these tools
`Subqueries: The following are examples of database
`accomplish this by severely limiting the range of informa- 40 queries that require subquery constructs which appear as
`tion that can be retrieved. More importantly, these tools
`nested WHERE clauses in SOL:
`make it very easy for users to get incorrect results. These
`Show customersthat have children under age 10 and do
`problemsarise out of the reality that SQL is very difficult to
`not have a college fund.
`learn and use. Existing technologies designedto shield users
`Show orders that have more than 2 line items on backo-
`from the complexities of SQL can be grouped into three 45
`rder.
`categories: point-and-shoot menus; natural language sys-
`HAVING:The following are examples of database que-
`tems; and natural language menu systems. Each of these
`ties that require the HAVING construct:
`three categories of product/technology have architectural
`Show ytd expenses by employee for divisions that have
`deficiencies that prevent them from truly shielding users
`total ytd expenses over 15,000,000.
`from the complexities of SQL.
`Show the name and manager of salesmen that havetotal
`outstanding receivable of more than $100,000.
`CREATE VIEW:Thefollowing are examples of database
`queries that require the
`Limitati
`f
`SOL As An E
`CREATE VIEWsyntax:
`imitations of S Canewee nd User Query
`Show ytd sales by customer with percent oftotal.
`;
`;
`;
`Whatpercent of my salesmen have total ytd sales under
`SQLis, on the whole, very complex. Some information
`$25,000?
`requirements can be satisfied by very simple SQLstate-
`
`ments. For example, to produce from a databasealist of UNION:Thefollowing are examples of database queries
`customer names and phones for New York customers sorted
`that require the UNIONconstruct:
`:
`:
`60
`by zip code, the following SQL statement could be used:
`Show ytd sales for Connecticut salesmen compared to
`
`New York salesmen sorted by product name.
`Show QI sales compared to last year Q1 sales sorted by
`salesman.
`Thus, common information needs require complex SQL
`that is likely to be far beyond the understanding of the
`business people that need this information.
`
`d)
`
`SELECT NAME, PHONE
`FROM CUSTOMERS
`WHERE STATE = ‘NY’
`ORDERBY ZIP_CODE
`
`
`65
`
`Page 29 of 63
`
`Page 29 of 63
`
`

`

`5,584,024
`
`3
`A greater problem than the complexity of SQL is that
`syntactically correct queries often produce wrong answers.
`SQL is a context-free language, one that can be fully
`described by a backus normal form (BNF), or context-free,
`grammar. However, learning the syntax of the language is
`not sufficient because many syntactically correct SQL state-
`ments produce semantically incorrect answers. This problem
`is illustrated by some examples using the database that has
`the tables shown in FIGS. 1A-G.If the user queries the
`database with the following SQL query:
`
`4
`producean incorrectresult. When the Line_Item table is not
`included in the query, the proper result is obtained. Unless
`the users understand the manner in which the database is
`designed and the way in which SQL performsits query
`operations, they cannot be certain that this type of error in
`the result will or will not occur. Whenever a query may
`utilize more then two tables, this type of error is possible.
`Most information systems users would be reluctant to use
`a database query tool that could produce twodifferent sets
`of results for what to them is the same information require-
`
`3)
`
`SELECT CUSTOMERS.NAME, SUM(ORDERS.ORDER_DOLLARS),
`SUM(LINE_ITEMS.QTY_ORDERED)
`FROM CUSTOMERS, ORDERS, LINE_ITEMS
`WHERE CUSTOMERS.CUSTOMER# = ORDERS.CUSTOMER#
`AND ORDERS:ORDER# = LINE_ITEMS.ORDER#
`
`The following results are produced:
`
`
`20
`
`NAME
`
`1 American Butcher Block
`2 Barn Door Furniture
`3 Bond Dinettes
`4 Carroll Cut-Rate
`5 Milford Furniture
`6 Porch and Patio
`7 Railroad Salvage
`8 Sheffield Showrooms
`9 Vista Designs
`
`SUM(ORDER__
`DOLLARS)
`
`SUM(QTY__
`ORDERED
`
`119284
`623585
`51470
`53375
`756960
`1113400
`85470
`101245
`61790
`
`22
`52
`19
`29
`48
`89
`28
`26
`25
`
`25
`
`30
`
`The second column ofthis report appears to show thetotal
`order amount for each customer. However, the numbersare
`incorrect. In contrast, the following query
`
`ment (i.e. total order dollars for each customer). Virtually
`every known database query tool suffers from this short-
`coming.
`A more formal statementof this problem is that the set of
`acceptable SQL statements for an information system is
`muchsmaller than the set of sentences in SQL. This smaller
`set of sentences is almost certainly not definable as a
`context-tree grammar.
`
`Point-And-Shoot Query Tools
`
`Most SQL generator products are “point-and-shoot”
`query tools. This class of products eliminates the need for
`users to enter SQL statements directly by offering users a
`series of point-and-shoot menu choices. In response to the
`user choices, point-and-shoot query tools create SQLstate-
`ments, execute them, and present the results to the user,
`
`4)
`
`SELECT CUSTOMERS.NAME, SUM(ORDERS.ORDER_DOLLARS)
`FROM CUSTOMERS, ORDERS
`WHERE CUSTOMERS.CUSTOMER# = ORDERS.CUSTOMER#
`
`
`produces the correct result:
`
`NAME
`
`SUM(ORDER_DOLLARS)
`
`1 American Butcher Block
`2
`Barn Door Furniture
`3
`Bond Dinettes
`4
`Carroll Cut-Rate
`5 Milford Furniture
`6
`Porch and Patio
`7
`Railroad Salvage
`8
`Sheffield Showrooms
`9 Vista Designs
`
`83169
`129525
`51470
`53375
`111240
`222680
`85470
`101245
`61790
`
`Both SQLqueries are syntactically correct, but only the
`second produces correct numbers forthe total order dollars.
`The problem arises from the fact that before performing the
`selection and totaling functions, the SQL processor performs
`a cross-productjoin on all the tables in the query. In thefirst
`query above,
`three tables are used: Customer (a list of
`customers with customer data): Order(a list of orders with
`dollar amounts); and Line__Item (alist of the individual line
`items on the orders). Since the Order table has the total
`dollars and there are multiple line items for each order, the
`joining scheme of the SQL processor creates a separate
`record containing the total dollars for an order for each
`instance of a line item. Whentotaled by Customer,this can
`
`45
`
`50
`
`55
`
`60
`
`65
`
`appearing to hide the complexities of SQL from the user.
`Examples of this class of product
`include Microsoft’s
`Access, Gupta’s Quest, Borland’s Paradox, and Oracle’s
`Data Query.
`Although such products shield users from SQL syntax,
`they either limit users to simple SQL queries or require users
`to understand the theory behind complex SQL constructs.
`Moreover, because they target the context-free SQL gram-
`mar discussed above, it is easy and commonforusersto get
`incorrect answers. A point-and-shoot query toolis illustrated
`below with several examples showing a generic interface
`similar to several popular query tools representative of this
`genre. The screen of FIG. 2A appears after the user has
`chosen the customertable of FIG. 1A outofa pick list. This
`screen showsthe table chosen and three other boxes, one for
`each of the SELECT, WHERE, and ORDER BYclauses of
`the SQL statement.If the user selects either the ‘Fields’ box
`or the “Sort Order” box,a list of the fields in the customer
`table appears. The user makes choicesto fill in the “Fields”
`and “Sort Order” boxes. In this example, the user chooses to
`display the NAME. STATE, and BALANCEfields, and to
`sort by NAMEand STATE.This produces the screen of FIG.
`2B.
`
`the user can choose to view the SQL
`At any time,
`statementthat is being created as shown in FIG. 2C. There
`is a one-to-one correspondence betweenuserchoices and the
`
`Page 30 of 63
`
`Page 30 of 63
`
`

`

`5,584,024
`
`5
`SQL being generated. To fill in the WHERE clause of the
`SQLstatement being compiled, the user chooses the “Con-
`ditions” box andfills in the dialog box of FIG. 2D to enter
`a condition. This produces the completed query design
`shown in FIG. 2E. The user then chooses the “OK” button
`to run the query and see the results shown in FIG. 2F.
`For queries that involve only a simple SELECT, WHERE,
`and ORDERBY statement for a single table, a user can
`readily create and execute SQL statements without knowing
`SQLor even viewing the SQLthat is created.
`Unfortunately, only a small proportion of user queries are
`this simple. Most database queries involve more complex
`SQL. Toillustrate this point, consider a user who wishesto
`see the same information as in the above example, but to
`limit the data retrieved to customers of salespersons with
`total outstanding balanceof all the salesperson’s customers
`greater then $80,000. If the user realizes that this query
`requires two additional SQL clauses (a GROUP BY clause
`and a HAVINGclause) the query (shown in FIG. 2G) can be
`readily constructed. However, few users are sufficiently
`familiar with SQL to do so.
`Most point-and-shoot query tools cannot handle other
`complex SQL constructs such as subqueries. CREATE
`VIEW and UNION.Theyoffer no way (other than entering
`SQLstatements directly) for the user to create these other
`constructs. Those products that do offer a way to generate
`other complex constructs require the user to press a “Sub-
`query” or “UNION” or “CREATE VIEW” button. Of
`course, only users familiar enough with the relational cal-
`culus to know how to break a query up into a subquery or
`use another complex SQL construct would know enough to
`press the right buttons.
`Additional complexity is introduced when data must be
`retricved from more than onetable. As shown in FIG. 2H,
`the user may be required to specify how to join the tables
`together. The typical user query will involve at least three
`tables. Problems that can arise in specifying joins include:
`the columns used to join tables may not have the same
`name;
`
`the appropriate join between two tables may involve
`multiple columns;
`there may be alternative ways of joining two tables; and
`there may not be a wayofdirectly joining two tables,
`thereby requiring joins through other tables not otherwise
`used in the query.
`In summary, point-and-shoot query tools shield users
`from syntactic errors, but still require users to understand
`SQLtheory. The othercritical limitation of point-and-shoot
`menu products is that they target
`the context-free SQL
`language discussed above. A user seekingtotal order dollars
`could as easily generate incorrect SQL statement (3) as
`correct SQL statement
`(4) above. Thus,
`these products
`generate syntactically correct SQL, but not necessarily
`semantically correct SQL. Only a user that understands the
`relational calculus can be assured of making choices that
`generate both syntactically correct and semantically correct
`SQL. However, most information system users do not know
`relational calculus. Moreover, when queries require joins,
`there are numerous way of making errors that also produce
`results that have the correct format, but the wrong answer.
`
`Natural Language Query Tools
`
`Natural language products use a different approach to
`shielding users from the complexities of SQL. Natural
`language products allow a user to enter a request for
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`information in conversational English or some other natural
`language. The natural language product uses one mechanism
`to deduce the meaning of the input, a second mechanism to
`locate database elements that correspond to the meaning of
`the input, and a third mechanism to generate SQL.
`Examples of natural language products include Natural
`Language from Natural Language Inc. and EasyTalk from
`Intelligent Business Systems (described in U.S. Pat. No.
`5,197,005 to Shwartz et al.).
`FIG. 3A shows a sample screen for a natural language
`query system which showsa user query, the answer, another
`query requesting the SQL, and the SQL.
`The sequence of int