Helix SwarmHelix Swarm
Loading...

overview.html

  • //
  • guest/
  • julian_hyde/
  • saffron/
  • doc/
  • overview.html #5
  • View
  • Commits
  • Open Download .zip Download (50 KB) 
  1. <body>
  2. <html>
  3.  
  4. <head>
  5. <meta http-equiv="Content-Language" content="en-us">
  6. <meta name="GENERATOR" content="Microsoft FrontPage 5.0">
  7. <meta name="ProgId" content="FrontPage.Editor.Document">
  8. <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
  9. <title>Saffron overview</title>
  10.  
  11. <style>
  12.  
  13. A:link { color:#000066; }
  14. A:visited { color:#666666; }
  15.  
  16. A.clsIncCpyRt,
  17. A.clsIncCpyRt:visited,
  18. P.clsIncCpyRt {
  19.   font-weight:normal; font-size:75%; font-family:verdana,arial,helvetica,sans-serif;
  20.   color:black;
  21.   text-decoration:none;
  22. }
  23.  
  24. A.clsLeftMenu,
  25. A.clsLeftMenu:visited {
  26.   color:#000000;
  27.   text-decoration:none;
  28.   font-weight:bold; font-size:8pt;
  29. }
  30.  
  31. A.clsBackTop,
  32. A.clsBackTop:visited {
  33.   margin-top:10; margin-bottom:0;
  34.   padding-bottom:0;
  35.   font-size:75%;
  36.   color:black;
  37. }
  38.  
  39. A:hover,
  40. A.clsBackTop:hover,
  41. A.clsIncCpyRt:hover,
  42. A:active { color:blue; }
  43.  
  44. A.clsGlossary {
  45.   font-size:10pt;
  46.   color:green;
  47. }
  48.  
  49. BODY { font-size:80%; font-family:verdana,arial,helvetica,sans-serif; }
  50.  
  51. BUTTON.clsShowme,
  52. BUTTON.clsShowme5 {
  53.   font-weight:bold; font-size:11; font-family:arial;
  54.   width:68; height:23;
  55.   position:relative; top:2;
  56.   background-color:#002F90;
  57.   color:#FFFFFF;
  58. }
  59.  
  60. DIV.clsBeta {
  61.   font-weight:bold;
  62.   color:red;
  63. }
  64.  
  65. DIV.clsDocBody { margin-left:10px; margin-right:10px; }
  66.  
  67. DIV.clsDocBody HR { margin-top:0; }
  68.  
  69. DIV.clsDesFooter { margin:10px 10px 0px 223px; }
  70.  
  71. DIV.clsFPfig { font-size:80%; }
  72.  
  73. DIV.clsHi {
  74. 	padding-left:2em;
  75. 	text-indent:-2em
  76. }
  77.  
  78. DIV.clsShowme { margin-bottom:.5em; margin-top:.5em; }
  79.  
  80. H1{
  81.   font-size:145%;
  82.   margin-top:1.25em; margin-bottom:0em;
  83. }
  84.  
  85. H2 {
  86.   font-size:135%;
  87.   margin-top:1.25em; margin-bottom:.5em;
  88. }
  89.  
  90. H3 {
  91.   font-size:128%;
  92.   margin-top:1em; margin-bottom:0em;
  93. }
  94.  
  95. H4 {
  96.   font-size:120%;
  97.   margin-top:.8em; margin-bottom:0em;
  98. }
  99.  
  100. H5 {
  101.   font-size:110%;
  102.   margin-top:.8em; margin-bottom:0em;
  103. }
  104.  
  105. H6 {
  106.   font-size:70%;
  107.   margin-top:.6em; margin-bottom:0em;
  108. }
  109.  
  110. HR.clsTransHR {
  111. 	position:relative; top:20;
  112. 	margin-bottom:15;
  113. }
  114.  
  115. P.clsRef {
  116.   font-weight:bold;
  117.   margin-top:12pt; margin-bottom:0pt;
  118. }
  119.  
  120. PRE {
  121.   background:#EEEEEE;
  122.   margin-top:1em;	margin-bottom:1em; margin-left:0px;
  123.   padding:5pt;
  124. }
  125.  
  126. PRE.clsCode, CODE.clsText { font-family:'courier new',courier,serif; font-size:130%; }
  127.  
  128. PRE.clsSyntax { font-family:verdana,arial,helvetica,sans-serif; font-size:120%; }
  129.  
  130. SPAN.clsEntryText {
  131.   line-height:12pt;
  132.   font-size:8pt;
  133. }
  134.  
  135. SPAN.clsHeading {
  136.   color:#00319C;
  137.   font-size:11pt; font-weight:bold;
  138. }
  139.  
  140. SPAN.clsDefValue, TD.clsDefValue { font-weight:bold; font-family:'courier new' }
  141.  
  142. SPAN.clsLiteral, TD.clsLiteral { font-family:'courier new'; }
  143.  
  144. SPAN.clsRange, TD.clsRange { font-style:italic; }
  145.  
  146. SPAN.clsShowme {
  147.   width:100%;
  148.   filter:dropshadow(color=#000000,OffX=2.5,OffY=2.5,Positive=1);
  149.   position:relative;
  150.   top:-8;
  151. }
  152.  
  153. TABLE { font-size:100%; }
  154.  
  155. TABLE.clsStd {
  156. 	background-color:#444;
  157. 	border:1px none;
  158. 	cellspacing:0;
  159. 	cellpadding:0
  160. }
  161.  
  162. TABLE.clsStd TH,
  163. BLOCKQUOTE TH {
  164. 	font-size:100%;
  165. 	text-align:left; vertical-align:top;
  166. 	background-color:#DDD;
  167. 	padding:2px;
  168. }
  169.  
  170. TABLE.clsStd TD,
  171. BLOCKQUOTE TD {
  172. 	font-size:100%;
  173. 	vertical-align:top;
  174. 	background-color:#EEE;
  175. 	padding:2px;
  176. }
  177.  
  178. TABLE.clsParamVls,
  179. TABLE.clsParamVls TD { padding-left:2pt; padding-right:2pt; }
  180.  
  181. #TOC { visibility:hidden; }
  182.  
  183. UL UL, OL UL { list-style-type:square; }
  184.  
  185. .clsHide { display:none; }
  186.  
  187. .clsShow { }
  188.  
  189. .clsShowDiv {
  190.   visibility:hidden;
  191.   position:absolute;
  192.   left:230px; top:140px;
  193.   height:0px; width:170px;
  194.   z-index:-1;
  195. }
  196.  
  197. .#pBackTop { display:none; }
  198.  
  199. #idTransDiv {
  200. 	position:relative;
  201. 	width:90%; top:20;
  202.   filter:revealTrans(duration=1.0, transition=23);
  203. }
  204.  
  205.  
  206. /*** INDEX-SPECIFIC ***/
  207.  
  208. A.clsDisabled {
  209.   text-decoration:none;
  210.   color:black;
  211.   cursor:text;
  212. }
  213.  
  214. A.clsEnabled { cursor:auto; }
  215.  
  216. SPAN.clsAccess { text-decoration:underline; }
  217.  
  218. TABLE.clsIndex {
  219.   font-size:100%;
  220.   padding-left:2pt; padding-right:2pt;
  221. 	margin-top: 17pt;
  222. }
  223.  
  224. TABLE.clsIndex TD {
  225.   margin:3pt;
  226.   background-color:#EEEEEE;
  227. }
  228.  
  229. TR.clsEntry { vertical-align:top; }
  230.  
  231. TABLE.clsIndex TD.clsLetters {
  232.   background-color:#CCCCCC;
  233.   text-align:center;
  234. }
  235.  
  236. TD.clsMainHead {
  237.   background-color:#FFFFFF;
  238.   vertical-align:top;
  239.   font-size:145%; font-weight:bold;
  240.   margin-top:1.35em; margin-bottom:.5em;
  241. }
  242.  
  243. UL.clsIndex { margin-left:20pt; margin-top:0pt; margin-bottom:5pt; }
  244.  
  245. LI OL { padding-bottom: 1.5em }
  246.  
  247.  
  248. /*** GALLERY/TOOLS/SAMPLES ***/
  249.  
  250. FORM.clsSamples { margin-bottom:0; margin-top:0; }
  251.  
  252. H1.clsSampH1 {
  253. 	font-size:145%;
  254.   margin-top:.25em; margin-bottom:.25em;
  255. }
  256.  
  257. H1.clsSampHead {
  258.   margin-top:5px; margin-bottom:5px;
  259.   font-size:24px; font-weight:bold; font-family:verdana,arial,helvetica,sans-serif;
  260. }
  261.  
  262. H2.clsSampTitle {
  263.   font-size:128%;
  264.   margin-top:.2em; margin-bottom:0em;
  265. }
  266.  
  267. TD.clsDemo {
  268.   font-size:8pt;
  269.   color:#00319C;
  270.   text-decoration:underline;
  271. }
  272.  
  273. .clsSampDnldMain { font-size:11px; font-family:verdana,arial,helvetica,sans-serif; }
  274.  
  275. .clsShowDesc { cursor:hand; }
  276.  
  277. A.clsTools {
  278.   color:#0B3586;
  279.   font-weight:bold;
  280. }
  281.  
  282. H1.clsTools, H2.clsTools {
  283.   color:#0B3586;
  284.   margin-top:5px;
  285. }
  286.  
  287. TD.clsToolsHome {
  288.   font-size:9pt;
  289.   line-height:15pt;
  290. }
  291.  
  292. SPAN.clsToolsTitle {
  293.   color:#00319C;
  294.   font-size:11pt; font-weight:bold;
  295.   text-decoration:none;
  296. }
  297.  
  298.  
  299. /*** DESIGN ***/
  300. P.cat {
  301. 	font-size:13pt;
  302. 	color:#787800;
  303. 	text-decoration:none;
  304. 	margin-top:18px;
  305. }
  306.  
  307. P.author {
  308. 	font-size:9pt; font-style:italic;
  309. 	line-height:13pt;
  310. 	margin-top:10px;
  311. }
  312.  
  313. P.date {
  314. 	font-size:8pt;
  315. 	line-height:12px;
  316. 	margin-top:0px;
  317. 	color:#3366FF;
  318. }
  319.  
  320. P.graph1 {
  321. 	line-height:13pt;
  322. 	margin-top:-10px;
  323. }
  324.  
  325. P.col {
  326. 	line-height:13pt;
  327. 	margin-top:10px; margin-left:5px;
  328. }
  329.  
  330. P.cal1 {
  331. 	text-decoration:none;
  332. 	margin-top:-10px;
  333. }
  334.  
  335. P.cal2 {margin-top:-10px; }
  336. P.photo { font-size:8pt; }
  337.  
  338.  
  339. /*** DOCTOP ***/
  340.  
  341. #tblNavLinks A {
  342. 	color:black;
  343. 	text-decoration:none;
  344. 	font-family:verdana,arial,helvetica,sans-serif;
  345. }
  346. #lnkShowText, #lnkSyncText, #lnkSearchText, #lnkIndexText { font-size:8pt; font-weight:bold; }
  347. #lnkPrevText, #lnkNextText, #lnkUpText { font-size:7.5pt; font-weight:normal; }
  348.  
  349.  
  350. DIV.clsBucketBranch {
  351. 	margin-left:10px; margin-top:15px; margin-bottom:-10pt;
  352. 	font-style:italic; font-size:85%;
  353. }
  354.  
  355. DIV.clsBucketBranch A,
  356. DIV.clsBucketBranch A:link,
  357. DIV.clsBucketBranch A:active,
  358. DIV.clsBucketBranch A:visited { text-decoration:none; color:black; }
  359. DIV.clsBucketBranch A:hover { color:blue; }
  360.  
  361.  
  362. /*** SDK, IE4 ONLY ***/
  363.  
  364. DIV.clsExpanded, A.clsExpanded { display:inline; color:black; }
  365. DIV.clsCollapsed, A.clsCollapsed { display:none; }
  366. SPAN.clsPropattr { font-weight:bold; }
  367.  
  368. #pStyles,	#pCode, #pSyntax, #pEvents, #pStyles {display:none; text-decoration:underline; cursor:hand; }
  369.  
  370. /*** jhyde added ***/
  371. CODE { color:maroon; font-family:'courier new' }
  372.  
  373. DFN { font-weight:bold; font-style:italic; }
  374.  
  375.  
  376. </style>
  377.  
  378. </head>
  379.  
  380. <!-- 
  381.  
  382. This sentence is here to fool javadoc (which is looking for a period, and otherwise finds one
  383. inside one of our header tables).
  384.  
  385.  -->
  386.  
  387. <table border="1" class="clsStd" width="100%">
  388.   <tr>
  389.     <td colspan="2"><a href="index.html">Top</a> |
  390.       <a href="http://public.perforce.com/guest/julian_hyde/saffron/doc/index.html">Web home</a> |
  391.       <a href="http://sourceforge.net/projects/saffron/">SourceForge home</a>
  392.     <div align="right">
  393.        <a href="http://sourceforge.net">
  394. 	       <img src="http://sourceforge.net/sflogo.php?group_id=46646&type=1" border="0" alt="SourceForge.net Logo">
  395. 	    </a>
  396.     </div>
  397. 	 </td>
  398.   </tr>
  399.   <tr>
  400.     <td colspan="2"><em>$Id: //guest/julian_hyde/saffron/doc/overview.html#5 $</em></td>
  401.   </tr>
  402.   <tr>
  403.     <td colspan="2"><em>(C) Copyright 2002, Julian Hyde</em></td>
  404.   </tr>
  405.   <tr>
  406.     <th align="right">Author</th>
  407.     <td>Julian Hyde (<a href="mailto:julian.hyde@mail.com">julian.hyde@mail.com</a>)</td>
  408.   </tr>
  409.   <tr>
  410.     <th align="right">Created</th>
  411.     <td>November 5<sup>th</sup>, 2002</td>
  412.   </tr>
  413. </table>
  414.  
  415. <h1>Saffron overview</h1>
  416.  
  417. <p>Julian Hyde, November 5th, 2001.</p>
  418. <h2>Overview</h2>
  419. <p>Saffron is a seamless integration of SQL-like relational expressions into Java. 
  420. As we shall see, the tight integration means that relational expressions are 
  421. much more powerful than those offered by SQL.</p>
  422. <h2>How is Saffron different from SQL?</h2>
  423. <ol>
  424.   <li><b>You can use Saffron expressions directly from Java code</b>. For example, 
  425.   an <code>exists </code>condition:<blockquote>
  426.   <pre>if (exists (select from emp where emp.salary &gt; 50000)) {
  427.   ...
  428. }</pre>
  429.   </blockquote>
  430.   <p>An <code>in </code>condition:</p>
  431.   <blockquote>
  432.   <pre>if (&quot;Fred&quot; in (select emp.ename from emp where emp.salary &gt; 50000)) {
  433.    ...
  434. }</pre>
  435.   </blockquote>
  436.   <p>A <code>for </code>loop:</p>
  437.   <blockquote>
  438.   <pre>for (emp in (select from emp order by emp.salary)) {
  439.    System.out.println(emp.ename + &quot; earns &quot; + emp.salary);
  440. }</pre>
  441.   </blockquote>
  442.   <p>And an array initialized using a relational expression:</p>
  443.   <blockquote>
  444.   <pre>Emp[] programmers = (select from emp
  445.         where emp.title.equals(&quot;Programmer&quot;));</pre>
  446.   </blockquote>
  447.   </li>
  448.   <li><b>Saffron</b><b> uses Java expression syntax</b>. You can call java methods, 
  449.   construct objects and arrays, and access java objects just as you would in 
  450.   regular java code. For example,<blockquote>
  451.     <pre>select emp.ename.substring(ename.indexOf(&quot;.&quot;)) from emp</pre>
  452.   </blockquote>
  453.   </li>
  454.   <li><b>Saffron</b><b> relational expressions use Java's type system</b>. Runtime type 
  455.   conversions (of, say, a <code>DECIMAL(8,2)</code> column to a java <code>float
  456.   </code>variable) are inefficient, error-prone, and can lose information.
  457.   The names of tables and columns are checked at compile time, so your programs 
  458.   are more maintainable.</li>
  459.   <li><b>Saffron</b><b> doesn't use 3-valued logic</b>. A condition in Saffron
  460.     always 
  461.   evaluates to <code>true</code> or <code>false</code>, whereas in SQL a 
  462.   condition can sometimes evaluates to NULL.</li>
  463.   <li><b>Saffron</b><b> expressions are evaluated efficiently</b>. If an expression 
  464.   involves only Java objects (no tables), the Saffron compiler will generate Java 
  465.   code which is almost as efficient as hand-written code.</li>
  466.   <li><b>Saffron</b><b> accesses heterogeneous data better</b>. Consider the following 
  467.   query, which accesses data from an in-memory array (<code>manufacturers</code>), and tables from two 
  468.   different relational databases (<code>orderDb </code>and <code>productDb</code>).<blockquote>
  469.   <pre>String[] manufacturers = new String[] {&quot;Heinz&quot;, &quot;Guinness&quot;};
  470. int[] customers = (
  471.   select order.customerId
  472.   from productDb.products as product
  473.   join orderDb.orders as order on order.productId == productId
  474.   where product.manufacturer in manufacturers);</pre>
  475.   </blockquote>
  476.   Should the query be executed on the orders database or the products database? 
  477.   And how should the manufacturer list be sent over: as a hard-coded in-list, or 
  478.   by restarting the query for each manufacturer in the list?&nbsp; It really 
  479.   doesn't matter: the Saffron optimizer will decide for you. 
  480.   </li>
  481. </ol>
  482. <h2>How does Saffron improve Java?</h2>
  483. <p>We have already discussed how Saffron makes your life easier if you are 
  484. embedding SQL statements in Java using JDBC. But Saffron can help even if 
  485. you are not accessing data stored in a relational database. This is 
  486. because in-memory data is often relational, and the algorithms to deal with it 
  487. are often the familiar relational operations: sort, join, filter, union, 
  488. intersect, minus.</p>
  489. <p>Suppose I have two lists of customers, and I want to create a list of both, 
  490. with duplicates eliminated. An experienced Java programmer would probably 
  491. write something like this:</p>
  492. <blockquote>
  493.   <pre>Customer[] addCustomerLists(Customer[] list1, Customer[] list2) {
  494.   Hashtable hashtable = new Hashtable();
  495.   for (int i = 0; i &lt; list1.length; i++) {
  496.     Customer c = list1[i];
  497.     hashtable.put(c, c);
  498.   }
  499.   for (int i = 0; i &lt; list2.length; i++) {
  500.     Customer c = list2[i];
  501.     hashtable.put(c, c);
  502.   }
  503.   Customer[] list3 = new Customer[hashtable.size()];
  504.   hashtable.asList().copyInto(list3);
  505.   return list3;
  506. }</pre>
  507. </blockquote>
  508. <p>They would test it, notice that the customers are now in arbitrary order, and 
  509. add</p>
  510. <blockquote>
  511.   <pre>  java.util.Arrays.sort(list3);</pre>
  512. </blockquote>
  513. <p>just before returning the result. In Saffron, a programmer would write</p>
  514. <blockquote>
  515.   <pre>Customer[] list3 = select from (list1 union list2) c order by c;</pre>
  516. </blockquote>
  517. <p>They don't need to know Hashtable is the 'correct' data structure to use. 
  518. They tell the system <i>what </i>they want, and the system figures <i>how </i>to 
  519. compute it efficiently.</p>
  520. <p>This is a rather simple example. It gets better, because Saffron is a <i>
  521. closed </i>language. This means that you can use a Saffron expression anywhere </p>
  522. <h2>Grammar</h2>
  523. <p><i>Definition</i>. A <dfn>set expression</dfn> is 
  524. an expression which returns more than one item; namely, a query, an array, an 
  525. iterator or collection, or a <code>Table</code>.</p>
  526. <h3>Relational expressions</h3>
  527. <blockquote>
  528.   <pre><code>select</code> [<code>{</code>[<i>expression</i> [<code>as </code><i>alias</i>]], ...<code>}</code> | <i>expression</i>]
  529.   [<code>from </code><i>from-expression</i>]
  530.   [<code>where </code><i>expression</i>]
  531.   [<code>order by </code>[<i>expression </i>[<code>asc </code>| <code>desc</code>]], ...]</pre>
  532.   <pre><i>expression </i><code>union </code><i>expression</i></pre>
  533.   <pre><i>expression </i><code>intersect </code><i>expression</i></pre>
  534.   <pre><i>expression </i><code>minus </code><i>expression</i></pre>
  535. </blockquote>
  536. <p>The syntax for the from list <i>from-expression</i> is as follows:</p>
  537. <blockquote>
  538.   <pre><i>expression </i>[as alias]</pre>
  539.   <pre><i>from-expression </i>[<code>left</code> | <code>right</code> | <code>full</code> | ] <code>join</code><i>
  540. </i>   <i>from-expression </i>[<code>on</code> <i>condition</i>]</pre>
  541. </blockquote>
  542. <p>Notes:</p>
  543. <ol>
  544.   <li>The select list can have 3 forms.<ol>
  545.   <li>An <i><dfn>empty select list</dfn> </i>means return everything from the from clause. 
  546.   If the from clause has precisely one item, the result is the same type as that 
  547.   item (for example, each row from <code>select from emp</code> has type <code>
  548.   Emp</code>); otherwise, the result is a record, with one field per from item 
  549.   (for example, each row from <code>select from emp join dept</code> has type
  550.   <code>{Emp emp; Dept dept}</code>; each row 
  551.   from <code>select</code> has type <code>{}</code>).</li>
  552.   <li>A <dfn>single-item select list</dfn> means 
  553.   return rows without boxing them into records. So, for example, each row from
  554.   <code>select three from new int[] {1, 2, 3} as three</code> is an <code>int</code>. </li>
  555.   <li>A <dfn>boxed select list</dfn> (enclosed in
  556.   <code>{</code> ... <code>}</code>) means create a record for each row. The 
  557.   optimizer will create a synthetic class to describe the type of the row. Two 
  558.   rows with the same types and aliases, in the same order, will have the same 
  559.   synthetic class (and are therefore union-compatible). For example, each 
  560.   row from <code>select {three} from new int[] {1, 2, 3} as three</code> is
  561.   <code>class Synthetic$124 { int three; }</code>; the type of <code>select {emp.empno, 
  562.   emp.ename as name} from emp</code> is <code>class Synthetic$527 { int empno; 
  563.   String name; }</code>.</li>
  564. </ol>
  565.   </li>
  566.   <li>Aliases of items in from and select lists default to variable, field, and 
  567.   method names. The aliases of the fields in <code>Emp emp; select emp, 
  568.   dept.deptno, dept.dname.substring(3) from dept</code> are <code>emp</code>,
  569.   <code>deptno</code>, and <code>substring</code>, respectively. Other 
  570.   kinds of expression have no default alias, and therefore an alias must be 
  571.   specified. Whether implied or explicit, the aliases in a select or from 
  572.   list must be distinct.</li>
  573.   <li>If the from clause is missing, the input to the select statement is a 
  574.   table with one row and no columns.</li>
  575.   <li>Expressions in the from list must be set expressions. 
  576.   Any kind of expression is allowed in the select list; queries are returned as 
  577.   arrays.</li>
  578.   <li>If <code>on</code><i> condition </i>is omitted from a <i>from-expression</i> 
  579.   it defaults to <code>true</code> (hence, a cartesian product). The keywords
  580.   <code>left</code>, <code>right</code> and <code>full</code> indicate that an 
  581.   outer join is to be performed.</li>
  582.   <li>No plans to do <i>aggregation</i>.</li>
  583. </ol>
  584. <h3>Boolean expressions</h3>
  585. <p>We add the following boolean expressions to Java:</p>
  586. <blockquote>
  587.   <pre><i>expression</i> <code>in </code><i>expression</i></pre>
  588.   <pre><code>exists </code>(<i>expression</i>)</pre>
  589. </blockquote>
  590. <p>The right-hand expressions must be set expressions.</p>
  591. <p>These expressions can, of course, occur inside relational expressions. The 
  592. sub-query so created is said to be <dfn>correlated</dfn> if it refers to rows
  593. from the outer query. For example, the following query 
  594. is correlated on <code>dept.deptno</code>:</p>
  595. <blockquote>
  596.   <pre><code>select
  597. from </code>depts <code>as </code>dept
  598. <code>where exists </code>(
  599.    <code>select from </code>emps <code>as </code>emp
  600. <code>   where </code>emp.deptno == dept.deptno &amp;&amp;
  601.       emp.gender.equals(&quot;F&quot;))</pre>
  602. </blockquote>
  603. <p>We do not provide a <code>not</code> operator to negate these. Use the 
  604. regular Java <code>!</code> operator, for example, <code>!(&quot;apple&quot; in fruit)</code> 
  605. or <code>!exists (select from fruit where fruit.equals(&quot;apple&quot;)</code>.</p>
  606. <h3>Statements</h3>
  607. <blockquote>
  608.   <pre><code>for </code>([<i>type</i>]<i> variable</i> <code>in </code><i>expression</i>) {
  609.    <i>statement list
  610. </i>}</pre>
  611. </blockquote>
  612. <h3>Aggregation</h3>
  613. <p>Simple example:</p>
  614. <blockquote>
  615.   <pre><code>select</code> emp.deptno, sum(emp.sal)<code> as</code> sumSal<code>
  616. group by</code> emp.deptno<code>
  617. from </code>emps <code>as </code>emp</pre>
  618. </blockquote>
  619. <p>Unlike SQL, the <code>group by</code> clause comes before the <code>from</code> 
  620. clause, and is mandatory if you want to aggregate. The equivalent of the SQL <code>select 
  621. sum(emp.sal) from emp</code> has an empty <code>group by</code> clause in Saffron: <code>select sum(emp.sal) 
  622. group by from emp</code>.</p>
  623. <p>In Saffron, the <code>where</code> clause is applied <i>after</i> aggregation 
  624. has been performed, more like a SQL <code>having</code> clause than a <code>
  625. where</code> clause. Expressions in the <code>where</code> clause can only 
  626. reference aggregations and grouping expressions, not ungrouped expressions. If 
  627. you want to filter the rows going into the aggregation, use a subquery in the 
  628. from list:</p>
  629. <blockquote>
  630.   <pre><code>select</code> femp.deptno, sum(femp.sal)<code> as</code> sumSal<code>
  631. group by</code> femp.deptno<code>
  632. from </code>(
  633.     <code>select</code>
  634.     <code>from</code> emps <code>as</code> emp
  635.     <code>where</code> emp.gender.equals(&quot;F&quot;)) <code>as </code>femp
  636. <code>where </code>avg(femp.sal) &gt; 50000</pre>
  637. </blockquote>
  638. <p>There are 3 kinds of aggregation function:</p>
  639. <ol>
  640.   <li>Builtin aggregation functions (such as <code>count</code>) are treated 
  641.   specially by the system, and generate optimized code.</li>
  642.   <li>A regular java function which takes a set (array, collection, or iterator) 
  643.   will be called if its argument matches the element type in the actual usage. 
  644.   For example, if <code>emp.sal</code> is of type <code>double</code>, then
  645.   <code>double sum(double[] a)</code> would match. Likewise, <code>int 
  646.   count(Iterator iter)</code> would match <code>select count(emp) from emps as 
  647.   emp</code>, because Emp can be up-cast to Object, the element type of Iterator.</li>
  648.   <li>User-defined aggregations.</li>
  649. </ol>
  650.  
  651. <pA user-defined aggregation is a class which implements <code>interface {@link
  652. saffron.AggregationExtender}</code>. If you invoke the {@link
  653. saffron.AggregationExtender#aggregate} pseudo-method, the system generates the
  654. right code to calculate the aggregation.</p>
  655.  
  656. <p>Now let's see how the Saffron system invokes a user-defined aggregation
  657. while evaluating a query. Suppose we have written <code>class MySum</code>,
  658. which can total both <code> int</code> and <code>double</code> values, and
  659. evaluate the query</p>
  660.  
  661. <blockquote>
  662.   <pre><code>select</code> MySum(i)
  663. <code>from new int</code>[] {2, 3, 4} <code>as</code> i</pre>
  664. </blockquote>
  665. <p>The Saffron system makes following calls. Note how the <code>resolve</code> 
  666. method deals with operator overloading. Note how <code>int</code>s are wrapped 
  667. as <code>Integer</code>s then in arrays to be passed to <code>addOne</code>, and returned from
  668. <code>result</code>.</p>
  669. <blockquote>
  670.   <pre>AggregatorClass sum = new MySum();
  671. AggregationExtender intSum = sum.resolve(new Class[] {Integer.TYPE});
  672. Object total = intSum.start(null);
  673. intSum.addOne(total, new Object[] {new Integer(2)});
  674. intSum.addOne(total, new Object[] {new Integer(4)});
  675. Object total2 = intSum.start(null);
  676. intSum.addOne(total2, new Object[] {new Integer(3)});
  677. intSum.merge(total, total2);
  678. System.out.println(&quot;Result is &quot; +
  679.     ((Integer) intSum.result(total)).intValue());</pre>
  680. </blockquote>
  681. <p>Examples of more complex aggregations:</p>
  682. <ul>
  683.   <li>The <code>median</code> aggregation ({@link saffron.ext.Median}) requires a 
  684.   variable-size workspace. A typical implementation would use an {@link java.util.ArrayList} to collect the values, sort them, then return the middle one.</li>
  685.   <li>The <code>nth</code> aggregation {@link saffron.ext.Nth}) returns the <i>n</i>th item of a set. <i>n</i> 
  686.   is passed to the <code>start</code> method, so must be independent of any 
  687.   particular row. Example:<blockquote>
  688.     <pre><code>select</code> new Nth(3).aggregate(name) <code>from</code> (<code>select from</code> emps <code>order by</code> salary)</pre>
  689.   </blockquote>
  690.   </li>
  691.   <li>The <code>closest</code> aggregation computes the nearest of a set of 
  692.   points to a given point. Its <code>start</code> method receives the latitude 
  693.   and longitude of the initial point (as <code>new Object[] {new Double(42), new 
  694.   Double(129)}</code>), and the <code>addOne</code> method receives the latitude 
  695.   and longitude of each subsequent point.<blockquote>
  696.     <pre><code>select</code> closest(42, -129, office.latitude, office.longitude)
  697. <code>from</code> offices <code>as</code> office</pre>
  698.   </blockquote>
  699.   </li>
  700. </ul>
  701. <p>Notes &amp; issues:</p>
  702. <ol>
  703.   <li>Arguments are zero or more primitive types or objects. Primitives are 
  704.   passed wrapped as objects.</li>
  705.   <li>A robust aggregation of median (not possible without invoking custom 
  706.   code-generation) would internally expand it to<blockquote>
  707.     <pre><code>select </code>nth(count() / 2, sorted)
  708. <code>from</code> (<code>select from new int</code>[] {2, 3, 4} <code>as</code> i <code>order by</code> i) <code>as </code>sorted</pre>
  709.   </blockquote>
  710.   </li>
  711.   <li>Distinct aggregations. Syntax? Implementation?</li>
  712.   <li>Could we use aggregations as rolling averages? (I guess the <code>{@link saffron.AggregationExtender}.result()</code> method would have to be non-destructive.)</li>
  713. </ol>
  714. <h2>Type-checking</h2>
  715. <p>One of Java's most important features is its strong type system. To 
  716. take advantage of this, every relational expression is always has a result which 
  717. is an array type.</p>
  718. <p>This doesn't mean that the array is actually created. If you use the
  719. <code>for (... in ...)</code> construct, for example, the system will implement the loop 
  720. using an iterator, and is unlikely to construct the result as an array. 
  721. And the optimizer tries hard not to convert intermediate sets, such as that 
  722. created by an <code>in </code>operator, into arrays.</p>
  723. <p>Regular java expressions can also be used as relational expressions:</p>
  724. <ul>
  725.   <li>arrays</li>
  726.   <li>collections (<code>Collection</code>, including <code>Vector</code>)</li>
  727.   <li>iterators (<code>Enumeration</code>, <code>Iterator</code>)</li>
  728. </ul>
  729. <p>The problem with collections and iterators (until generics arrive in Java 
  730. 1.4) is that we don't know what type of objects they contain. We allow the 
  731. programmer to specify that type information using by a dummy cast to an array 
  732. type. For example:</p>
  733. <blockquote>
  734.   <pre>Vector fruit = new Vector();
  735. fruit.addElement(&quot;apple&quot;);
  736. fruit.addElement(&quot;banana&quot;);
  737. fruit.addElement(&quot;orange&quot;);
  738. fruit.addElement(&quot;mango&quot;);
  739. String[] tropicalFruit = (select fruit
  740.                           from (String[]) fruit
  741.                           where fruit.indexOf(&quot;n&quot;) &gt;= 0);</pre>
  742. </blockquote>
  743. <p>You can cast a collection or iterator to an array of primitive types, 
  744. provided that the collection does not contain null values.</p>
  745. <h3>Casting input datasets</h3>
  746. <p>Some data sources, such as vectors, iterators and external data sources such 
  747. as JDBC tables, contain very little type information, and this makes it 
  748. difficult to write concise queries. For example,</p>
  749. <blockquote>
  750.   <pre>Vector emps = new Vector();
  751. emps.addElement(fred);
  752. emps.addElement(barney);
  753. for (emp in select from emps as emp where ((Emp) emp).deptno == 20) {
  754.   print(((Emp) emp).name);
  755. }</pre>
  756. </blockquote>
  757. <p>Better to tell the system just once that <code>emps </code>is a collection of
  758. <code>Emp </code>objects:</p>
  759. <blockquote>
  760.   <pre>for (emp in select from (Emp[]) emps as emp where emp.deptno == 20) {
  761.   print(emp.name);
  762. }</pre>
  763. </blockquote>
  764. <p>The cast does not necessarily cause the vector to be converted to an array:
  765. we are simply providing the Saffron compiler with more type information, and
  766. allowing it to choose the most efficient plan.</p>
  767.  
  768. <h3>Determining the output type</h3>
  769.  
  770. <p>By default, a relational expression returns an array. You can produce results 
  771. in a different format by using a dummy cast, like this:</p>
  772.  
  773. <blockquote>
  774.   <pre>Iterator emps;
  775. Iterator femaleEmps = (Iterator)
  776.     (select from (Emp[]) emps as emp
  777.      where emp.gender.equals(&quot;F&quot;));</pre>
  778. </blockquote>
  779. <p>This is particularly useful where the output is large (even infinite!) and 
  780. you to iterate over the first few rows without computing the whole result.</p>
  781.  
  782. <p>The available types are {@link java.util.Iterator}, {@link 
  783. java.util.Enumeration}, {@link java.util.Collection}, {@link java.util.Vector}, 
  784. and <code>type[]</code>. In future, we may add {@link java.sql.ResultSet}.</p>
  785.  
  786. <h3><a name="Tables_and_Schemas">Tables and Schemas</a></h3>
  787.  
  788. <p>The interfaces Table, Schema and Connection allow you to access data sources
  789. which have arbitrary access methods. A table (<code>interface {@link
  790. saffron.Table}</code>) represents a set of relational data, and it provides
  791. methods to describe the data source, discover its access methods, and so
  792. forth. Schemas (<code>interface {@link saffron.Schema}</code>) make it easy to
  793. expose a set of tables and the information necessary to compile programs which
  794. use them. If you can to access data in a JDBC database, derive a class from
  795. <code>class {@link saffron.ext.ReflectSchema}</code> and create a member of
  796. type {@link saffron.ext.JdbcTable} for each table your wish to access
  797. (<code>class {@link sales.Sales}</code> is an example of this.)</p>
  798.  
  799. <p>Let's look at what happens when you compile a program which uses a
  800. schema.</p>
  801.  
  802. <ol>
  803.   <li>The compiler notices a piece of code (<code>sales.emps</code>) which 
  804.   accesses a member or method of an object (<code>sales</code>) which implements <code>
  805.   interface {@link saffron.Connection}</code>.</li>
  806.   <li>The compiler calls the static method <code>getSchema</code> on that 
  807.   object. (Why call a static method, not a method in the interface?&nbsp; 
  808.   Well, remember that this is happening at compile time. The real object 
  809.   does not exist yet.)</li>
  810.   <li>The compiler invokes the schema's <code>getMemberTable</code> or <code>
  811.   getMethodTable</code> method, to retrieve a <code>Table</code>. If there is no 
  812.   such table, these methods may throw <code>openjava.mop.NoSuchMemberException</code>, 
  813.   which will be reported as a compilation error.</li>
  814.   <li>The compiler invokes the table's <code>toRel</code> method, passing the 
  815.   piece of parse tree which represents the expression which will yields the 
  816.   schema. (The <i>real </i>schema object only gets created at run time, 
  817.   remember.)</li>
  818.   <li>The compiler calls schema's getTable method with the parse&nbsp; object 
  819.   be for example, class Sales.</li>
  820. </ol>
  821.  
  822. <p>In particular, we provide <code>abstract class {@link saffron.ext.JdbcTable}
  823. implements {@link saffron.Table}</code> to make it easy to access tables via
  824. JDBC. We recommend that you group tables into a schema class, which extends
  825. <code>class {@link saffron.ext.ReflectSchema}</code>. For
  826. example,</p><blockquote>
  827.  
  828.   <pre>class SalesConnection
  829.    extends saffron.ext.JdbcConnection
  830.    implements saffron.Connection
  831. {
  832.    public SalesConnection(String connect) {
  833.       super(connect);
  834.    }
  835.    // required for saffron.Connection
  836.    public static saffron.Schema getSchema() {
  837.       return new SalesSchema();
  838.    }
  839. };
  840.  
  841. class SalesSchema
  842.    extends saffron.ext.ReflectSchema
  843.    implements saffron.Schema
  844. {
  845.    public static class Emp {
  846.       public int empno;
  847.       public String name;
  848.       public int deptno;
  849.    };
  850.    public static class Dept {
  851.       public int deptno;
  852.       public String name;
  853.    };
  854.  
  855.    public saffron.Table emp = new saffron.ext.JdbcTable(
  856.       this, &quot;EMP&quot;, Emp.class);
  857.    public saffron.Table depts = new saffron.ext.JdbcTable(
  858.       this, &quot;DEPT&quot;, Dept.class);
  859. };
  860.  
  861. SalesConnection sales = new SalesConnection(&quot;jdbc:odbc:MyDatabase&quot;);
  862. for (emp in sales.emps) {
  863.   <i>some code</i>
  864. }</pre>
  865. </blockquote>
  866. <p>The Saffron compiler creates an instance of the schema, and interrogates it 
  867. regarding the objects it contains. When it sees the expression <code>sales.emps</code>, 
  868. it invokes <code>SalesConnection.getSchema().getTableForMember(&quot;emps&quot;)</code> to 
  869. get a {@link saffron.Table} which describes <code>emps</code> and, in particular, 
  870. that it returns rows of type <code>Emp</code>. The translator then calls 
  871. the table's <code>toRel()</code> method to create a relational expression node; 
  872. in this case a {@link saffron.rel.TableAccess}. (The translator actually converts <code>
  873. sales.emp</code> into a brief intermediate expression <code>(Emp[]) 
  874. sales.contentsAsArray(&quot;emps&quot;)</code>. The <code>contentsAsArray</code> function 
  875. is a placeholder which has special meaning to the translator. Note how an array 
  876. cast is used to provide type information.)</p>
  877.  
  878. <p>As well as type information, the schema could in future provide information
  879. about volumetrics, indexes, and even custom rules for optimizing the query.</p>
  880.  
  881. <p><i>todo</i>: Expose <code>Map</code>s (including <code>Hashtable</code>s) as 
  882. relations with 2 columns.</p>
  883. <h3>Non-relational schemas</h3>
  884. <p>A schema could be used to present non-relational data in a relational format. 
  885. It would know that 'getDept(40)' was the same as 'select from dept where deptno 
  886. = 40' and 'dept.getEmployees()' is the same as 'select from emp where emp.deptno 
  887. == dept.deptno'. We would need a mechanism to construct an <dfn>
  888. extent</dfn> (the set of all instances of a given 
  889. entity). The schema could declare an explicit method to find the instances of an 
  890. entity; another way is to use mandatory relationships (for example, since every 
  891. employee must work in a department, given all departments, we can find all 
  892. employees by traversing the 'works in' relationship). It helps if the 
  893. relationship is many- (or one-) to-one, since we don't need to eliminate 
  894. duplicates. There could be more than one access path to an entity.</p>
  895.  
  896. <p>How to represent such mappings? Views: dept.getEmployees() is equivalent to
  897. select from emp where emp.deptno == dept.deptno. Better, parameterized views.
  898. Example {@link sales.Reflect} presents Java's type system ({@link
  899. java.lang.Class}, {@java.lang.reflect.Field}, <i>et cetera</i>) as
  900. relations.</p>
  901.  
  902. <p><i>todo: </i>Could allow a type (e.g. <code>boolean</code>,
  903. <code>int</code>) to serve as a relation. Could implement by iterating over all
  904. possible values of that type (rarely practical) or joining to an attribute of a
  905. more finite relation. Example: <code>select from int as i where i in (select
  906. emp.deptno from emp)</code>.</p>
  907.  
  908. <h2>Null semantics</h2>
  909. <p>Saffron uses Java, not SQL, null semantics. <code>null</code> 
  910. is always the Java null value. Every boolean expression evaluates to 
  911. either <code>true </code>or <code>false</code>. And yes, <code>null == 
  912. null</code> evaluates to <code>true</code>.</p>
  913. <h2>Comparison semantics</h2>
  914. <p>In Saffron, as in Java, the <code>==</code> operator 
  915. compares addresses, not content. The expression <code>&quot;abc&quot; == &quot;a&quot; 
  916. + &quot;bc&quot;</code> may, on some Java systems, evaluate to false, so you should 
  917. write <code>&quot;abc&quot;.equals(&quot;a&quot; + &quot;bc&quot;)</code> instead.</p>
  918. <p>The <code>in </code>operator expands to expressions which use the <code>
  919. equals()</code> and <code>hashCode()</code> methods, so you should only uses it 
  920. on classes for which these methods are well-behaved. And the expression</p>
  921. <blockquote>
  922.   <pre>null in new String[] {&quot;apple&quot;, &quot;orange&quot;}</pre>
  923. </blockquote>
  924. <p>will give a <code>NullPointerException</code>.</p>
  925. <p>The <code>order by</code> operator requires that objects implement the <code>
  926. interface java.lang.Comparable</code>. (<i>todo: Compile- or run-time error if 
  927. not?</i>)</p>
  928. <p>Primitive types are compared using the primitive operators <code>==</code>, 
  929. <code>&lt;</code> etc.</p>
  930. <p>Two instances of a synthetic classes are equal if and only if each of their 
  931. components are equal. Synthetic classes are compared lexicographically. 
  932. Example:</p>
  933. <blockquote>
  934. <pre>select
  935. from (select from twos join threes) as i
  936. join (select from twos join threes) as j
  937. where i &lt; j</pre>
  938. </blockquote>
  939. <h2>Primitive values</h2>
  940. <p>Saffron accepts primitive values, such as <code>int</code>, <code>char</code>,
  941. <code>double</code>, in most places that it accepts objects. A couple of 
  942. exceptions:</p>
  943. <ol>
  944.   <li>Outer joins need to produce null values. For example,<pre>select {twos, threes}
  945. from new int[] {2, 4, 6, 8} as twos
  946. left join new int[] {3, 6, 9} as threes
  947. on twos == threes</pre>
  948.   would produce<pre>2, 0
  949. 4, 0
  950. 6, 6
  951. 8, 0 </pre>
  952.   </li>
  953.   <li>Saffron uses Java collections to implement certain algorithms. For example, 
  954.   in the following expression, it uses a Hashtable to detect values which have 
  955.   already been emitted.
  956.   <pre>select from new int[] {2, 4, 6, 8} as twos
  957. minus
  958. select from new int[] {3, 6, 9} as threes</pre>
  959.   It automatically boxes and unboxes primitive values.</li>
  960. </ol>
  961. <h2>Planning and evaluation</h2>
  962. <p>The Saffron system runs in static and dynamic mode.</p>
  963.  
  964.  
  965. <p>In static mode, relational expressions are embedded into Java programs. A 
  966. pre-processor checks that the relational expressions are valid, and converts 
  967. them into regular java. There are many ways to evaluate a relational expression, </p>
  968.  
  969.  
  970. <p>A query optimizer chooses an evaluation plan.</p>
  971. <h2>Evaluation model</h2>
  972. <h2>Implementation issues</h2>
  973.  
  974.  
  975. <h3>Composite rows</h3>
  976.  
  977.  
  978. <p>If a relational expression has more than one expression in its <code>select
  979. </code>clause, it produces rows which are not atomic. For example,</p>
  980.  
  981.  
  982. <blockquote>
  983.   <pre>int[] twos = new int[] {2,4,6,8};
  984. int[] threes = new int[] {3,6,9};
  985. for (i in (select twos, threes twos cross join threes)) {
  986.    ...
  987. }</pre>
  988. </blockquote>
  989. <p>creates rows which are pairs of <code>int</code>s. It is translated to</p>
  990. <blockquote>
  991.   <pre>int[] twos = new int[] {2,4,6,8};
  992. int[] threes = new int[] {3,6,9};
  993. for (int x = 0; x &lt; twos.length; x++) {
  994.    for (int y = 0; y &lt; threes.length; y++) {
  995.       Synth1 i = new Synth1(twos[x], threes[y]);
  996.       ...
  997.    }
  998. }</pre>
  999. </blockquote>
  1000. <p>This illustrates two issues with composite rows. First, these rows need 
  1001. a type. The Saffron compiler solves this issue by generating a synthetic 
  1002. class (in this case, <code>class Synth1</code>). We don't know what this 
  1003. class will be called, so we use <code>for (<i>variable</i> in ...)</code> 
  1004. syntax, which lets the system infer the type for us.</p>
  1005. <p>Second, the system creates a new object for every row, which might be 
  1006. expensive. In this case, they are emitted from the query, so we can't avoid 
  1007. creating them. If the composite rows are not emitted, the Saffron optimizer will 
  1008. do its best to avoid creating them.</p>
  1009. <h2>How the optimizer works</h2>
  1010. <p>The job of the optimizer is to convert a parse tree containing Saffron expressions into a regular parse tree. Its input and output, therefore, are both 
  1011. parse trees.</p>
  1012. <p>In between times, it searches for Saffron expressions, and converts them to 
  1013. tree of intermediate relational expressions (<code>class {@link saffron.rel.Rel}</code>).</p>
  1014. <p>These relational expressions still contain fragments of regular Java 
  1015. expressions for select expressions, method calls, and so forth. The Java 
  1016. expressions are translated into internal form. Except for references to 
  1017. variables outside the Saffron expression, variables tend to disappear, to be 
  1018. replaced by mysterious-looking expressions. For example, in the expression</p>
  1019. <blockquote>
  1020. <pre>select
  1021. from location
  1022. join (select
  1023.       from emp
  1024.       join dept on emp.deptno == dept.deptno)
  1025. on location.state.equals(dept.state) </pre>
  1026. </blockquote>
  1027. <p>the join condition <code>location.state.equals(dept.state)</code> becomes <code>$input0.state.equals($input1.$f1.state)</code>. 
  1028. Here, <code>$input0</code> and <code>$input1</code> represent the 2 
  1029. inputs to the join node (which is the context for this Java fragment); <code>$f1</code> 
  1030. is the first field of the composite row produced by the inner query. That 
  1031. field's type is Dept, and therefore it has a <code>state</code> field.</p>
  1032. <p>The optimizer uses a dynamic programming approach based upon that used by the 
  1033. Volcano optimizer. Starting with the initial expression, it applies 
  1034. transformation rules to convert it, and its sub-expressions, into semantically 
  1035. equivalent expressions. It estimates the cost of each expression, and 
  1036. cultivates variants of expressions until it finds cheap implementations of them.</p>
  1037. <p>An expression can be implemented using several <dfn>calling
  1038. conventions</dfn>. Calling conventions include array,
  1039. vector, iterator. The most important (and efficient) calling convention is 
  1040. inline. Inline means that a piece of code will be executed for every row 
  1041. in the expression; no collection of objects is created, just <i>stuff happens</i>. 
  1042. An inline implementation of</p>
  1043. <blockquote>
  1044.   <pre>for (o in (select from emp join dept on emp.deptno == dept.deptno)) {
  1045.   System.out.println(o.emp.ename + &quot; works in &quot; + o.dept.dname);
  1046. }</pre>
  1047. </blockquote>
  1048. <p>would be</p>
  1049. <blockquote>
  1050.   <pre>for (int i = 0; i &lt; emp.length; i++) {
  1051.    for (int j = 0; j &lt; dept.length; j++) {
  1052.       if (emp[i].deptno == dept[j].deptno) {
  1053.          Synth1 o = new Synth1(emp[i], dept[j]);
  1054.          System.out.println(o.emp.ename + &quot; works in &quot; + o.dept.dname);
  1055.       }
  1056.    }
  1057. }</pre>
  1058. </blockquote>
  1059. <p>This is rather tricky to implement, because the stuff in the middle of the 
  1060. for loop corresponds to stuff at the top of Rel tree. Each Rel node's 
  1061. implement method has to handle a callback from a child saying 'I have placed a 
  1062. row in variable <i>xyz</i>; please generate code to do something with it.'</p>
  1063.  
  1064.  
  1065.  
  1066. <p>If two expressions have the same meaning but different calling conventions, 
  1067. they are not immediately interchangeable. It may be cheaper to evaluate a 
  1068. particular expression as an array, but another algorithm may find it more 
  1069. convenient if that expression is a vector. For this reason, there are 
  1070. special kinds of rule called <dfn>conversion rules</dfn>. 
  1071. They can convert from one convention to another, but they have a non-zero cost. 
  1072. The optimizer may decide that it is cheaper to build a vector in the first 
  1073. place, rather than paying the cost of converting it to a vector later.</p>
  1074.  
  1075.  
  1076.  
  1077. <p>There is a special kind of node called a <dfn>Terminator</dfn> 
  1078. (<code>class {@link saffron.rel.java.Terminator}</code>). 
  1079. After a tree has been optimized, a Terminator is placed on the root to drive 
  1080. code-generation. It behaves somewhat like a Rel node (in that it has 
  1081. inputs, and can be called-back to generate code), but it does not actually 
  1082. produce any result. (<i>todo</i>: Maybe Terminator should be a calling 
  1083. convention?)</p>
  1084.  
  1085.  
  1086. <h1>Appendix 1: Design notes</h1>
  1087.  
  1088.  
  1089. <h2>Syntax of <code>group by</code></h2>
  1090.  
  1091.  
  1092. <p>There are several problems with a SQL-like aggregation:</p>
  1093. <ol>
  1094.   <li>If a <code>select</code> statement contains a <code>group by</code> clause, 
  1095.   the validation rules for expressions within that statement are altered: only 
  1096.   expressions which are in the <code>group by</code> can be used outside of an 
  1097.   aggregate function.</li>
  1098.   <li>Even if there is no <code>group by</code> clause present, aggregation 
  1099.   implicitly occurs if an aggregate function occurs anywhere in the <code>select</code> 
  1100.   statement. For example, every expression in<blockquote>
  1101.     <pre>select emp.gender.toLowerCase(), emp.name
  1102. from emp
  1103. where emp.name.startsWith(&quot;P&quot;)</pre>
  1104.   </blockquote>
  1105. <p>becomes illegal if an aggregation is added:</p>
  1106.   <blockquote>
  1107.     <pre>select emp.gender.toLowerCase(), emp.name
  1108. from emp
  1109. where emp.name.startsWith(&quot;P&quot;) &amp;&amp; min(emp.salary) &gt; 50000</pre>
  1110.   </blockquote>
  1111. <p>This syntax problem could be fixed fairly easily, by requiring an empty <code>
  1112. group by</code> clause in such cases.</p>
  1113.   </li>
  1114.   <li>If we allow functions on sets to be used as aggregation functions, then 
  1115.   certain statements are ambiguous. Consider the following:<blockquote>
  1116.     <pre>int count(Object[] a) {
  1117.     int n = 0;
  1118.     for (int i = 0; i &lt; a.length; i++) {
  1119.         if (a[i] != null) {
  1120.             n++;
  1121.         }
  1122.     }
  1123.     return n;
  1124. }
  1125. class Emp {
  1126.     String name;
  1127.     Person[] dependents;
  1128. };
  1129. select count(emp.dependents) from emp;</pre>
  1130.   </blockquote>
  1131.   <p>It is not clear whether Saffron should return a row for each employee with 
  1132.   the number of the dependents that employee has, or a single number, the number 
  1133.   of employees whose <code>dependents</code> field is not null.</li>
  1134. </ol>
  1135. <p>The underlying problem is that SQL aggregation makes a scalar expression 
  1136. behave like a set, and this undermines the usual rules of expression validation 
  1137. and type-checking. We can make the set explicit, but the resulting expression</p>
  1138. <blockquote>
  1139.   <pre>select deptno,
  1140.     sum(select emp.sal from emps as emp
  1141.            where emp.deptno == deptno) as sumSal,
  1142.     min(select emp.sal from emps as emp
  1143.            where emp.deptno == deptno) as minSal
  1144. from (select distinct deptno from emps) as deptno</pre>
  1145. </blockquote>
  1146. <p>is more verbose -- the underlying set, <code>emps</code>, is referenced three 
  1147. times -- and perhaps less efficient.</p>
  1148. <p>We need to make grouping an aggregation explicit.</p>
  1149. <p>QUEL aggregations are more like scalar sub-queries. They are more verbose. They are also more powerful: note how we can sum only female employees' 
  1150. salaries. In this syntax, the set of values to be aggregated over (in this case,
  1151. <code>select ... from emp</code>) is formed for each aggregate expression; the 
  1152. optimizer recognizes common expressions and evaluates them only once. Example:</p>
  1153. <blockquote>
  1154.   <pre><code>select distinct </code>emp.deptno,
  1155.   min(<code>select</code> emp.sal <code>from </code>emps <code>as </code>emp2
  1156.       <code>where </code>emp2.deptno == emp.deptno) <code>as </code>minSal
  1157.   sum(<code>select</code> emp.sal <code>from </code>emps <code>as </code>emp2
  1158.       <code>where </code>emp2.deptno == emp.deptno &amp;&amp;
  1159.           gender.equals(&quot;F&quot;)) <code>as </code>sumFemaleSal
  1160. <code>from </code>emps <code>as </code>emp</pre>
  1161. </blockquote>
  1162.  
  1163.  
  1164. <h2>Aggregation types</h2>
  1165. <p>Jim Gray et al. [<a href="#GBLP96">GBLP96</a>] classify aggregation operators into 3 
  1166. categories, in increasing order of complexity:</p>
  1167. <ul>
  1168.   <li><dfn>Distributive</dfn> aggregations requires fixed storage, and two totals can 
  1169.   be merged. Example: <code>sum</code>, <code>count</code>, <code>min</code>,
  1170.   <code>max</code>. To merge two partial sums, take <code>sum(S1 u S2) = 
  1171.   sum({sum(S1), sum(S2)})</code>. (Here, <code>S1</code> and <code>S2</code> are 
  1172.   the sets of values which formed the partial sums, and <code>S1 u S2</code> is 
  1173.   their union, the set of all values.) <code>min</code> and <code>max</code> 
  1174.   work the same. <code>count</code> is different, in that it cannot be used to 
  1175.   merge two sums; instead, you use <code>+</code>: <code>count(S1 u S2) = 
  1176.   count(S1) + count(S2)</code>.</li>
  1177.   <li><dfn>Algebraic</dfn> aggregations also require 
  1178.   fixed storage, but two totals cannot be merged. Example: <code>avg</code>,
  1179.   <code>stddev</code>.</li>
  1180.   <li><dfn>Holistic</dfn> aggregations require 
  1181.   variable storage. Example: <code>median</code>, <code>countDistinct</code>.</li>
  1182. </ul>
  1183. <p>Some algebraic aggregates can be decomposed into distributive aggregates, as 
  1184. follows: avg(S) = sum(S) / count(S). We could provide better 
  1185. support for these; maybe a new method &lt;code&gt;Expression {@link saffron.rel.Aggregation}.preExpand()&lt;/code&gt;, which is called before the parse tree is 
  1186. converted into a {@link saffron.rel.Aggregate} relational operator.</p>
  1187. <p>It is hard to implement holistic aggregations efficiently. For example, <code>
  1188. median</code> can be translated into an efficient relational expressions by 
  1189. hand:</p>
  1190. <blockquote>
  1191.   <pre>select {nth(countEmp / 2, salary) as medianSalary}
  1192. group by {emp.deptno}
  1193. from (select from emp order by emp.deptno) empSorted
  1194. join (select {emp.deptno, count() as empCount}
  1195.       group by {emp.deptno} from emp) empCounted
  1196. on empSorted.deptno == empCounted.deptno</pre>
  1197. </blockquote>
  1198. <p>Similarly distinct <code>count</code>:</p>
  1199. <blockquote>
  1200.   <pre>select {
  1201.     empGrouped.deptno,
  1202.     count(empGrouped.gender) as countDistinctGender}
  1203. group by {empGrouped.deptno}
  1204. from (
  1205.     select distinct {emp.deptno, emp.gender}
  1206.     from emps as emp) as empGrouped</pre>
  1207. </blockquote>
  1208. <p>We should supply an extender which can transform either the parse tree or the 
  1209. relational operator tree in such a way.</p>
  1210. <h2>Start parameters for aggregations</h2>
  1211. <p>Aggregations can take parameters per query, per group, and per row. Examples:</p>
  1212. <ul>
  1213.   <li>Conventional aggregations take parameters only per row.</li>
  1214.   <li>The nth(count, value), count is per-group, and value is per-row.</li>
  1215.   <li>In min(collator, value), collator is per-query, and value is per-row.</li>
  1216. </ul>
  1217. <p>One way to provide per-group parameters is for aggregations to have two sets 
  1218. of parameters: the first passed at start time, the other passed per row.</p>
  1219. <p>But custom aggregations can also do the job. They are a little less efficient, 
  1220. and the syntax is a little more verbose, but what's going on is clearer.
  1221. </p>
  1222. <p>Custom aggregation to do locale-specific min:</p>
  1223. <blockquote>
  1224.   <pre>select {emp.dept.deptno,
  1225.    new LocaleMin(emp.dept.locale).apply(name) minName}
  1226. group by {emp.dept}
  1227. from emps as emp</pre>
  1228. </blockquote>
  1229. <h2>Problems with iterators</h2>
  1230. <p><i>The ideas in this section are not implemented. So, if your iterator is 
  1231. infinite, the optimizer may generate a plan which never finishes. And it may 
  1232. generate a plan which requires iterators to be restarted.</i></p>
  1233. <p>Iterators (and enumerations) present peculiarities that finite data sources such as JDBC tables, arrays, 
  1234. and collections don't present.</p>
  1235. <p><b>Restarting an iterator</b></p>
  1236. <p>First, they need to be restarted. Suppose the optimizer implemented</p>
  1237. <blockquote>
  1238.   <pre>Iterator nouns, verbs;
  1239. for (i in (String[]) verbs intersect (String[]) nouns) {
  1240.    print(verb + &quot; is both a noun and a verb&quot;);
  1241. }</pre>
  1242. </blockquote>
  1243. <p>as a nested loops join,</p>
  1244. <blockquote>
  1245.   <pre>while (nouns.hasNext()) {
  1246.    String noun = (String) nouns.next();
  1247.    while (verbs.hasNext()) {
  1248.       String verb = (String) verbs.next();
  1249.       if (verb.equals(noun)) {
  1250.          print(verb &quot; is both a noun and a verb&quot;);
  1251.       }
  1252.    }
  1253. }</pre>
  1254. </blockquote>
  1255. <p>This doesn't work. The problem is, the second time around the outer loop,
  1256. <code>verbs.hasNext()</code> has already returned <code>false</code>.</p>
  1257. <p>If possible, you should use a class which implements {@link java.util.Collection} 
  1258. or {@link saffron.runtime.Iterable}; the optimizer calls the <code>iterate()</code> 
  1259. method each time it needs to start an iteration.</p>
  1260. <p>If you supply an {@link java.util.Iterator}, the optimizer wraps it in a {@link 
  1261.   saffron.runtime.BufferedIterator}.</p>
  1262. <p><i>Enhancement</i>: If the plan never requires that the iterator is 
  1263. restarted, the optimizer should leave the iterator unwrapped.</p>
  1264. <p><b>Infinite iterators</b></p>
  1265. <p>The second problem with iterators is that they can be infinite. This is a bad 
  1266. idea if you're copying the results to an array, but you can achieve spectacular 
  1267. results if you're prepared to go with the whole <i>streaming thing</i>. Here's 
  1268. an example:</p>
  1269. <blockquote>
  1270.   <pre>class MultiplesOf implements Iterator {
  1271.     int i, n;
  1272.     MultiplesOf(int n) {
  1273.         this.n = n;
  1274.         this.i = 0;
  1275.     }
  1276.     public boolean hasNext() {
  1277.         return true;
  1278.     }
  1279.     public Object next() {
  1280.         return i += n;
  1281.     }
  1282.     public void remove() {
  1283.         throw new UnsupportedOperationException();
  1284.     }
  1285. }
  1286.  
  1287. Iterator twos = new MultiplesOf(2);
  1288. Iterator tens = (Iterator) (select from twos where twos % 5 == 0);</pre>
  1289. </blockquote>
  1290. <p>We have created one infinite iterator from another!</p>
  1291. <p>The problem is that the optimizer might be tempted to do stupid things, like 
  1292. storing the results in an intermediate array. We tell it not to by implementing 
  1293. an empty interface, {@link saffron.runtime.Infinite}.</p>
  1294. <p><i>We have not implemented support for infinite iterators. Expressions 
  1295. involving infinite iterators might just go on for ever.</i></p>
  1296. <h1>Appendix 2: Futures</h1>
  1297. <p>List:</p>
  1298. <ol>
  1299.   <li>Aggregation<ol>
  1300.     <li>Allow built-in aggregations in regular java (that is, outside <code>
  1301.     select</code> statements with a <code>group by</code> clause). Example #1:
  1302.     <code>select {deptno, count(select from emps as e2 where e2.deptno == 
  1303.     e1.deptno) as countEmp} from emps as e1</code>. Example #2: <code>if (count(select from 
  1304.     emps as e2 where e2.deptno == e1.deptno</code>.</li>
  1305.   </ol>
  1306.   </li>
  1307.   <li>Schema on top of persistence layer -- JDO say. Or JAXB. Talk to Castor 
  1308.   folks about it.</li>
  1309.   <li>Refactoring.<ol>
  1310.     <li>search for obsolete &amp; deprecated</li>
  1311.   </ol>
  1312.   </li>
  1313.   <li>Demos<ol>
  1314.     <li>Swing application where you can enter expressions or statements, and 
  1315.     execute them. Can create a set of named connections.</li>
  1316.   </ol>
  1317.   </li>
  1318.   <li>Environment<ol>
  1319.     <li>log</li>
  1320.     <li>hsqldb</li>
  1321.   </ol>
  1322.   </li>
  1323.   <li>OpenJava<ol>
  1324.   <li>Obsolete MSJavaCompiler maybe</li>
  1325.   <li>Drive compiler from system properties</li>
  1326.   <li>Drive parser from system properties (or only have one parser, and turn off 
  1327.   saffron features programmatically).</li>
  1328. </ol>
  1329.  
  1330.  
  1331.   </li>
  1332. </ol>
  1333.  
  1334. <h1>Appendix 3: References</h1>
  1335.  
  1336. <dl>
  1337. <dt><a name="GBLP96">GBLP96</a></dt>
  1338.  <dd>J. Gray, A. Bosworth, A. Layman, and H. Pirahesh. Data cube: A relational 
  1339.  aggregation operator generalizing group-by, cross-tab, and sub-totals. In <em>
  1340.  IEEE 12th International Conference on Data Engineering</em>, pages 152&mdash;159, 
  1341.  1996 (<a href="http://research.microsoft.com/~gray/DataCube.doc">doc</a>).</dd>
  1342. </dl>
  1343.  
  1344. <table border="1" width="100%" class="clsStd">
  1345.   <tr>
  1346.     <td>End <i>$Id: //guest/julian_hyde/saffron/doc/overview.html#5 $</i></td>
  1347.   </tr>
  1348. </table>
  1349.  
  1350. </html>
  1351. </body>
# Change User Description Committed
#5 1748 Julian Hyde saffron:
convert unit tests to JUnit;
add CallingConvention.ITERABLE;
lots of other stuf...f;
release 0.1. «		 23 years ago
#4 1485 Julian Hyde Saffron/Mondrian: John Sichi's feedback. 23 years ago
#3 1474 Julian Hyde saffron:
Aggregations are working.
Renamed 'aggregator' to 'aggregation'. 		23 years ago
#2 1467 Julian Hyde saffron: First saffron check-in;
incorporate my changes to openjava. 		23 years ago
#1 1461 Julian Hyde saffron: First check in.
Just documents, and the unmodified OpenJava  20001010 source... files. «		 23 years ago