<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head profile="http://internetalchemy.org/2003/02/profile">
<link rel="foaf" type="application/rdf+xml" title="FOAF" href="http://www.openlinksw.com/dataspace/uda/about.rdf" />
<link rel="schema.dc" href="http://purl.org/dc/elements/1.1/" />
<meta name="dc.subject" content="SQL" />
<meta name="dc.subject" content="SQL Reference" />
<meta name="dc.subject" content="Select" />
<meta name="dc.subject" content="Update" />
<meta name="dc.subject" content="delete" />
<meta name="dc.subject" content="Select Statement" />
<meta name="dc.subject" content="SQL Syntax" />
<meta name="dc.subject" content="Syntax" />
<meta name="dc.title" content="8. SQL Reference" />
<meta name="dc.subject" content="8. SQL Reference" />
<meta name="dc.creator" content="OpenLink Software Documentation Team ; " />
<meta name="dc.copyright" content="OpenLink Software, 1999 - 2009" />
<link rel="top" href="index.html" title="OpenLink Virtuoso Universal Server: Documentation" />
<link rel="search" href="/doc/adv_search.vspx" title="Search OpenLink Virtuoso Universal Server: Documentation" />
<link rel="parent" href="sqlreference.html" title="Chapter Contents" />
<link rel="prev" href="BITMAPINDICES.html" title="Bitmap Indices" />
<link rel="next" href="sqlreffastphrasematch.html" title="Fast Phrase Match Processor" />
<link rel="shortcut icon" href="../images/misc/favicon.ico" type="image/x-icon" />
<link rel="stylesheet" type="text/css" href="doc.css" />
<link rel="stylesheet" type="text/css" href="/doc/translation.css" />
<title>8. SQL Reference</title>
<meta http-equiv="Content-Type" content="text/xhtml; charset=UTF-8" />
<meta name="author" content="OpenLink Software Documentation Team ; " />
<meta name="copyright" content="OpenLink Software, 1999 - 2009" />
<meta name="keywords" content="SQL; SQL Reference; Select; Update; delete; Select Statement; SQL Syntax; Syntax; " />
<meta name="GENERATOR" content="OpenLink XSLT Team" />
</head>
<body>
<div id="header">
<a name="transitivityinsQL" />
<img src="../images/misc/logo.jpg" alt="" />
<h1>8. SQL Reference</h1>
</div>
<div id="navbartop">
<div>
<a class="link" href="sqlreference.html">Chapter Contents</a> | <a class="link" href="BITMAPINDICES.html" title="Bitmap Indices">Prev</a> | <a class="link" href="sqlreffastphrasematch.html" title="Fast Phrase Match Processor">Next</a>
</div>
</div>
<div id="currenttoc">
<form method="post" action="/doc/adv_search.vspx">
<div class="search">Keyword Search: <br />
<input type="text" name="q" /> <input type="submit" name="go" value="Go" />
</div>
</form>
<div>
<a href="http://www.openlinksw.com/">www.openlinksw.com</a>
</div>
<div>
<a href="http://docs.openlinksw.com/">docs.openlinksw.com</a>
</div>
<br />
<div>
<a href="index.html">Book Home</a>
</div>
<br />
<div>
<a href="contents.html">Contents</a>
</div>
<div>
<a href="preface.html">Preface</a>
</div>
<br />
<div class="selected">
<a href="sqlreference.html">SQL Reference</a>
</div>
<br />
<div>
<a href="sqlrefDATATYPES.html">Datatypes</a>
</div>
<div>
<a href="udt.html">User Defined Types</a>
</div>
<div>
<a href="sqlrefxmldatatype.html">XML Column Type</a>
</div>
<div>
<a href="catidentifiers.html">Identifier Case & Quoting</a>
</div>
<div>
<a href="wideidentifiers.html">Wide Character Identifiers</a>
</div>
<div>
<a href="QUALIFIEDNAMES.html">Qualified Names</a>
</div>
<div>
<a href="litsbraceescs.html">Literals, Brace Escapes</a>
</div>
<div>
<a href="CREATETABLE.html">CREATE TABLE Statement</a>
</div>
<div>
<a href="DROPTABLE.html">DROP TABLE Statement</a>
</div>
<div>
<a href="CREATEINDEX.html">CREATE INDEX Statement</a>
</div>
<div>
<a href="DROPINDEX.html">DROP INDEX Statement</a>
</div>
<div>
<a href="ALTERTABLE.html">ALTER TABLE Statement</a>
</div>
<div>
<a href="CREATEVIEW.html">CREATE VIEW Statement</a>
</div>
<div>
<a href="CREATEXMLSCHEMA.html">CREATE XML SCHEMA Statement</a>
</div>
<div>
<a href="DROPXMLSCHEMA.html">DROP XML SCHEMA Statement</a>
</div>
<div>
<a href="sequenceobjects.html">Sequence Objects</a>
</div>
<div>
<a href="insertSTMT.html">INSERT Statement</a>
</div>
<div>
<a href="updatestmt.html">UPDATE Statement</a>
</div>
<div>
<a href="SELECTSTMT.html">SELECT Statement</a>
</div>
<div>
<a href="COMMIT_ROLLBACK.html">COMMIT WORK, ROLLBACK WORK Statement</a>
</div>
<div>
<a href="CHECKPOINT.html">CHECKPOINT, SHUTDOWN Statement</a>
</div>
<div>
<a href="spasviewsandtables.html">Stored Procedures as Views & Derived Tables</a>
</div>
<div>
<a href="GRANT.html">GRANT, REVOKE Statement</a>
</div>
<div>
<a href="SETstmt.html">SET Statement</a>
</div>
<div>
<a href="anytimequeries.html">Anytime Queries</a>
</div>
<div>
<a href="besteffortunion.html">Best Effort Union</a>
</div>
<div>
<a href="aggregates.html">Standard and User-Defined Aggregate Functions</a>
</div>
<div>
<a href="sqloptimizer.html">Virtuoso SQL Optimization</a>
</div>
<div>
<a href="sqlinverse.html">SQL Inverse Functions</a>
</div>
<div>
<a href="GRAMMAR.html">SQL Grammar</a>
</div>
<div>
<a href="BITMAPINDICES.html">Bitmap Indices</a>
</div>
<div class="selected">
<a href="transitivityinsQL.html">Transitivity in SQL</a>
</div>
<div>
<a href="sqlreffastphrasematch.html">Fast Phrase Match Processor</a>
</div>
<br />
</div>
<div id="text">
<a name="transitivityinsQL" />
<h2>8.32. Transitivity in SQL</h2>
<p>Virtuoso SQL supports tree and graph data structures represented with SQL relations through the use of transitive subqueries.</p>
<p>A derived table, i..e. a select inside a from clause, can be declared to be transitive. This is done by putting the TRANSITIVE modifier after the SELECT keyword, at the place where a DISTINCT or TOP modifier would go.</p>
<p>The syntax of this is:</p>
<div>
<pre class="programlisting">
transitive_decl ::= TRANSITIVE <trans_option>[, ...]
trans_opt :: =
| T_MIN (INTNUM)
| T_MAX (INTNUM)
| T_DISTINCT
| T_EXISTS
| T_NO_CYCLES
| T_CYCLES_ONLY
| T_NO_ORDER
| T_SHORTEST_ONLY
| T_IN <position_list>
| T_OUT ( <position_list )
| T_END_FLAG (INTNUM)
| T_FINAL_AS NAME
| T_STEP ( <position_or_path_spec> )
| T_DIRECTION (INTNUM)
position_list ::= INTNUM [,...]
position_or_path_spec ::= INTNUM | 'step_no' | 'path_id'
</pre>
</div>
<p>A transitive derived table has a selection that may consist of four different types of columns. These are input, output, step data and special columns.
When a transitive derived table occurs in a query, the enclosing query must specify an equality condition for either all input, all output columns or both.
The designation of input and output columns is for convenience only. The order of query execution will be generally decided by the optimizer, unless overridden with the T_DIRECTION option.
</p>
<p>Consider a simplified social network application:</p>
<div>
<pre class="programlisting">
create table knows (p1 int, p2 int, primary key (p1, p2))
alter index knows on knows partition (p1 int);
create index knows2 on knows (p2, p1) partition (p2 int);
insert into knows values (1, 2);
insert into knows values (1, 3);
insert into knows values (2, 4);
</pre>
</div>
<p>All persons have single integer identifiers. There is a row in the knows table if person p1 claims to know person p2.</p>
<p>The most basic query is to find all the people that a given person knows either directly or indirectly.</p>
<div>
<pre class="programlisting">
select * from (select transitive t_in (1) t_out (2) t_distinct p1, p2 from knows) k where k.p1 = 1;
</pre>
</div>
<p>The transitive derived table simply selects from the knows table. The
enclosing top level query gives an initial value for the input column
of the transitive select. This leaves the output column P2 unbound,
so the query will iterate over the possible values of P2. Initially,
the query loops over the people directly known by 1. In the next
stage, it takes the binding of P2 and uses it as a new value of the
input column P1 to look for people the first degree contact knows and
so on, until no new values are found.</p>
<p>The basic meaning of the transitive modifier is that given initial
values for input column(s), the subquery is evaluated to produce
values for the output columns. Then these values are fed back as
values of input columns and so forth, until some termination condition
is reached. If there are equality conditions for columns designated as output
but no conditions for columns designated as input, then the same
process runs from output to input. The terms input and output do not
imply execution order. If there are bindings for both input and
output columns in the enclosing query, then the transitive derived
table looks for ways of connecting the input and output bindings. If
no such way is found, the subquery is empty and causes the whole
enclosing query to also have no result. A transitive derived table
cannot be the right side of an outer join directly but can be wrapped
in a derived table that is. In this way, an outer join usage is also
possible, whether finding a path is optional.</p>
<p>The result set of a transitive subquery can be thought of as a set of
paths. A path consists of one or more consecutive bindings for the
input columns and is ordered. In our example, a path is p1=1, p1=2,
p1=4. This is the path connecting persons 1 and 4. If there are
columns in the select that are neither input or output, they too are
recorded for each step of the path. The result set may include just
the ends of a path, i.e. one row where the input columns have the
beginning and the output columns the end of the path. This means there is one row per distinct path. The result set may also include a row for each step on each path.
</p>
<p>In this example, we bind both ends of the transitive subquery and ask how person 1 and 4 are connected.
Since the columns p1 and p2 have an equality condition, each row of the result set has these at values 1 and 4 respectively.
</p>
<div>
<pre class="programlisting">
select * from (select transitive t_in (1) t_out (2) t_direction 3 t_distinct t_shortest_only p1, p2, t_step (1) as via, t_step ('path_id') as path , t_step ('step_no') as step from knows) k where p1 = 1 and p2 = 4;
P1 P2 VIA PATH STEP
1 4 1 0 0
1 4 2 0 1
1 4 4 0 2
</pre>
</div>
<p>The three rightmost columns allow returning information in the intermediate steps of the transitive evaluation. t_step (1) means the value of the column at position 1 at the intermediate step. The t_step ('step_no) is the sequence number of the step returned. The t_step ('path_id') is a number identifying the connection path, since there may be many paths joining persons 1 and 4.</p>
<p>In this situation, the result set has one row per step, including a
row for the initial and final steps. While the evaluation order may
vary internally, the result set is presented as if the query were
evaluated from input to output, i.e. looking for people known by 1,
finding 2 and 3, then looking for people they know, finding that 2
knows 4, which is a solution, since p2 = 4 was specified in the outer select.
If the outere query had p1 = 4 and p2 = 1, there would be an empty result set
since there is no path from 4 to 1.
</p>
<p>For example, if tables have multipart keys, there can be many input and output columns but there must be an equal number of both, since the engine internally feeds the output back into the input or vice versa. The transitive derived table may be arbitrarily complex.</p>
<p>We may have an application that returns extra information about a
step. This could for example be a metric of distance. In such a
case, a column which is neither designated as input nor output and is
not a t_step () function call, will simply be returned as is.
</p>
<p>The result set of a transitive subquery will either have one row for each state reached, or it may have one row for each step on the path to each state reached.</p>
<p>The first example returns only the ends of the paths, i.e. directly and indirectly known person id's. It does not return for each returned id how this person is known, through which set of connections.
The second example returns a row for each step on each path.
Steps will be returned if the selection has t_step () calls or columns that are neither input or output.
</p>
<p>The forms of t_step are:</p>
<div>
<pre class="programlisting">
t_step (<column number>)
</pre>
</div>
<p>This returns the value that the column, one of the columns designated
as input, has at this step. The input or output columns themselves, if
there is a condition on them, look equal to the condition. This
allows seeing intermediate values of input columns on a path.
</p>
<div>
<pre class="programlisting">
</pre>
</div>
<p>t_step ('step_no')</p>
<p>This returns the ordinal number of the step on the path. Step -0 corresponds to the input variables being at the value seen in the enclosing query. Step 1 is one removed from this. Step numbering is assigned as if evaluating from input to output.</p>
<p>Consider this:</p>
<div>
<pre class="programlisting">
select * from (select transitive t_in (1) t_out (2) t_min (0) t_distinct p1, p2, t_step (1) as via, t_step ('path_id') as path , t_step ('step_no') as step from knows) k where p1 = 1 ;
P1 P2 VIA PATH STEP
1 1 1 0 0
1 3 1 1 0
1 3 3 1 1
1 2 1 2 0
1 2 2 2 1
1 4 1 3 0
1 4 2 3 1
1 4 4 3 2
</pre>
</div>
<p>This returns four paths, all starting at 1: the paths. The path from
1 to 1, the path from 1 to 2, the path from 1 to 3 and the path from 1
to 2 to 4. The path_id column has values from 0 to 3, distinguishing
the four different paths returned. The p1 column is the start of the
path, thus always 1 since this is given in the outer query. The p2
column is the end of the path. The via column is the value of p1 at
the intermediate step. The step number where via is equal to p1 is 0.
The next step number is 1. At the highest step number of each path,
p2 and via are the same.</p>
<p>Now, let us do this in reverse:</p>
<div>
<pre class="programlisting">
select * from (select transitive t_in (1) t_out (2) t_min (0) t_distinct p1, p2, t_step (1) as via, t_step ('path_id') as path , t_step ('step_no') as step from knows) k where p2 = 4 ;
P1 P2 VIA PATH STEP
4 4 4 0 0
2 4 2 1 0
2 4 4 1 1
1 4 1 2 0
1 4 2 2 1
1 4 4 2 2
</pre>
</div>
<p>We give an initial value to p2 and leave p1 free. Now we get three
paths, the path from 4 to 4, from 2 to 4 and from 1 to 2 to 4. We
enumerate the steps as if counting from input to output, albeit
internally the evaluation order is the reverse. Again, step number 0
has the via column equal to p1 and the highest numbered step has via
equal to p2.</p>
<p>Now we may look more formally at the meaning of the transitive options:</p>
<ul>
<li>T_MIN (INTNUM) - This means that paths shorter than the number are not returned. In the examples above, we had min at 0, so that a path of zero length was also returned, i.e. where the first output equals the outer conditions for the inputs.</li>
<li>T_MAX (INTNUM) - This gives a maximum length of path. Paths longer than this many steps are not returned. A value of 1 means that the subquery is evaluated once, i.e. the outputs of the first evalyuation are not fed back into the inputs. Specifying a minimum of 0 and a maximum of one means an optional join. Specifying min and max both to 1 means an ordinary derived table.</li>
<li>T_DISTINCT - This means that if a binding of input columns is produced more than once, only the first is used. Id est, the same point is not traversed twice even if many paths lead to it.</li>
<li>T_EXISTS - Only one path is generated and returned.</li>
<li>T_NO_CYCLES - If a path is found that loops over itself, i.e. a next step has the input values equal to the input values of a previous step on the path, the binding is ignored.</li>
<li>T_CYCLES_ONLY - Only paths that have a cycle, i.e. input values of a subsequent step equal the input values of a previous step on the same path, are returned.</li>
<li>T_SHORTEST_ONLY - If both ends of the path are given, the evaluation stops at the length of path where the first solution is found. If many paths of equal length are found, they are returned but longer paths are not sought.</li>
<li>T_IN (column_positions) - This specifies which columns are called input.</li>
<li>T_OUT (column_positions) - This specifies which columns are called output.</li>
<li>T_DIRECTION INTNUM - A value of 0 (default) means that the SQL
optimizer decides which way the transitive subquery is evaluated. 1
means from input to output, 2 from output to input, 3 from both ends. Supposing we are looking at how two points are related, it makes sense to start expanding the transitive closure at both ends. in the above example, this would be going from p1 to p2 on one side and from p2 to p1 on the other.
</li>
</ul>
<div class="tip">
<div class="tiptitle">See Also:</div>
<a href="rdfsparql.html#rdfsparqlimplementatiotransexamples">Collection of Transitivity Option Demo Queries for SPARQL.</a>
</div>
<table border="0" width="90%" id="navbarbottom">
<tr>
<td align="left" width="33%">
<a href="BITMAPINDICES.html" title="Bitmap Indices">Previous</a>
<br />Bitmap Indices</td>
<td align="center" width="34%">
<a href="sqlreference.html">Chapter Contents</a>
</td>
<td align="right" width="33%">
<a href="sqlreffastphrasematch.html" title="Fast Phrase Match Processor">Next</a>
<br />Fast Phrase Match Processor</td>
</tr>
</table>
</div>
<div id="footer">
<div>Copyright© 1999 - 2009 OpenLink Software All rights reserved.</div>
<div id="validation">
<a href="http://validator.w3.org/check/referer">
<img src="http://www.w3.org/Icons/valid-xhtml10" alt="Valid XHTML 1.0!" height="31" width="88" />
</a>
<a href="http://jigsaw.w3.org/css-validator/">
<img src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!" height="31" width="88" />
</a>
</div>
</div>
</body>
</html>
distrib
>
Fedora
>
14
>
x86_64
>
media
>
updates
>
by-pkgid
>
71d40963b505df4524269198e237b3e3
>
files
>
899
