select.html (18331B)
1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/1998/REC-html40-19980424/loose.dtd"> 2 <html lang="en"> 3 <head> 4 <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 5 <title>The 'select' Predicate</title> 6 <link rel="stylesheet" href="doc.css" type="text/css"> 7 </head> 8 <body> 9 <a href="mailto:abu@software-lab.de">abu@software-lab.de</a> 10 11 <h1>The 'select' Predicate</h1> 12 13 <p align=right>(c) Software Lab. Alexander Burger 14 15 <p>The <a href="ref.html#pilog">Pilog</a> <a 16 href="refS.html#select/3">select/3</a> predicate is rather complex, and quite 17 different from other predicates. This document tries to explain it in detail, 18 and shows some typical use cases. 19 20 <p><ul> 21 <li><a href="#syntax">Syntax</a> 22 <li><a href="#example1">First Example</a> 23 <li><a href="#univar">Unification Variables</a> 24 <li><a href="#gencl">Generator Clauses</a> 25 <ul> 26 <li><a href="#db">B-Tree Stepping</a> 27 <li><a href="#interaction">Interaction of Generator Clauses</a> 28 <li><a href="#combined">Combined Indexes</a> 29 <li><a href="#associations">Indirect Object Associations</a> 30 <li><a href="#nested">Nested Pilog Queries</a> 31 </ul> 32 <li><a href="#filcl">Filter Clauses</a> 33 <ul> 34 <li><a href="#little">A Little Report</a> 35 <li><a href="#filpr">Filter Predicates</a> 36 </ul> 37 </ul> 38 39 40 <p><hr> 41 <h2><a name="syntax">Syntax</a></h2> 42 43 <p><code>select</code> takes at least three arguments: 44 45 <p><ul> 46 <li>A list of unification variables, 47 <li>a list of generator clauses 48 <li>and an arbitrary number of filter clauses 49 </ul> 50 51 <p>We will describe these arguments in the following, but demonstrate them first 52 on a concrete example. 53 54 55 <p><hr> 56 <h2><a name="example1">First Example</a></h2> 57 58 <p>The examples in this document will use the demo application in "app/*.l" (see 59 also "<a href="app.html#minApp">A Minimal Complete Application</a>"). To get an 60 interactive prompt, start it as 61 62 <pre><code> 63 $ pil app/main.l -main + 64 : 65 </code></pre> 66 67 <p>As ever, you can terminate the interpreter by hitting <code>Ctrl-D</code>. 68 69 <p>For a first, typical example, let's write a complete call to <a 70 href="refS.html#solve">solve</a> that returns a list of articles with numbers 71 between 1 and 4, which contain "Part" in their description, and have a price 72 less than 100: 73 74 <pre><code> 75 (let (Nr (1 . 4) Nm <u>Part</u> Pr '(NIL . 100.00)) 76 (solve 77 (quote 78 @Nr Nr 79 @Nm Nm 80 @Pr Pr 81 (select (@Item) 82 ((nr +Item @Nr) (nm +Item @Nm) (pr +Item @Pr)) 83 (range @Nr @Item nr) 84 (part @Nm @Item nm) 85 (range @Pr @Item pr) ) ) 86 @Item ) ) 87 </code></pre> 88 89 <p>This expression will return, with the default database setup of "app/init.l", 90 a list of exactly one item <code>({3-2})</code>, the item with the number 2. 91 92 <p>The <code><a href="refL.html#let">let</a></code> statement assigns values to 93 the search parameters for number <code>Nr</code>, description <code>Nm</code> 94 and price <code>Pr</code>. The Pilog query (the first argument to 95 <code>solve</code>) passes these values to the Pilog variables <code>@Nr</code>, 96 <code>@Nm</code> and <code>@Pr</code>. Ranges of values are always specified by 97 cons pairs, so <code>(1 . 4)</code> includes the numbers 1 through 4, while 98 <code>(NIL . 100.00)</code> includes prices from minus infinite up to one 99 hundred. 100 101 <p>The list of unification variables is 102 103 <pre><code> 104 <code>(@Item)</code> 105 </code></pre> 106 107 <p>The list of generator clauses is 108 109 <pre><code> 110 ((nr +Item @Nr) (nm +Item @Nm) (pr +Item @Pr)) 111 </code></pre> 112 113 <p>The filter clauses are 114 115 <pre><code> 116 (range @Nr @Item nr) 117 (part @Nm @Item nm) 118 (range @Pr @Item pr) 119 </code></pre> 120 121 122 <p><hr> 123 <h2><a name="univar">Unification Variables</a></h2> 124 125 <p>As stated above, the first argument to <code>select</code> should be a list 126 of variables. These variables communicate values (via <code><a 127 href="refU.html#unify">unify</a></code>) from the <code>select</code> 128 environment to the enclosing Pilog environment. 129 130 <p>The first variable in this list (<code>@Item</code> in the above example) is 131 mandatory, it takes the direct return value of <code>select</code>. Additional 132 optional variables may be unified by clauses in the body of <code>select</code>, 133 and return further values. 134 135 136 <p><hr> 137 <h2><a name="gencl">Generator Clauses</a></h2> 138 139 <p>The second argument to <code>select</code> is a list of "generator clauses". 140 Each of these clauses specifies some kind of database B-Tree <code><a 141 href="refI.html#+index">+index</a></code>, to be traversed by 142 <code>select</code>, step by step, where each step returns a suitable single 143 database object. In the simplest case, they consist like here just of a relation 144 name (e.g. <code>nr</code>), a class (e.g. <code>+Item</code>), an optional hook 145 specifier (not in this example), and a pattern (values or ranges, e.g. (1 . 4) 146 or "Part"). 147 148 <p>The generator clauses are the core of 'select'. In some way, they behave 149 analog to <code><a href="refO.html#or/2">or/2</a></code>, as each of them 150 generates a sequence of values. However, the generator clauses behave different, 151 as they will not generate an exhaustive set of values upon backtracking, one 152 after the other, where the next gets its turn when the previous one is 153 exhausted. Instead, all clauses will generate their values quasi-parallel, with 154 a built-in optimization so that successful clauses will be called with a higher 155 probability. "Successful" means that the returned values successfully pass 156 <code>select</code>'s filter clauses. 157 158 159 <p><hr> 160 <h3><a name="db">B-Tree Stepping</a></h3> 161 162 <p>In its basic form, a generator clause is equivalent to the <code><a 163 href="refD.html#db/3">db/3</a></code> predicate, stepping through a single 164 B-Tree. The clause 165 166 <pre><code> 167 (nr +Item @Nr) 168 </code></pre> 169 170 <p>generates the same values as would be produced by a stand-alone Pilog clause 171 172 <pre><code> 173 (db nr +Item @Nr @Item) 174 </code></pre> 175 176 <p>as can be seen in the following two calls: 177 178 <pre><code> 179 : (? (db nr +Item (1 . 4) @Item)) 180 @Item={3-1} 181 @Item={3-2} 182 @Item={3-3} 183 @Item={3-4} 184 -> NIL 185 : (? (select (@Item) ((nr +Item (1 . 4))))) 186 @Item={3-1} 187 @Item={3-2} 188 @Item={3-3} 189 @Item={3-4} 190 -> NIL 191 </code></pre> 192 193 194 <p><hr> 195 <h3><a name="interaction">Interaction of Generator Clauses</a></h3> 196 197 <p><code>select</code> is mostly useful if more than one generator clause is 198 involved. The tree search parameters of all clauses are meant to form a logical 199 <code>AND</code>. Only those objects should be returned, for which all search 200 parameters (and the associated filter clauses) are valid. As soon as one of the 201 clauses finishes stepping through its database (sub)tree, the whole call to 202 <code>select</code> will terminate, because further values returned from other 203 generator clauses cannot be part of the result set. 204 205 <p>Therefore, <code>select</code> would find all results most quickly if it 206 could simply call only the generator clause with the smallest (sub)tree. 207 Unfortunately, this is usually not known in advance. It depends on the 208 distribution of the data in the database, and on the search parameters to each 209 generator clause. 210 211 <p>Instead, <code>select</code> single-steps each generator clause in turn, in a 212 round-robin scheme, applies the filter clauses to each generated object, and 213 re-arranges the order of generator clauses so that the more successful clauses 214 will be preferred. This process usually converges quickly and efficiently. 215 216 217 <p><hr> 218 <h3><a name="combined">Combined Indexes</a></h3> 219 220 <p>A generator clause can also combine several (similar) indexes into a single 221 one. Then the clause is written actually as a list of clauses. 222 223 <p>For example, a generator clause to search for a customer by phone number is 224 225 <pre><code> 226 (tel +CuSu @Tel) 227 </code></pre> 228 229 If we want to search for a customer without knowing whether a given number is a 230 normal or a mobile phone number, then a combined generator clause searching both 231 index trees could look like 232 233 <pre><code> 234 ((tel +CuSu @Tel mob +CuSu @Tel)) 235 </code></pre> 236 237 <p>The generator will first traverse all matching entries in the <code><a 238 href="refR.html#+Ref">+Ref</a></code> tree of the <code>tel</code> relation, and 239 then, when these are exhausted, all matching entries in the <code>mob</code> 240 index tree. 241 242 243 <p><hr> 244 <h3><a name="associations">Indirect Object Associations</a></h3> 245 246 <p>But generator clauses are not limited to the direct B-Tree interaction of 247 <code><a href="refD.html#db/3">db/3</a></code>. They can also traverse trees of 248 associated objects, and then follow <code><a 249 href="refL.html#+Link">+Link</a></code> / <code><a 250 href="refJ.html#+Joint">+Joint</a></code> relations, or tree relations like 251 <code><a href="refR.html#+Ref">+Ref</a></code> to arrive at database objects 252 with a type suitable for return values from <code>select</code>. 253 254 <p>To locate appropriate objects from associated objects, the generator clause 255 can contain - in addition to the standard relation/class/pattern specification 256 (see <a href="#gencl">Generator Clauses</a> above) - an arbitrary number of 257 association specifiers. Each association specifier can be 258 259 <ol> 260 <li>A symbol. Then a <code><a href="refL.html#+Link">+Link</a></code> or 261 <code><a href="refJ.html#+Joint">+Joint</a></code> will be followed, or a 262 <code><a href="refL.html#+List">+List</a></code> of those will be traversed to 263 locate appropriate objects. 264 265 <li>A list. Then this list should hold a relation and a class (and an optional 266 hook) which specify some B-Tree <code><a 267 href="refI.html#+index">+index</a></code> to be traversed to locate appropriate 268 objects. 269 270 </ol> 271 272 In this way, a single generator clause can cause the traversal of a tree of 273 object relations to generate the desired sequence of objects. 274 275 An example can be found in "app/gui.l", in the 'choOrd' function which 276 implements the search dialog for <code>+Ord</code> (order) objects. Orders can 277 be searched for order number and date, customer name and city, item description 278 and supplier name: 279 280 <pre><code> 281 (select (@@) 282 ((nr +Ord @Nr) (dat +Ord @Dat) 283 (nm +CuSu @Cus (cus +Ord)) 284 (ort +CuSu @Ort (cus +Ord)) 285 (nm +Item @Item (itm +Pos) ord) 286 (nm +CuSu @Sup (sup +Item) (itm +Pos) ord) ) 287 </code></pre> 288 289 <p>While <code>(nr +Ord @Nr)</code> and <code>(dat +Ord @Dat)</code> are direct 290 index traversals, <code>(nm +CuSu @Cus (cus +Ord))</code> iterates the 291 <code>nm</code> (name) index of customers/suppliers <code>+CuSu</code>, and then 292 follows the <code><a href="refR.html#+Ref">+Ref</a></code> <code><a 293 href="refL.html#+Link">+Link</a></code> of the <code>cus</code> relation to the 294 orders. The same applies to the search for city names via <code>ort</code>. 295 296 <p>The most complex example is <code>(nm +CuSu @Sup (sup +Item) (itm +Pos) 297 ord)</code>, where the supplier name is searched in the <code>nm</code> tree of 298 <code>+CuSu</code>, then the <code><a href="refR.html#+Ref">+Ref</a></code> tree 299 <code>(sup +Item)</code> tree is followed to locate items of that supplier, then 300 all positions for those items are found using <code>(itm +Pos)</code>, and 301 finally the <code>ord</code> <code><a href="refJ.html#+Joint">+Joint</a></code> 302 is followed to arrive at the order object(s). 303 304 305 <p><hr> 306 <h3><a name="nested">Nested Pilog Queries</a></h3> 307 308 <p>In the most general case, a generator clause can be an arbitrary Pilog query. 309 Often this is a query to a database on a remote machine, using the <code><a 310 href="refR.html#remote/2">remote/2</a></code> predicate, or some other resource 311 not accessible via database indexes, like iterating a <code><a 312 href="refL.html#+List">+List</a></code> of <code><a 313 href="refL.html#+Link">+Link</a></code>s or <code><a 314 href="refJ.html#+Joint">+Joint</a></code>s. 315 316 <p>Syntactically, such a generator clause is recognized by the fact that its CAR 317 is a Pilog variable to denote the return value. 318 319 <p>The second argument is a list of Pilog variables to communicate values (via 320 <code><a href="refU.html#unify">unify</a></code>) from the surrounding 321 <code>select</code> environment. 322 323 <p>The third argument is the actual list of clauses for the nested query. 324 325 <p>Finally, an arbitrary number of association specifiers may follow, as 326 described in the <a href="#associations">Indirect Object Associations</a> 327 section. 328 329 <p>We can illustrate this with a somewhat useless (but simple) example, which 330 replaces the standard generators for item number and supplier name 331 332 <pre><code> 333 (select (@Item) 334 ( 335 (nr +Item @Nr) 336 (nm +CuSu @Sup (sup +Item)) 337 ) 338 ... 339 </code></pre> 340 341 <p>with the equivalent form 342 343 <pre><code> 344 (select (@Item) 345 ( 346 (@A (@Nr) ((db nr +Item @Nr @A))) 347 (@B (@Sup) ((db nm +CuSu @Sup @B)) (sup +Item)) 348 ) 349 </code></pre> 350 351 <p>That is, a query with the <code><a href="refD.html#db/3">db/3</a></code> tree 352 iteration predicate is used to generate appropriate values. 353 354 355 <p><hr> 356 <h2><a name="filcl">Filter Clauses</a></h2> 357 358 <p>The generator clauses produce - independent from each other - lots of 359 objects, which match the patterns of individual generator clauses, but not 360 necessarily the desired result set of the total <code>select</code> call. 361 Therefore, the filter clauses are needed to retain the good, and throw away the 362 bad objects. In addition, they give feedback to the generator for optimizing its 363 traversal priorities (as described in <a href="#gencl">Generator Clauses</a>). 364 365 <p><code>select</code> then collects all objects which passed through the 366 filters into a unique list, to avoid duplicates which would otherwise appear, 367 because most objects can be found by more than one generator clause. 368 369 <p>Technically, the filters are normal Pilog clauses, which just happen to be 370 evaluated in the context of <code>select</code>. Arbitrary Pilog predicates can 371 be used, though there exist some predicates (e.g. <code><a 372 href="refI.html#isa/2">isa/2</a></code>, <code><a 373 href="refS.html#same/3">same/3</a></code>, <code><a 374 href="refB.html#bool/3">bool/3</a></code>, <code><a 375 href="refR.html#range/3">range/3</a></code>, <code><a 376 href="refH.html#head/3">head/3</a></code>, <code><a 377 href="refF.html#fold/3">fold/3</a></code>, <code><a 378 href="refP.html#part/3">part/3</a></code> or <code><a 379 href="refT.html#tolr/3">tolr/3</a></code>) especially suited for that task. 380 381 382 <p><hr> 383 <h3><a name="little">A Little Report</a></h3> 384 385 <p>Assume we want to know how many pieces of item #2 were sold in the year 2007. 386 Then we must find all <code>+Pos</code> (position) objects referring to that 387 item and at the same time belonging to orders of the year 2007 (see the class 388 definition for <code>+Pos</code> in "app/er.l"). The number of sold pieces is 389 then in the <code>cnt</code> property of the <code>+Pos</code> objects. 390 391 <p>As shown in the complete <code>select</code> below, we will hold the item 392 number in the variable <code>@Nr</code> and the date range for the year in 393 <code>@Year</code>. 394 395 <p>Now, all positions referred by item #2 can be found by the generator clause 396 397 <pre><code> 398 (nr +Item @Nr (itm +Pos)) 399 </code></pre> 400 401 <p>and all positions sold in 2007 can be found by 402 403 <pre><code> 404 (dat +Ord @Year pos) 405 </code></pre> 406 407 <p>However, the combination of both generator clauses 408 409 <pre><code> 410 (select (@Pos) 411 ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos)) ) 412 </code></pre> 413 414 <p>will probably generate too many results, namely all positions with item #3 415 <u>OR</u> from the year 2007. Thus, we need two filter clauses. With them, the 416 full search expression will be: 417 418 <pre><code> 419 (? 420 @Nr 2 # Item number 421 @Year (cons (date 2007 1 1) (date 2007 12 31)) # Date range 2007 422 (select (@Pos) 423 ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos)) # Generator clauses 424 (same @Nr @Pos itm nr) # Filter item number 425 (range @Year @Pos ord dat) ) ) # Filter order date 426 </code></pre> 427 428 <p>For completeness, let's calculate the total count of sold items: 429 430 <pre><code> 431 (let Cnt 0 # Counter variable 432 (pilog 433 (quote 434 @Nr 2 435 @Year (cons (date 2007 1 1) (date 2007 12 31)) 436 (select (@Pos) 437 ((nr +Item @Nr (itm +Pos)) (dat +Ord @Year pos)) 438 (same @Nr @Pos itm nr) 439 (range @Year @Pos ord dat) ) ) 440 (inc 'Cnt (get @Pos 'cnt)) ) # Increment total count 441 Cnt ) # Return count 442 </code></pre> 443 444 445 <p><hr> 446 <h3><a name="filpr">Filter Predicates</a></h3> 447 448 <p>As mentioned under <a href="#filcl">Filter Clauses</a>, some predicates 449 exists mainly for <code>select</code> filtering. 450 451 <p>Some of these predicates are of general use: <code><a 452 href="refI.html#isa/2">isa/2</a></code> can be used to check for a type, 453 <code><a href="refS.html#same/3">same/3</a></code> checks for a definite vaue, 454 <code><a href="refB.html#bool/3">bool/3</a></code> looks if the value is 455 non-<code>NIL</code>. These predicates are rather independent of the <code><a 456 href="refR.html#+relation">+relation</a></code> type. 457 458 <p><code><a href="refR.html#range/3">range/3</a></code> checks whether a value 459 is within a given range. This could be used with any <code><a 460 href="refR.html#+relation">+relation</a></code> type, but typically it will be 461 used for numeric (<code><a href="refN.html#+Number">+Number</a></code>) or time 462 ( <code><a href="refD.html#+Date">+Date</a></code> and <code><a 463 href="refT.html#+Time">+Time</a></code>) relations. 464 465 <p>Other predicates make only sense in the context of a certain <code><a 466 href="refR.html#+relation">+relation</a></code> type: 467 468 <ul> 469 <li><code><a href="refH.html#head/3">head/3</a></code> is mainly intended for 470 <code>(<a href="refK.html#+Key">+Key</a> <a 471 href="refS.html#+String">+String</a>)</code> or <code>(<a 472 href="refR.html#+Ref">+Ref</a> <a href="refS.html#+String">+String</a>)</code> 473 relations, 474 475 <li><code><a href="refF.html#fold/3">fold/3</a></code> is useful for <code>(<a 476 href="refF.html#+Fold">+Fold</a> <a href="refR.html#+Ref">+Ref</a> <a 477 href="refS.html#+String">+String</a>)</code> relations, 478 479 <li><code><a href="refP.html#part/3">part/3</a></code> for <code>(<a 480 href="refF.html#+Fold">+Fold</a> <a href="refI.html#+Idx">+Idx</a> <a 481 href="refS.html#+String">+String</a>)</code> relations, and 482 483 <li><code><a href="refT.html#tolr/3">tolr/3</a></code> for <code>(<a 484 href="refS.html#+Sn">+Sn</a> <a href="refI.html#+Idx">+Idx</a> <a 485 href="refS.html#+String">+String</a>)</code> relations. 486 487 </ul> 488 489 </body> 490 </html>