tag:blogger.com,1999:blog-48991561615268608822024-02-19T01:50:23.032-08:00Pyrrho DBMSThis blog is for discussions about the open source Pyrrho Database Management System.Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.comBlogger118125tag:blogger.com,1999:blog-4899156161526860882.post-77263677019596841612023-10-18T06:07:00.003-07:002023-12-02T05:56:47.283-08:00Typed Graph Implementation in PyrrhoDB<p>During 2023 I have been implementing Fritz Laux's concept of the Typed Graph Model (TGM) in PyrrhoDB. This is topical because ISO 9075-16 Property Graph Queries (SQL/PGQ) was published this year, and the new draft international standard ISO 39075 Graph Query Language (GQL) is in development and likely to be published in early 2024. In all three cases, we have the prospect of a full integration between the hitherto different topics of graph databases and relational databases.</p>
<p>PyrrhoV7alpha 7.06 is available on github, and contains considerable progress in this direction. This blog post is based on sections of the Pyrrho Manual and "Introduction to the Source Code of the PyrrhoDBMS" document in that repository.
The important point in the implementation of
typed graphs in Pyrrho is that graph data can be entered and modified using
either relational SQL or the CREATE and MATCH statements, and Pyrrho maintains
all of the base tables and indexes to make this work. The graph matching algorithms support repeating patterns and are reminiscent of Prolog backtracking in their use of continuations.
The implementation takes care to respect transactions, roles, etc and all the RDBMS aspects, while making the creation and modification of graph data as smooth as possible.</p>
<p>A NodeType (or EdgeType) corresponds to a single
database object that defines both a base Table in the database and a
user-defined type for its rows. This UDT is managed by the database engine by
default, but the usual ALTER operations are available for both Table and UDT. Its
first column is a primary key ID of type INT, usually provided in the CREATE
statement, or if this is not supplied, a new int value.
Other columns are provided in the node type for any properties that are defined
for a node of this type.</p>
<p>An EdgeType additionally specifies NodeTypes for
Leaving and Arriving foreign key columns (an edge is said to leave a node and
arrive at another). This means that all
leaving nodes for an edge type have the same node type (and similarly all
arriving nodes for an edge type have the same node type. As usual with foreign
keys, the engine maintains multisets for the reverse relationships (edges leaving
from or arriving at the node).</p>
<p>TNode and TEdge are TypedValues whose dataType is a
NodeType (resp EdgeType). A TGraph is a collection of node and edge uids.</p>
<p>Nodes and edges are rows in the tables thus
defined, and these can be updated and deleted using SQL in the usual ways,
while ALTER TYPE, ALTER DOMAIN and ALTER TABLE statements can be applied to
node and edge types.</p>
<p>In CREATE TYPE statements, metadata is available to
declare a new type as a node type or an edge type, automatically specifying the
ID (resp. ID, LEAVING and ARRIVING) columns and constraints as column 0 (resp,
0,1,2). A more convenient
mechanism for defining or adding to typed graphs is provided by the CREATE syntax.</p>
<p><b>Creating graph data in the RDBMS</b></p>
<p>A Neo4j-like syntax can be used to add one or more
nodes and zero or more edges using the CREATE statement defined below:</p>
<p>CreateStatement = CREATE Graph {THEN Statement END}</p>
<p>Graph= Node Path {',' Node Path } .</p>
<p>Path = { Edge Node } .</p>
<p>Node = '(' GraphItem ')' .</p>
<p>Edge= '-[' GraphItem ']->' | '<-[' GraphItem ']-'</p>
<p>GraphItem = [id |
<i>Node_</i>Value] [GraphLabel] [ Document] .</p>
<p>GraphLabel = ':' (id | <i>Label_</i>Value) [GraphLabel] .</p>
<p>In this syntax we see new diglyph and triglyph tokens for indicating the start and end of directed edges. In this syntax id is an SQL identifier for later reference in the statement, not a node ID: node and edge identities are specified in the JSON document doc. Pyrrho will supply a default value for ID if not specified.</p>
<p>The Label identifies a node or edge type (with an optional subtype), which may be new. As suggested above, the columns of new node and edge types are inferred from supplied property values and automatically modified as needed. All nodes and edges by default have the special property ID of type INT. The syntax connects up the edges: it is not permitted to specify leaving and arriving nodes explicitly.</p>
<p>As indicated, the syntax can contain a comma-separated list of graph fragments. The engine endeavours to combine these, verifying or modifying the available node and edge types, and defining new nodes and edges.</p>
<h3><b>Retrieving graph data from
the RDBMS</b></h3>
<p>The given graph fragments are evaluated in a
recursive process that finds sets of values for unbound identifiers, for which
the graph fragments are all found in the database. The result is thus a set of
successful assignments of unbound identifiers to TypedValues. The Statement if
supplied is executed for each row of this set. To be unbound, an identifier
should not match any top-level database object (table, view, domain, type,
procedure) or any identifier defined earlier in the current SQL statement.
If there are no unbound identifiers in the
MatchStatement, its value is just a Boolean indicating whether all of the
fragments were found. = MATCH Match {',' Match} [WhereClause]
[Statement] [THEN Statements END ] .</p>
<p>The
Match statement computes a rowset of bindings for unbound identifiers (or a
boolean if there are none) for which the Match is found in all or a selected
set of graphs in the database (see MatchMode below). The Statement if present is
executed for each row of bindings and may replace it with the result of a RETURN
statement. If the Statement is present but has no RETURN, or if it changes the
database, there is no rowset result for the MatchStatement. Match removes
duplicate rows from its bindings and from the result if present. The THEN
clause if present has access to the bindings but does not alter the result
rowset.</p>
<p>Match = (MatchMode [id '='] MatchNode) {'|' Match}.</p>
<p>MatchNode = '(' MatchItem ')' {(MatchEdge|MatchPath)
MatchNode}.</p>
<p>MatchEdge = '-[' MatchItem '->' | '<-' MatchItem ']-' .</p>
<p>MatchItem = [id |
<i>Node_</i>Value] [GraphLabel] [ Document | Where ] .</p>
<p>MatchPath = '[' Match ']' MatchQuantifier .</p>
<p>MatchQuantifier = '?' | '*' | '+' | '{' int , [int] '}' .</p>
<p>MatchMode = [TRAIL|ACYCLIC| SIMPLE] [SHORTEST |ALL|ANY] .</p>
<p>The
MatchMode controls how repetitions of path patterns are managed in the graph matching
mechanism. A MatchPath creates lists of values of bound identifiers in its
Match. By default, binding rows that have already occurred in the match are
ignored,
and paths that have already been listed in a quantified graph are not followed.
The MatchMode modifies this default behaviour: TRAIL omits paths where an edge
occurs more than once, ACYCLIC omits paths where a node occurs more than once,
SIMPLE looks for a simple cycle. The last three options apply to
MatchStatements that do not use the comma operator, and select the shortest
match, all matches or an arbitrary match.</p>
<b>The Graph view of graph
data</b>
<p>The database is considered to contain a (possibly
empty) set of disjoint TGraphs. Every Node in the database belongs to exactly
one graph in this set.</p>
<p>The nodes of a graph are totally ordered by the
order of insertion in the database, but this is not the traversal ordering: the
first node in a graph is the first in both orderings. The traversal ordering
starts with this first node but preferentially follows edges: the leaving edges
ordered by their edge types and edge uids followed by arriving edges ordered
similarly, while not visiting any node or edge more than once.</p>
<p>The set of graphs is (internally) totally ordered
by the defining position of their first node.</p>
<p> In the data management language, an SqlNode is an
SqlRow whose domain is a Node type. Evaluation of the SqlNode gives an explicit
rowset of TGraph values. A TGraph specified in the above ways may match a
subgraph of one of the graphs in this set, in which case we say the TGraph is
found in the database.</p>
<h3>The relational view of graph data</h3>
<p>Graph models are typed
collections of nodes and edges. This means that node and edge types are defined
with particular typed properties including an integer identity, and for edge
types, a leaving and an arriving integer property. Each node or edge type has a
collection of nodes and edges, and these can be identified with a relational
table whose columns of the properties of the node type/edge type, and whose
rows are the values of the properties of a particular node.</p>
<p>The leaving and arriving
properties of edges can be thought of as connecting the nodes into directed
graphs. The leaving and arriving properties behave like foreign keys to a
particular node type. Types can have subtypes (using the standard UNDER
keyword).</p>
<p>The above description
highlights the similarities with the relational model, so that it becomes
natural to add the node/edge type behaviour to a relational type by simple
metadata added to a standard type declaration with syntax respectively.</p>
<p>NODETYPE ['(' <i>Identity_</i>id [CHAR] ')']</p>
<p>Where id is an optional name
for the identity column (if not specified, a column of type INT called ID is
used, or added if not already specified).
The column is automatically the primary key of the node type, but also accesses
the database-wide collection of nodes and edges. By default it is an integer, but may be declared as a string type.</p>
<p>EDGETYPE [<i>Identity_</i>id ]
'('[<i>Leaving_</i>id '='] <i>NodeType_</i>id ',' [<i>Arriving_</i>id '='] <i>NodeType</i>_id
')'</p>
<p>If not specified, columns of type
string called LEAVING and ARRIVING are used or added if not already specified
or inherited in the type declaration.</p>
<p>The identifiers ID, LEAVING
and ARRIVING are not reserved words, and these columns can be renamed on a
per-role basis subject to the usual rules and permissions. The identities of
these structural columns are however inherited by subtypes. Columns added to a
type in this way are appended to the row type.</p>
<p>The simplest node type (for a
new node type called MYTYPE), containing only an identity column, is defined by
the SQL statement</p>
<p>CREATE TYPE mytype NODETYPE</p>
<p>Additional columns can be specified in the usual ways,
by declaring the new type to be UNDER and existing type and/or adding a clause
AS '(' column_list ')' before the metadata part. A subtype of a node or edge type automatically
inherits all its properties, so the metadata keywords should not occur in the
declaration of a subtype of a node type or edge type. Edge types can be
similarly defined in SQL.</p>
<p>The Graph CREATE statement has
been added to facilitate rapid creation of graph types, nodes and edges. It
uses extra token types for indicating directed arrows for edge connections and
a JSON-style notation for providing property lists, so that a single statement
can create many node types, edge types, and nodes and edges whose associated
tables and columns are set up behind the scenes (in one transaction). Identifiers
can be defined in the CREATE statement following the usual left-to-right
conventions, and Pyrrho will supply an integer id value using its autokey
feature if necessary. All such database items can be subsequently retrieved using
MATCH and modified using SQL DDL statements such as SQL UPDATE, ALTER
statements and now CREATE. An
extra feature allows CREATE to be followed by a THEN clause which allows DDL
and DML statements to use the identifiers accumulated during the CREATE.
</p><p>Columns for node and edge types can thus be
declared in three ways: (a) explicitly in the type clause of CREATE TYPE
following the AS keyword, (b) ID, LEAVING and ARRIVING, in metadata in CREATE
TYPE, (c) in the graph CREATE statement for a previously unknown Node or Edge
label. In case (c) the values of these properties are also provided for the
first node or edge of the new node or edge type.</p>
<p>In all cases, the NodeType.Build method
does the actual work of creating the node or edge type and ensuring that the
special properties ID, LEAVING , and ARRIVING have appropriate columns and
indexes in the new type (or its supertypes). Even for a simple
type-declaration, the transaction will require several stages of database
object construction. </p>
<p>The parsing of these statements results in
a set of physical records for the transaction log: (1) PNodeType or PEdgeType
giving merely the name of the new type and its supertype (if there is a
supertype all its supertypes and subtypes, and their supertypes and subtypes,
will be modified to record this); (2) The new columns of the new type, that is,
columns not inherited from supertypes (installing these objects modifies the
parent type); (3) new indexes, for the primary key of the new type, and the two
special foreign keys of a new edge type (installing these objects will modify
the node/edge type to note their uids); and (4) for the graph create statement,
Records containing new nodes and edges. </p>
<p>The label part for a node or edge can be a
chain of identifiers in supertype to subtype order, but subtypes are first
class types in the role and can be referenced on their own. Subtypes inherit
the identity column (and leaving, arriving columns for edge types) so that the
primary key of the subtype is also the primary key of the supertype. If a chain
of labels is used for a new node or edge, any new columns are added to the
first type in the chain. A new edge type in a CREATE statement will use the
specified types for its leaving and arriving node type constraints.</p>
<p>Then supertypes are created before
subtypes, node and edge types before edges, and columns before their indexes.
The syntax ensures some regularity, and, for the most part, the class structure
of the implementation is helpful. But it is useful at this point in the
documentation to distinguish the various tasks and how their supported in the
parser. In this version, the base table of a user-defined types has a rowType
consisting (only) of the columns declared in the most specific type, but all
records may contain values for columns in its pathDomain, which also contains
columns inherited from supertypes if any. EdgeType is a subclass of NodeType,
so in the discussion of the implementation below we can write node type even if
we mean node type or edge type.</p>
<h3>Additional data types in the implementation</h3><p>Every node (TNode) has a unique integer identifier we refer to in
these notes as <b>id</b> (whatever its column name is in the current role) and
this can be modified using an SQL update statement: its value is independent of
the role. The TNode also has a uid property that identifies the database
TableRow discussed above. TNode is a subclass of TRow and its fields are the
fields of this TableRow.</p>
<p>Every edge (TEdge) has a leaving property and an arriving property
whose values reference actual nodes: the database maintains indexes to the
actual TNodes. These properties are initially called LEAVING and ARRIVING but
can be modified for the model. TEdge is a subclass of TNode, so edges have the identifiers
and properties discussed above.</p>
<p>A graph (TGraph) is a collection of TNodes. A database TNode, in principle, identifies a
graph consisting of all nodes that be reached by following edges. The database
maintains a set of such connected TGraphs that cover the database. Any such
connected TGraph can be represented by its base node (the oldest, which has the
lowest uid). It follows that TGraphs in the database are not modified directly.
</p><p>TGParam is a class of TypedValues used only in MatchStatements,
which has a lexical uid from its first occurrence in the statement, a type
indicating its use in the MatchStatement (flags for node, edge, path, group,
nullable) and its name (a string). It is initially unbound, and once bound its
value is found in the Context's list of
bindings. TGParams can occur as the id of a node or edge, as the label part, or
in SqlLiterals. </p><p>A MatchStatement is a collection of TGParams, a list of SqlNodes,
and possibly where clause and a procedural body. An SqlNode keeps track of the
TGParams they introduce, and SqlValues for id, type, and properties (a list of
SqlValue key/value pairs: each key is a list of SqlValues that evaluate to strings).
SqlNode has a subclass SqlEdge, which also has SqlValues for its leaving and arriving
SqlNode, SqlEdge has a sbclass SqlPath, which has a pattern (a list of SqlNodes)
and a pair of integers called the MatchQuantifier in the syntax for
MatchStatement. All these evaluate to the binding of their id (a TNode or
TEdge).</p><h3 style="text-align: left;">The Match Algorithm</h3>
<p>When a MatchStatement is executed, the Context may already contain
bindings from an enclosing Match in progress, but its own bindings will be
unbound. The MatchStatement examines the first node in its list of SqlNodes and
creates a continuation consisting of the rest of its list. On examination of
this first SqlNode, a set of
database nodes of its required type and properties is constructed; on
examination of an SqlPath, the continuation is the pattern. For each element of
this set, the SqlNode's TGParams are bound, and traversal continues to the next
node in the continuation. . If there is no next node in the continuation, all
SqlNodes in the MatchStatement have been bound to database rows (TNodes): subject
to the where clause if any, the body of the match statement is obeyed, or if
there is no body, a row of bindings is added to the result of the
MatchStatement. When all elements at the
current stage have been examined, the TGParams in the SqlNode's list are
removed from the list of bindings. When the recursion is complete, the
MatchStatement's side-effects have occurred and/or the rowset result has been
built.</p>
<p>In some ways, unbound identifiers are like the
aliases used in ordinary SQL, since they are given a meaning inside the current
statement and then forgotten after it is executed. But there is an important
difference: by its nature the MatchStatement looks to match unbound identifiers
with database objects, so that if you want a new unbound identifier you need to
avoid the names of existing database objects (tables, types, procedures, or
columns, fields or methods of objects referenced in the current statement), or
currently bound identifiers or aliases. These observations also apply to the
use of unbound identifiers in the CreateStatement, which also can have a
dependent executable statement. In this section we examine more sophisticated
opportunities provided by MATCH.</p>
<p>Like the CreateStatement, the Match statement consists of a set of
graph fragments, but like a SELECT statement as it builds a rowset whose
columns are unbound identifiers in the graph syntax. Such
identifiers can occur anywhere in the graph syntax, and as its name implies,
the MATCH statement finds all possible values of these such that the graph
fragments are found in the database.</p>
<p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">[CREATE<o:p></o:p></span></span></b></p><p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">(:Product:WoodScrew
{spec:'16/8x4'}),(:Product: WallPlug{spec:'18cm'}),<o:p></o:p></span></span></b></p><p class="MsoNormal" style="text-align: justify;"><v:shapetype coordsize="21600,21600" filled="f" id="_x0000_t75" o:preferrelative="t" o:spt="75" path="m@4@5l@4@11@9@11@9@5xe" stroked="f"><b><span style="font-family: courier; font-size: x-small;">
<v:stroke joinstyle="miter">
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0">
<v:f eqn="sum @0 1 0">
<v:f eqn="sum 0 0 @1">
<v:f eqn="prod @2 1 2">
<v:f eqn="prod @3 21600 pixelWidth">
<v:f eqn="prod @3 21600 pixelHeight">
<v:f eqn="sum @0 0 1">
<v:f eqn="prod @6 1 2">
<v:f eqn="prod @7 21600 pixelWidth">
<v:f eqn="sum @8 21600 0">
<v:f eqn="prod @7 21600 pixelHeight">
<v:f eqn="sum @10 21600 0">
</v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:formulas>
<v:path gradientshapeok="t" o:connecttype="rect" o:extrusionok="f">
<o:lock aspectratio="t" v:ext="edit">
</o:lock></v:path></v:stroke></span></b></v:shapetype><v:shape alt="A computer screen shot of a black screen
Description automatically generated" id="Picture_x0020_1" o:spid="_x0000_s1026" style="height: 377.3pt; left: 0; margin-left: 342pt; margin-top: 1.2pt; mso-position-horizontal-relative: text; mso-position-horizontal: absolute; mso-position-vertical-relative: text; mso-position-vertical: absolute; mso-width-percent: 0; mso-width-percent: 0; mso-width-relative: margin; mso-wrap-distance-bottom: 0; mso-wrap-distance-left: 9pt; mso-wrap-distance-right: 9pt; mso-wrap-distance-top: 0; mso-wrap-style: square; position: absolute; text-align: left; visibility: visible; width: 116.85pt; z-index: 251784192;" type="#_x0000_t75">
<v:imagedata o:title="A computer screen shot of a black screen
Description automatically generated" src="file:///C:/Users/Malcolm/AppData/Local/Temp/msohtmlclip1/01/clip_image001.png"><b><span style="font-family: courier; font-size: x-small;">
<w:wrap type="square">
</w:wrap></span></b></v:imagedata></v:shape><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">(Joe:Customer
{Name:'Joe Edwards', Address:'10 Station Rd.'}),<o:p></o:p></span></span></b></p><p>
</p><p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">(Joe)-[:Ordered
{"Date":date'2002-11-22'} ]->(:"Order"{id:201})]<o:p></o:p></span></span></b></p><p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">[MATCH (O:"Order"{id:201})<o:p></o:p></span></span></b></p><p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;">begin MATCH(P:Product{spec:'16/8x4'}) CREATE
(O)-[:Item {Qty: 5}]->(P);<o:p></o:p></span></span></b></p><p class="MsoNormal" style="text-align: justify;">
</p><p class="MsoNormal" style="text-align: justify;"><v:shapetype coordsize="21600,21600" filled="f" id="_x0000_t75" o:preferrelative="t" o:spt="75" path="m@4@5l@4@11@9@11@9@5xe" stroked="f"><span style="font-family: courier; font-size: x-small;">
<v:stroke joinstyle="miter">
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0">
<v:f eqn="sum @0 1 0">
<v:f eqn="sum 0 0 @1">
<v:f eqn="prod @2 1 2">
<v:f eqn="prod @3 21600 pixelWidth">
<v:f eqn="prod @3 21600 pixelHeight">
<v:f eqn="sum @0 0 1">
<v:f eqn="prod @6 1 2">
<v:f eqn="prod @7 21600 pixelWidth">
<v:f eqn="sum @8 21600 0">
<v:f eqn="prod @7 21600 pixelHeight">
<v:f eqn="sum @10 21600 0">
</v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:f></v:formulas>
<v:path gradientshapeok="t" o:connecttype="rect" o:extrusionok="f">
<o:lock aspectratio="t" v:ext="edit">
</o:lock></v:path></v:stroke></span></v:shapetype><v:shape alt="A screen shot of a black screen
Description automatically generated" id="Picture_x0020_1" o:spid="_x0000_s1026" style="height: 78.75pt; left: 0; margin-left: 306pt; margin-top: 8.25pt; mso-position-horizontal-relative: text; mso-position-horizontal: absolute; mso-position-vertical-relative: text; mso-position-vertical: absolute; mso-wrap-distance-bottom: 0; mso-wrap-distance-left: 9pt; mso-wrap-distance-right: 9pt; mso-wrap-distance-top: 0; mso-wrap-style: square; position: absolute; text-align: left; visibility: visible; width: 131.25pt; z-index: 251785216;" type="#_x0000_t75">
<v:imagedata o:title="A screen shot of a black screen
Description automatically generated" src="file:///C:/Users/Malcolm/AppData/Local/Temp/msohtmlclip1/01/clip_image001.png"><span style="font-family: courier; font-size: x-small;">
<w:wrap type="square">
</w:wrap></span></v:imagedata></v:shape><b><span lang="EN-US"><span style="font-family: courier; font-size: x-small;"> MATCH(P:Product{spec:'18cm'}) CREATE
(O)-[:Item {Qty: 3}]->(P) end]</span></span></b><span lang="EN-US"> </span><b><span lang="EN-US" style="font-family: Consolas; font-size: 8.0pt; mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;"><o:p></o:p></span></b></p>
<p><span style="font-family: courier;"><b>MATCH ()-[:Item {Qty:A}]->(:T{spec:X})
where A>4</b></span></p>
<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEi0DX6ESeUadDag78KGQQnMH4UHAEo63JFNsMQmTX1GJXchm5mlEygH4SXtI85DUPDbhZiOgHgzy8sWIhAKsZDx3h_lLbjFwBmiPXsKRyIbIx7ho88u_umAnl7PzT1lHZakNULnmJlQ2rwcYrwlGwjxLxR8MargZ-0hx2GQ6iNK2_TlFgJN-e3PZ-QfjkiS" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="145" data-original-width="528" height="125" src="https://blogger.googleusercontent.com/img/a/AVvXsEi0DX6ESeUadDag78KGQQnMH4UHAEo63JFNsMQmTX1GJXchm5mlEygH4SXtI85DUPDbhZiOgHgzy8sWIhAKsZDx3h_lLbjFwBmiPXsKRyIbIx7ho88u_umAnl7PzT1lHZakNULnmJlQ2rwcYrwlGwjxLxR8MargZ-0hx2GQ6iNK2_TlFgJN-e3PZ-QfjkiS=w456-h125" width="456" /></a></div>Taking the last example above and modifying it a little to reduce
the number of steps below, let us trace through the execution of<p></p><p><span style="font-family: courier;"><span>12345678901234567890123456789012345678901234567890</span><br /></span><span style="font-family: courier;"><b>match (:"Order")-[:Item where
Qty>4]->(:T{spec:X})</b></span></p><p><span style="font-family: inherit;">The MatchStatement (referred to as %5 below) defines TGParams T and X and has a single graph whose nodes
are the SqlNode #8, the SqlEdge #19, and the SqlNode #40. Looking at the
TGParams we see that their properties remain to be discovered during the Build
method of the MatchStatement.</span></p>
<p>The two main methods in the implementation of MatchStatement are: </p><p>void ExpNode(Context cx, ExpStep be, Sqlx tok, TNode? pd)</p><p><span style="text-align: justify;">which is passed the current position in the Match Expression in a </span><i style="text-align: justify;">continuation</i><span style="text-align: justify;">
<b>be</b> (as we will see below) and some context tok and pd, and DbNode: </span></p><p>void DbNode(Context cx, NodeStep bn, Sqltok, TNode? pd)</p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">which is passed a list of relevant nodes in its continuation <b>bn</b>. In
both cases the continuation specifies what the algorithm does if the algorithm
is able to move to the next SqlMatch node. If all the nodes have matched and
there no further nodes, the AddRow method will be called by the EndStep of the
continuation to add a row of bindings to the result in an ExplicitRowSet constructed for the MatchStatement.<o:p></o:p></span></p>
<p><span style="text-align: justify;">To start the process, ExpNode is called as follows:</span> </p><p><span style="font-family: courier;">ExpNode(cx, new ExpStep(sa.mode, xf, new GraphStep(gf.Next(), new EndStep(this), Sqlx.Null, null);</span></p><p><span style="text-align: justify;">We can see that the continuation specifies the current match
expression xf, the remaining graphs of the Match statement gf.Next() (there are
none in this case), and the EndStep. The four continuation classes visible above
are subclasses of Step, and each Step contains a link to the next step. Step has
one more subclass, PathStep, which is discussed in the next section. We start with the first node in the first Graph (gf is a
bookmark for the first MatchAlt in the MatchStatement) and an ExpStep (sa is the first MatchAlt, and xf is a
bookmark for sa’s first MatchExp)</span>.</p>
<p>Thus, the first step in the match is</p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span style="font-family: Consolas;">Step 1: ExpNode({Exp[#8,#19,#40],Graph[],End[%5]},
Null, null)</span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span style="font-family: Consolas;">xn<-{SqlNode COLON #8 421 Order NODETYPE
(444)[444,Domain INTEGER] rows 1 Indexes:((444)468) KeyCols: (444=True)
IdIx=468 IdCol=444 [#9]}</span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US"><span style="font-family: inherit;">ExpNode constructs a list of relevant nodes in the database. There is just one at this stage:</span></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">ds {(487=..)}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;">
</p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">
ds[0].vals {(444=201)}<span style="font-size: 8pt;"><o:p></o:p></span></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US" style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;">We now call DbNode for this list of possible matches, with a
continuation consisting of a NodeStep for the first node in the list ds,
followed by an ExpStep for the rest of the current graph, and the rest of the
continuation.<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 2: DbNode</span><span lang="EN-US">
</span><span lang="EN-US" style="font-family: Consolas;">{Node#8:[487],Exp[#19,#40],Graph[],End[%5]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 487[421]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;">
</p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">
dn.tableRow {(444=201)}<span style="font-size: 8pt;"><o:p></o:p></span></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US" style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;">This node
matches our requirements so DbNode adds any relevant bindings. There are no bindings for this SqlNode, so and the
Next method for our NodeStep continuation takes us to the next SqlNode in the
graph, remembering the node we have just left:<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 4: DbNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">({Node#19:[990,1024],Exp[#40],Graph[],End[%5]},
ARROWBASE, {TNode 487[421]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> dn<-{</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 990[774]} vals
{(802=1,847=201,905=1,963=5)}<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US">Again, we hit the DoBindings breakpoint (since Qty is 5) and Next
takes us to<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 5: ExpNode({Exp[#40],Graph[],End[%5]}, ARROWBASE,
{TEdge 990[774]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> xn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{SqlNode COLON
#40 -509 NODETYPE rows 0 [#41] {#43=#48}
TYPE T,#41 T,#48 X}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{[157,{{(48=1,88=16/8x4)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US">This time, in DbNode, when we hit DoBindings, we add bindings for
T and X:<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 6: DbNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{Node#40:[157],Exp[],Graph[],End[%5]},
ARROWBASE, {TEdge 990[774]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 157[113]}<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">
</p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> cx.binding<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{(#41=WOODSCREW,#48=16/8x4)}<span style="font-size: 8pt;"><o:p></o:p></span></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">and Next takes us to next.Next() where the GraphStep is also empty
so we get to the EndStep, and AddRow adds the bindings to ers.explRows:<o:p></o:p></span></p><p class="MsoNormal" style="margin-bottom: 6.0pt; margin-left: 0cm; margin-right: 0cm; margin-top: 6.0pt; margin: 6pt 0cm; text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">AddRow(cx)
where cx.binding {[#41=WOODSCREW,#48=16/8x4]})<o:p></o:p></span></p><p class="MsoNormal">
<span lang="EN-US" style="font-family: "Times New Roman", serif;">Returning from AddRow brings us back to Step6,
where the bindings are cleared, to Step 4 where we call DbNode at Step 7, where the next value for </span><span lang="EN-US" style="font-family: Consolas;">dn
{TEdge 1024[774</span><span lang="EN-US" style="font-family: Consolas;">]} </span><span lang="EN-US" style="font-family: "Times New Roman", serif;">fails the test Qty>4, so backtracks and no
further rows get added.</span></p>
<table border="1">
<tbody><tr><th>T</th><th>X</th></tr>
<tr><td>WOODSCREW</td><td>16/8x4</td></tr>
</tbody></table>
<h3>Repeating Patterns</h3><div><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">For simplicity let us start with an empty database:<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b><span lang="EN-US" style="font-family: Consolas;">[CREATE (a:Person {name:'Fred
Smith'})<-[:Child]-(b:Person {name:'Peter Smith'}),<o:p></o:p></span></b></p>
<p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US" style="font-family: Consolas;">(b)-[:Child]->(:Person {name:'Mary
Smith'})]<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b><span lang="EN-US" style="font-family: Consolas;">MATCH (p)-[:Child]->(c) RETURN
p.name,c.name AS child<o:p></o:p></span></b></p>
<p class="MsoNormal" style="text-align: justify;"><span lang="EN-US"><span style="font-family: courier;">123456789012345678901234567890123456789012345678901234567890123456</span></span><br /><span style="font-family: courier;"><b>MATCH ({name:'Peter Smith'}
[()-[:Child]->()]+ (x) RETURN x.name</b></span></p></div><span style="font-family: Consolas;"><o:p></o:p></span><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">The + is shorthand for {1,*} . The pattern must be overall like a
complicated edge and therefore must start and end with a node, but these need
not be empty: any requirements apply to the repeat and to the preceding and
following nodes.<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Tracing the steps as before (and watching also for calls on PathNode):<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 1: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Exp[#8,%1,#50],Graph[],End[%7]},
Null, null)<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> xn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{SqlNode LBRACE
#8 .. {#9=#14}}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{[112,
{{(47=1,87=Fred Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify; text-indent: 36.0pt;"><span lang="EN-US" style="font-family: Consolas;">{[139, {{(47=2,87=Peter Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify; text-indent: 36.0pt;"><span lang="EN-US" style="font-family: Consolas;">{[346, {{(193=1,236=2,290=1)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify; text-indent: 36.0pt;"><span lang="EN-US" style="font-family: Consolas;">{[372, {{(47=3,87=Mary Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify; text-indent: 36.0pt;"><span lang="EN-US" style="font-family: Consolas;">{[399, {{(193=2,236=2,290=3)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 2: DbNode ({</span><span lang="EN-US" style="font-family: Consolas;">Node#8:[112,139,346,372,399],Exp[%1,#50],Graph[],End[%7]}</span><span lang="EN-US" style="font-family: Consolas;">,Null,null)<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">
dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 112[23]} backtrack (on
CheckProps)<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 3: DbNode(..)<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">
dn<- {TNode 139[23]} <o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 4: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{Exp[%1,#50],Graph[],End[%7]} null {TNode
139[23]}<o:p></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span lang="EN-US" style="font-family: Consolas;">Step 5: PathNode
({Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 139[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 6: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{Exp[#35,#45],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},Null,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 139[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<-{SqlEdge #35 CHILD}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{[346, {{(193=1,236=2,290=1)}}]}<o:p></o:p></span></p><p class="MsoNormal" style="text-indent: 36.0pt;"><span lang="EN-US" style="font-family: Consolas;">{[399, {{(193=2,236=2,290=3)}}]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 7: DbNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">({Node#35:[346,399],Exp[#45],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},
ARROWBASE, {TNode 139[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<-{TEdge 346[166]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 8: ExpNode ({</span><span lang="EN-US" style="font-family: Consolas;">Exp[#45],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]}</span><span lang="EN-US" style="font-family: Consolas;">,ARROWBASE,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 346[166]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<- {SqlNode RPAREN #45 }<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{[112, {{(47=1,87=Fred Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 9: DbNode({Node#45:[112],Exp[],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},ARROWBASE,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 346[166]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<- {TNode 110[23]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 10: PathNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Path1[#32,#35,#45],Exp[#50],Graph[],End[%7]},</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 112[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ot<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{(%0,(0=(0=TNode 139[23],1=TEdge 346[166],2=TNode
112[23])))}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 11: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Exp[#35,#45],Path1[#32,#35,#45],Exp[#50],Graph[],End[%7]},Null,
{TNode 112[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<-{SqlEdge COLON #35 166 CHILD ..}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-{} back to step 10<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 12: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Exp[#50],Graph[],End[%7]},WITH,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 112[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<-{SqlNode X #50 -510 NODETYPE rows 0 From:%8 Id=#50 Id X,#50 X}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{#50, {{(47=1,87=Fred Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 13: DbNode({Node#50:[112],Exp[],Graph[],End[%7]},
WITH,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode
112[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 112[23]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> <span style="background: yellow; mso-highlight: yellow;">AddRow({(#50=TNode 112[23])}</span> back to Step 9 back to step 7<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 14: DbNode({Node#35:[346,399],Exp[#45],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},
ARROWBASE,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 139[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 399[166]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 15: ExpNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Exp[#45],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},ARROWBASE,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 399[166]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<-{SqlNode RPAREN #45 }<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{[372, {{(47=3,87=Mary Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 16: DbNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Node#45:[372],Exp[],Path0[#32,#35,#45],Exp[#50],Graph[],End[%7]},
ARROWBASE,</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 399[166]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<-{TNode 372[23]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 17: PathNode</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">(</span><span lang="EN-US" style="font-family: Consolas;">{Path1[#32,#35,#45],Exp[#50],Graph[],End[%7]},</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 372[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 18: ExpNode
({Exp[#35,#45],Path1[#32,#35,#45],Exp[#50],Graph[],End[%7]}, Null, {TNode 372[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<- {SqlEdge COLON #35 166 CHILD ..}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-{} back to step 17<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 19: ExpNode({Exp[#50],Graph[],End[%7]},WITH,
{TNode 372[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> xn<-{SqlNode X #50 -510 NODETYPE rows 0 From:%8 Id=#50 Id X,#50 X}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> ds<-{[#50, {{(47=3,87=Mary Smith)}}]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 19: DbNode({Node#50:[372],Exp[],Graph[],End[%7]},
WITH, {TNode 372[23]})<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 372[23]}<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;"> <span style="background: yellow; mso-highlight: yellow;">AddRow({(#50=TNode 372[23])}</span> back to step 20 back to step 16
back to step 14 back to step 5 back to step 3 <o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 21: dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TEdge 346[166]}
backtrack<o:p></o:p></span></p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 22: dn<-</span><span lang="EN-US"> </span><span lang="EN-US" style="font-family: Consolas;">{TNode 372[23]}
backtrack<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">
</p><p class="MsoNormal"><span lang="EN-US" style="font-family: Consolas;">Step 23: dn<- {TEdge
399[166]} backtrack back to step 1<span style="font-size: 8pt;"><o:p></o:p></span></span></p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEjljjTOF9pXLt3vvxhb49KxhZbXZ9XhSrOVmck9E0rjWACTfPQbc-fmwjlNnGVkqwxmYuSw7Ogdak9OKEa71thYkh4q6psDtYW-pxCELo7DXwXYJxY3_VIE1t4Sdaqexz1kUOnSNZ3fXfNooBXUzviim4xu5u_Ce7evPphs8KGiSbwV6iHCiax4gK8QKMj2" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="170" data-original-width="686" height="114" src="https://blogger.googleusercontent.com/img/a/AVvXsEjljjTOF9pXLt3vvxhb49KxhZbXZ9XhSrOVmck9E0rjWACTfPQbc-fmwjlNnGVkqwxmYuSw7Ogdak9OKEa71thYkh4q6psDtYW-pxCELo7DXwXYJxY3_VIE1t4Sdaqexz1kUOnSNZ3fXfNooBXUzviim4xu5u_Ce7evPphs8KGiSbwV6iHCiax4gK8QKMj2=w460-h114" width="460" /></a></div><br /><h3>References</h3>
<p>F. Laux and M. Crowe, “Information Integration using
the Typed Graph Model”, DBKDA 2021: The Thirteenth International Conference on
Advances in Databases, Knowledge, and Data Applications, IARIA, May 2021, pp.
7-14, ISSN: 2308-4332, ISBN: 978-1-61208-857-0</p>
<p>N. Francis, A. Gheerbrant, P. Guagliardo, L. Leonid, V. Marsault, et al.. A
Researcher’s Digest of GQL. 26th International Conference on Database Theory
(ICDT 2023), Mar 2023, Ioannina, Greece. doi:10.4230/LIPIcs.ICDT.2023.1.
https://hal.science/hal-04094449 </p>
<p>M. Crowe, PyrrhoV7alpha, https://github.com/MalcolmCrowe/ShareableDataStructures </p><p></p><p></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-78484015884148399572022-04-21T11:32:00.002-07:002022-06-16T23:48:24.009-07:00PyrrhoV7alpha is on GitHub again<p> As of today 21 April 2022, the version of PyrrhoDBMS that I have been working on since 2019 is available on GitHub once again. It is still alpha code, but has a number of features of interest which this article will briefly review. Go to <a>https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha</a> .</p><p>All textbooks on Relational Databases emphasise the imprtance of having serializable transactions, to preserve correctness in a live database. They explain the two main ways of achieving this are "pessimistic" control using two-phase locking and "optimistic" control where transactions are subject to a validation stage during commit. Both methods are stated as being over complex, so that all of the same textbooks immediately settle for something much weaker that serialzable transactions. Furthermore, the discussion of what serialisability means for business operations is based on schedules, where likely areas of conflict are considered and avoidance strategies planned.</p><p>The international standard for the database language SQL, and all commercial database products, offer a range of "isiolation levels" which can be specified for transaction control: and generally users settle for the REPEATABLE_READ level. If SERIALIZABLE is selected, many operations are prevented with an error message along the lines that serializable transactions cannot be guaranteed.</p><p>For years now, I have argued for an alternative strategy, based on the "optimistic" approach, but incorprating a full transaction log of every committed operation on the database. In fact, in a strong sense, the transaction log is the database: it is the only thing persisted on disk, and consists of a sequence of non-overlapping transaction records. All versions of Pyrrho have used this approach, which guarantees from the outset that the committed transactions were indeed serialisable, and the serialisation used is the one in the transaction log. When the server is running, all of the live data is in memory. This architecture is suited for many business databases where data (customers, accounts etc) accumulates, and less useful for use cases such as messaging hubs where data is not kept for long.</p><p>In 2019 I demonstrated with a simple DBMS called Strong (StrongDBMS) that such an approach could outperform commercial database products in situations of high concurrency and conflicting transactions. The code for this DBMS is available in the above github repository. </p><p>However, there were two important points in the demonstration: first, that full safety requires a style of programming based on immutable shareable data structures, and second, that my own PyrhhoDBMS was unable to commit even as many transactions as the competition, in an admittedly challenging test. Since that date I have been working to apply the approach of shareable data structures to the PyrrhoDBMS, so that it too can outperform the traditional two-phase locking products. The alpha code is now available for this version 7 of PyrrhoDBMS, and it will be presented at DBKDA 2022.</p><p>For the changes in programming techniques that are required, see previous posts in this blog. Just as strings are immutable in Java and C#, database objects such as rowsets and cursors are immutable and shareable. Queries are parsed to construct the implementing rowsets, which when traversed will use the current versions of the (immutable) base tables. The radical nature of the change in programming style can be seen in how structures are shared but never copied or cloned; taking a snapshot is simply recording the current root node, as each version has a different root node, while sharing nearly all the rest of the nodes in the structure. The server's list of database root nodes (1 per database) is briefly locked to install a new database root. Writing of data to the disk is the result of a successful commit (append storage): nothing on disk is ever overwritten.</p><p>PyrrhoV7alpha includes a set of tests that demonstrate stored procedures, constraints and triggers, user defined types and view-mediated virtual data warehousing.</p><p><br /></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-46176865115092982272021-09-23T00:45:00.004-07:002022-01-14T11:04:17.320-08:00Implementation: instancing and framing<h3 style="text-align: left;"><i>(Updated: 14th January 2022: Implementation continues)</i></h3><h3 style="text-align: left;">Tables and table references</h3><p>During traversal of a rowset, the value associated with a column name changes from one row to the next. This is managed in database implementations using the notion of cursor. A cursor is a row value with the additional capabilities of being able to advance to contain the values for the next row or step back to the previous row. </p><p>Column names are local to a table, or more precisely to a table reference, since a table and its columns may be referenced more than once in an SQL statement, and the differenet references are then distinguished using aliases. Different references to the same table thus have different properties, and may be subject to different where-conditions etc.</p><p>To manage this, it is useful to have a process of instancing, so that the shared table remains immutable, while its instance are placed in transient local storage (a heap). Thus the instance and its columns will be referenced using heap uids instead of names or defining positions.</p><p>Each table reference thus has its own instance on the heap, and instances for its columns. At the end of execuition of the current SQL statement, the heap can be forgotten.</p><h3 style="text-align: left;">Compiled database objects</h3><p>In standard SQL, s<span style="font-family: "Times New Roman", serif;">everal database object types (e.g. Procedure,
Check, Trigger, View) define executable code. It is an ambition of Pyrrho V7 to compile such code once only: on database load, or on definition of a new compiled object. The compilation process creates many subsidiary objects (variable declarations, expressions, executable statements) in memory. These objects are then immutable and only replaced if the database object is altered (ALTER VIEW etc). In the next iteration (V7) of Pyrrho, these subsidiary objects have temporary uids and are stored in a field of the compiled object called framing.</span></p><p><span style="font-family: Times New Roman, serif;">When the compiled object is referenced during execution of an SQL statement, the objects in the framing need to be copied to the top of the heap. However, for efficiency reasons, even such a simple step whould be carried out as few times as possible. Procedure code can be brought into the context just once when required. Trigger code, and constraints for columns and domains should be brought in to the context before rowset traversal begins.</span></p><p><span style="font-family: Times New Roman, serif;">When views are used in a query, view references need to be instanced in the same way as table references, so that an instance must be created for each reference, so that it can be equipped with where-conditions, grouping specifications etc.</span></p><h3 style="text-align: left;"><span style="font-family: Times New Roman, serif;">Prepared Statements</span></h3><p><span style="font-family: Times New Roman, serif;">Prepared statements are local to a connection, and have query parameters, and can be handled in much the same way as compiled statements. An instance of a prepared statement has the formal paramneters replaced with actual values before execution begins,</span></p><p><span style="font-family: Times New Roman, serif;">The storage used for prepared statements in shared with successive transactions on the connection, and does not need to be saved in the database.</span></p><p><span style="font-family: Times New Roman, serif;"><br /></span></p><p><span style="font-family: Times New Roman, serif;"><br /></span></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-83898986783067098432021-09-03T09:09:00.006-07:002021-09-03T09:17:42.129-07:00Implementing Shareable Data Structures<p> The concept of shareable data structures first appeared in this blog in 2018, and there has been a software <a href="https://github.com/MalcolmCrowe/ShareableDataStructures" target="_blank">repository</a> in Github since that time. Several demonstration programs and PyrrhoV7alpha source code can also be found there. In the nature of things, the concept has evolved.</p><p>The use of shareable data structures in fundamental to the implementation of Pyrrho V7. The following documentation is based on part of a tutorial given by me and Fritz Laux at DBKDA 2021.</p><p style="text-align: left;"><span style="text-align: justify;">These have a recursive definition: </span><i style="text-align: justify;">a data structure is shareable iff it is immutable, and all fields are in turn shareable.</i><span style="text-align: justify;"> In all programming languages, values of primitive data types are shareable. In Hava, Pythone and C#, strings are also shareable. Unfortunately, in any programming language that allows data structures to have have subclasses, other than declaring a class sealed or final. there is no way of preventing a subclass from adding a mutable field. If we want to ensure our data structures are shareable, we need to declare them as internal to our project. Then at least we control what subclasses exist.</span></p><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">In a programming language based on
references, such as Java, or C#, we can make all fields in our structure </span><span face="Calibri, sans-serif" lang="EN-US">final</span><span lang="EN-US">, or </span><span face="Calibri, sans-serif" lang="EN-US">readonly</span><span lang="EN-US">. Then any reference can be safely shared,
and all fields might as well be public (unless there are confidentiality
issues). <o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">If all of the fields are, in turn, also
known to be immutable, then there is no need to clone or copy fields: copying a
pointer to the structure itself gives read-only access to the whole thing. <o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">For example, if the Database class is
shareable, and b is a database, then a:=b is a shareable copy of the whole
database (we have just copied a single 64-bit pointer). Such an assignment (or
snapshot) is also guaranteed to be thread-safe. <o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Pointers to shareable structures are never
updated but can be replaced when we have a new version to reference. If this
new version has some changed fields, it is perfectly fine to continue to use
the same pointers for all the unchanged fields<o:p></o:p></span></p><h3 style="text-align: left;">Shareable tree structures: adding a node</h3><p></p><p></p><p class="MsoNormal">When
we add a field located deep in a shareable structure (e.g. a node to a
shareable tree structure), we will need to construct a single new node at each
level back to the top of the structure. But the magic is that all the other
nodes remain shared between the old and new versions.<span style="font-size: 10pt;"><o:p></o:p></span></p><br /><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjz4nDbSfg_WbN7prA6nUPuH9Zt9BlHVz3sdxImYdBSSZ1jEq97Cr3qadbBQYuXlPkf5-huJBx5sFUPqZFoUHLWnXIbN4ICJ2wlh_fVMp5a52a5ovgwA7IB20Gl2-Sgu3Kt4oJFpXQBHo5q/s866/ShareableTree.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="773" data-original-width="866" height="286" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjz4nDbSfg_WbN7prA6nUPuH9Zt9BlHVz3sdxImYdBSSZ1jEq97Cr3qadbBQYuXlPkf5-huJBx5sFUPqZFoUHLWnXIbN4ICJ2wlh_fVMp5a52a5ovgwA7IB20Gl2-Sgu3Kt4oJFpXQBHo5q/s320/ShareableTree.png" width="320" /></a></div>The above picture (from Krijnen and Mertens, Mathematics Centre, Amsterdam, 1987) shows a tree with 7 leaves (that is, a tree of size 7), and updating (that is, replacing) one leaf node has resulted in just 2 new inner nodes being added to the tree. This makes shareable B-Trees into extremely efficient storage structures.<p></p><div><p class="MsoNormal" style="margin-top: 6pt;">In tests, (such as DictDemo, in the github repository) we see that for a suitable minimum number of
child nodes in the B-Tree, the number of new nodes required for a single update
to a B-Tree of size N is O(logN), and experimentally, this means that for each
tenfold increase in N, the number of new nodes per operation roughly doubles.<o:p></o:p></p>
<p class="MsoNormal" style="margin-top: 6pt;">Note that we also get a new root node every time (this
avoids wearing out flash memory).<span style="font-size: 10pt;"><o:p></o:p></span></p><h3 style="text-align: left;"><span lang="EN-US"><span style="font-family: inherit;">The choice of programming language</span></span></h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">It is helpful if the
programming language supports:<o:p></o:p></p><p class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"></p><ul><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span><!--[endif]-->readonly
directives (Java has final)</li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Generics (Java
has these)</li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Customizing
operators such as += (not Java)</li></ul><!--[if !supportLists]--><o:p></o:p><p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="margin-left: 72pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Because a+=b is
safer than Add(a,b)<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="margin-left: 72pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Easy to forget to
use the return value a=Add(a,b)<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"></p><ul><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Implies strong
static typing (so not Java)</li></ul><!--[if !supportLists]--><o:p></o:p><p></p><p class="MsoListParagraphCxSpMiddle" style="margin-left: 72pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Many languages
have “type erasure” <o:p></o:p></p><p class="MsoListParagraphCxSpLast" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"></p><ul><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span><!--[endif]-->Also useful to
have all references nullable</li></ul><!--[if !supportLists]--><o:p></o:p><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">So I prefer C#, which now has
been around for 19 years. Java and Python have been with us for over 30
years. <o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt;">
</p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">However, as mentioned above, C# provides no syntax
for requiring a class to be shareable: specifically, there is no way of
requiring a subclass of a shareable class to be shareable. It will cease to be
shareable if it has even one mutable field.<o:p></o:p></p><h3 style="margin-top: 6pt; text-align: justify;">Shareable database objects</h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">What data structures in the
DBMS can be made shareable?<o:p></o:p></p><p class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"></p><ul><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Database itself,
and its subclass, Transaction.</li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Database Objects
such as Table, Index, TableColumn, Procedure, Domain, Trigger, Check, View,
Role</li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Processing
objects such as Query, Executable, RowSet, and their many subclasses; </li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Cursor and most
of its subclasses.</li><li><span style="font-family: Symbol;"><span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>TypedValue and
all its subclasses</li></ul><!--[if !supportLists]--><o:p></o:p><p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpLast" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18pt;"><o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">All of these can be made
shareable. But many things cannot be made shareable:<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">Context and Activation cannot
be made shareable because in processing expressions we so often have
intermediate values. <o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">Also, something needs to
access system non-shareable structures such as FileStreams, HttpRequest.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">
</p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">And Physical and its
subclasses are used for preparing objects for the database file, so cursors
that examine logs are not shareable.<span style="font-size: 10pt;"><o:p></o:p></span></p><h3 style="margin-top: 6pt; text-align: justify;">An implementation library: first steps</h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">A fundamental building block
in many DBMS implementation is the B-tree. In Pyrrho BTree<K,V> is a sort
of unbalanced B-tree. It has a += operator to add a (key,value) pair, and a -=
operator to remove a key.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">BList<V> is a
subscriptable subclass where K is int. It is much slower than BTree, because it
partially reindexes the list starting from 0 on insertion and deletion.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">Both of these structures can
be traversed up and down using shareable helper classes ABookmark<K,V>
and methods First(), Last(). The ABookmark class implements key(). value(),
Next() and Previous(). <o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">These classes and their
subclasses are used throughout the DBMS implementation. They are shareable
provided K and V are shareable. If the classes K and V are not themselves
shareable, for example if one or both is the <span face="Calibri, sans-serif">object </span>class,
a tree will be shareable provided all of its contents (the nodes actually
added) are shareable. At least, it is easy to ensure that all public
constructors only have shareable parameters.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">
</p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">For convenience, Pyrrho uses a
potentially non-shareable base class <b><span face="Calibri, sans-serif">Basis</span></b>, whose only field is a <b><span face="Calibri, sans-serif">BTree<long,object></span></b> called mem. It has an
abstract method New which can be used to implement the <b>+</b>= and -= as effectively
covariant operators on subclasses, and these can be used to change the
properties on a database (of course, by creating a new one).<span style="font-size: 10pt;"><o:p></o:p></span></p><h3 style="text-align: left;">DBObject and Database</h3></div><div><p class="MsoNormal" style="text-align: justify;"><b><span lang="EN-US">DBObject</span></b><span lang="EN-US"> is a subclass of </span><b><span face="Calibri, sans-serif" lang="EN-US">Basis</span></b><span lang="EN-US">, with a public readonly field called defpos, of type
long. The defpos (defining position) acts as a uid or unique identifier for
every object in the database. As described in section 2.3 below, the range of
values of long is divided into ranges for database objects depending on their
lifetime: committed objects have the same lifetime as the database (e.g., the
SQL delete statement can unlink one or more objects but they remain in the
log). There are many subclasses of </span><span face="Calibri, sans-serif" lang="EN-US">DBObject</span><span lang="EN-US">, described in this booklet.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><b><span face="Calibri, sans-serif" lang="EN-US">Database</span></b><span lang="EN-US"> is also a subclass of </span><b><span face="Calibri, sans-serif" lang="EN-US">Basis</span></b><span lang="EN-US">, and it uses the mem field with positive
uids to store all of database object it contains. (Entries in mem with negative
uids are used for propert ies of the database, as described in section 3.5.2.)
The Database class also has two static lists: databases, and dbfiles. The first
is the set of databases indexed by database name, and the second is a
corresponding this of </span><b><span face="Calibri, sans-serif" lang="EN-US">File</span></b><span lang="EN-US"> objects.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Then there is a method called Load() to
build the database from the transaction log file, and Commit() which writes
Physical record durably to the log.<span style="font-size: 10pt;"><o:p></o:p></span></span></p><h3 style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Transaction and B-Tree</span></h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"></span></p><p class="MsoNormal"><span lang="EN-US">We can use the
B-Tree concept to model how the transaction Commit process works. The Commit process was described in terms of transformations in the previous posting in this blog.<span style="font-size: 10pt;"><o:p></o:p></span></span></p><p class="MsoNormal"></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRQi1inGQo-g3vUau-1R58-YfaAwATw44QIYaDTw5qebWsOQVeXZHqQy6uBFeF1Ryywcm_LRbc2vVQq6uMLEbBNcjmoO0mlgPOMuInNtmCiY8Jfc4EgsIElyx0UgQbHhN690T6kc_Pz13f/s554/Transaction6.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="349" data-original-width="554" height="202" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRQi1inGQo-g3vUau-1R58-YfaAwATw44QIYaDTw5qebWsOQVeXZHqQy6uBFeF1Ryywcm_LRbc2vVQq6uMLEbBNcjmoO0mlgPOMuInNtmCiY8Jfc4EgsIElyx0UgQbHhN690T6kc_Pz13f/s320/Transaction6.png" width="320" /></a></div><p></p><p class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo1; text-indent: -18pt;"></p><ol style="text-align: left;"><li><span style="font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span><!--[endif]-->Suppose we have a
database in any starting state D0. </li><li>.<span style="font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span><!--[endif]-->If we start a
transaction T0 from this state, initially the T0 is a copy of D0 (i.e. equal
pointers).</li><li>.<span style="font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span><!--[endif]-->As T0 is modified
it becomes T1, which shares many nodes with D0, but not all.</li><li>.<span style="font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span><!--[endif]-->D0 also evolves
as some other transaction has committed, so D1 has a new root and some new
nodes.</li><li>.<span style="font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span><!--[endif]-->When T1 commits,
we get a new database D2 incorporating the latest versions of everything.</li></ol><!--[if !supportLists]--><o:p></o:p><p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-indent: -18pt;"><o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-indent: -18pt;"><o:p></o:p></p><p class="MsoNormal"><span lang="EN-US">
</span></p><br /></div>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-4708414726610567702021-09-02T14:10:00.006-07:002021-09-02T14:10:48.999-07:00Some Pyrrho V7 alpha documentation<p> At DBKDA2021 in May, I presented a <a href="https://youtu.be/t4h-zPBPtSw">tutorial</a> on the inner workings of Pyrrho V7. The PDF version, with the demonstrations, tiotalled 10MB, which was probably much too much. Material based on it will nevertheless be included in the introductory sections and appendices of the documentation "Introduction to the Source code of the PyrrhoDBMS" a version of which is available on my github site. The following extracts are from the very start of the tutorial, which went on to explain the use of shareable data structures and ended with a deep dive into remote updates using view-mediated web services. (All of this material will soon appear on the github site: email me at malcolm.crowe@uws.ac.uk if you are interested in getting it sooner.)</p><h3>ACID and Serializable Transactions</h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">Our starting point is that full isolation requires truly serializable transactions.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">All database textbooks begin by saying how important serializability and isolation are, but very quickly settle for something much less.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;">If we agree that ACID transactions are good, then:<o:p></o:p></p><p class="MsoListParagraphCxSpFirst" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>First, for atomicity and durability we should not write anything durable until (a) we are sure we wish to commit and (b) we are ready to write the whole transaction.<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Second: before we write anything durable, we should validate our commit against the current database.<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Third, for isolation, we should not allow any user to see transactions that have not yet been committed.<o:p></o:p></p><p class="MsoListParagraphCxSpLast" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Fourth, for durability, we should use durable media – preferably write-once append storage.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">From these observations, it seems clear that a database should record its durable transactions in a non-overlapping manner.<o:p></o:p></span></p><p class="MsoListParagraphCxSpFirst" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>If transactions in progress overlap in time, they cannot both commit if they conflict: and if they don’t conflict, it does not matter which one is recorded first.<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>The simplest order for writing is that of the transaction commit.<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>If we are writing some changes that we prepared earlier, the validation step must ensure that it depends on nothing that has changed in the meantime, so that our change can seem to date from the time it was committed rather than first considered.<o:p></o:p></p><p class="MsoListParagraphCxSpLast" style="text-align: justify; text-indent: -18pt;"><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;"> </span></span>Effectively we need to reorder overlapping transactions as we commit them.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">These few rules guarantee actual serialization of transactions for a single transaction log (sometimes called a single transaction master). It obviously does not matter where the transactions are coming from.<o:p></o:p></span></p><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">But if a transaction is trying to commit changes to more than one transaction log, things are very difficult (the notorious two-army problem). If messages between autonomous actors can get lost, then inconsistencies are inevitable. The best solution is to have a DBMS act as transaction master for every piece of data For safety any transaction should have at most one remote participant, and more complex transactions can be implemented as a sequence of such one-way dependency transactions. <span style="font-size: 10pt;"><o:p></o:p></span></span></p><h3 style="text-align: left;">The transaction log</h3><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">The first was about the transaction log. In
Pyrrho the transaction log defines the content of the database (it is the only
thing stored on disk).<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">In this demonstration, we will see how
every Transaction T consists of a set of elementary operations e<sub>1</sub>, e<sub>2</sub>,..
, e<sub>n</sub> .<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Each operation corresponds to a Physical
object written to the transaction log<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Committing this transaction applies the
sequence to the Database D.<span style="mso-spacerun: yes;"> </span>In reverse
mathematical notation</span></p><v:group coordorigin="19420" coordsize="31476,8279" id="Group_x0020_91" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQDvomTbxQAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI9Pa8JA
FMTvBb/D8oTemk2UlhqzikgtPYRCVRBvj+wzCWbfhuw2f759t1DocZiZ3zDZdjSN6KlztWUFSRSD
IC6srrlUcD4dnl5BOI+ssbFMCiZysN3MHjJMtR34i/qjL0WAsEtRQeV9m0rpiooMusi2xMG72c6g
D7Irpe5wCHDTyEUcv0iDNYeFClvaV1Tcj99GwfuAw26ZvPX5/bafrqfnz0uekFKP83G3BuFp9P/h
v/aHVrBK4PdL+AFy8wMAAP//AwBQSwECLQAUAAYACAAAACEA2+H2y+4AAACFAQAAEwAAAAAAAAAA
AAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQBa9CxbvwAAABUBAAAL
AAAAAAAAAAAAAAAAAB8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQDvomTbxQAAANsAAAAP
AAAAAAAAAAAAAAAAAAcCAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAMAAwC3AAAA+QIAAAAA
" o:spid="_x0000_s1030" style="height: 8279; left: 19420; position: absolute; width: 31477;"><v:shape fillcolor="#4472c4 [3204]" id="Flowchart_x003a__x0020_Direct_x0020_Access_x0020_Storage_x0020_93" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQANPwchwwAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI9BawIx
FITvhf6H8Aq9FM3aUtHVKKVQ7MFLV3/AY/PcLCYv2yS66783guBxmJlvmOV6cFacKcTWs4LJuABB
XHvdcqNgv/sZzUDEhKzReiYFF4qwXj0/LbHUvuc/OlepERnCsUQFJqWulDLWhhzGse+Is3fwwWHK
MjRSB+wz3Fn5XhRT6bDlvGCwo29D9bE6OQX9P58+rQ2zt8txUjVms41yqJV6fRm+FiASDekRvrd/
tYL5B9y+5B8gV1cAAAD//wMAUEsBAi0AFAAGAAgAAAAhANvh9svuAAAAhQEAABMAAAAAAAAAAAAA
AAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAWvQsW78AAAAVAQAACwAA
AAAAAAAAAAAAAAAfAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEADT8HIcMAAADbAAAADwAA
AAAAAAAAAAAAAAAHAgAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAADAAMAtwAAAPcCAAAAAA==
" o:spid="_x0000_s1032" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 8156; left: 23354; mso-wrap-style: square; position: absolute; top: 123; v-text-anchor: middle; visibility: visible; width: 9416;" type="#_x0000_t133">
<v:stroke joinstyle="miter">
<v:textbox>
<!--[if !mso]-->
<table cellpadding="0" cellspacing="0" style="width: 100%px;">
<tbody><tr>
<td><!--[endif]-->
<div>
<p align="center" class="MsoNormal" style="text-align: center;"><span face="Calibri, sans-serif" lang="EN-US" style="color: white;">e<sub><span style="mso-text-raise: -4.5pt; position: relative; top: 4.5pt;">1</span></sub><o:p></o:p></span></p>
</div>
<!--[if !mso]--></td>
</tr>
</tbody></table>
<!--[endif]--></v:textbox>
</v:stroke></v:shape><v:shape fillcolor="#4472c4 [3204]" id="Flowchart_x003a__x0020_Direct_x0020_Access_x0020_Storage_x0020_94" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQCC1p9VwwAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI9BawIx
FITvhf6H8Aq9FM1aWtHVKKVQ7MFLV3/AY/PcLCYv2yS66783guBxmJlvmOV6cFacKcTWs4LJuABB
XHvdcqNgv/sZzUDEhKzReiYFF4qwXj0/LbHUvuc/OlepERnCsUQFJqWulDLWhhzGse+Is3fwwWHK
MjRSB+wz3Fn5XhRT6bDlvGCwo29D9bE6OQX9P58+rQ2zt8txUjVms41yqJV6fRm+FiASDekRvrd/
tYL5B9y+5B8gV1cAAAD//wMAUEsBAi0AFAAGAAgAAAAhANvh9svuAAAAhQEAABMAAAAAAAAAAAAA
AAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAWvQsW78AAAAVAQAACwAA
AAAAAAAAAAAAAAAfAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAgtafVcMAAADbAAAADwAA
AAAAAAAAAAAAAAAHAgAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAADAAMAtwAAAPcCAAAAAA==
" o:spid="_x0000_s1033" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 8155; left: 28906; mso-wrap-style: square; position: absolute; v-text-anchor: middle; visibility: visible; width: 9416;" type="#_x0000_t133">
<v:stroke joinstyle="miter">
<v:textbox>
<!--[if !mso]-->
<table cellpadding="0" cellspacing="0" style="width: 100%px;">
<tbody><tr>
<td><!--[endif]-->
<div>
<p align="center" class="MsoNormal" style="text-align: center;"><span face="Calibri, sans-serif" lang="EN-US" style="color: white;">e<sub><span style="mso-text-raise: -4.5pt; position: relative; top: 4.5pt;">2</span></sub><o:p></o:p></span></p>
</div>
<!--[if !mso]--></td>
</tr>
</tbody></table>
<!--[endif]--></v:textbox>
</v:stroke></v:shape><v:shape fillcolor="#4472c4 [3204]" id="Flowchart_x003a__x0020_Direct_x0020_Access_x0020_Storage_x0020_95" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQDtmjrOwgAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI9BawIx
FITvBf9DeAUvpWYVFN0apRRKe/Di6g94bF43i8nLmkR3/feNIHgcZuYbZr0dnBVXCrH1rGA6KUAQ
11633Cg4Hr7flyBiQtZoPZOCG0XYbkYvayy173lP1yo1IkM4lqjApNSVUsbakMM48R1x9v58cJiy
DI3UAfsMd1bOimIhHbacFwx29GWoPlUXp6A/82VubVi+3U7TqjE/uyiHWqnx6/D5ASLRkJ7hR/tX
K1jN4f4l/wC5+QcAAP//AwBQSwECLQAUAAYACAAAACEA2+H2y+4AAACFAQAAEwAAAAAAAAAAAAAA
AAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQBa9CxbvwAAABUBAAALAAAA
AAAAAAAAAAAAAB8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQDtmjrOwgAAANsAAAAPAAAA
AAAAAAAAAAAAAAcCAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAMAAwC3AAAA9gIAAAAA
" o:spid="_x0000_s1034" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 8155; left: 35422; mso-wrap-style: square; position: absolute; v-text-anchor: middle; visibility: visible; width: 9416;" type="#_x0000_t133">
<v:stroke joinstyle="miter">
<v:textbox>
<!--[if !mso]-->
<table cellpadding="0" cellspacing="0" style="width: 100%px;">
<tbody><tr>
<td><!--[endif]-->
<div>
<p align="center" class="MsoNormal" style="text-align: center;"><span face="Calibri, sans-serif" lang="EN-US" style="color: white;">…<o:p></o:p></span></p>
</div>
<!--[if !mso]--></td>
</tr>
</tbody></table>
<!--[endif]--></v:textbox>
</v:stroke></v:shape><v:shape fillcolor="#4472c4 [3204]" id="Flowchart_x003a__x0020_Direct_x0020_Access_x0020_Storage_x0020_96" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQAdSKS5wwAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI/BasMw
EETvhf6D2EAuJZETaEgdK6EUQnropU4/YLE2lrG0ciUldv6+KhR6HGbmDVMdJmfFjULsPCtYLQsQ
xI3XHbcKvs7HxRZETMgarWdScKcIh/3jQ4Wl9iN/0q1OrcgQjiUqMCkNpZSxMeQwLv1AnL2LDw5T
lqGVOuCY4c7KdVFspMOO84LBgd4MNX19dQrGb74+Wxu2T/d+Vbfm9BHl1Cg1n02vOxCJpvQf/mu/
awUvG/j9kn+A3P8AAAD//wMAUEsBAi0AFAAGAAgAAAAhANvh9svuAAAAhQEAABMAAAAAAAAAAAAA
AAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAWvQsW78AAAAVAQAACwAA
AAAAAAAAAAAAAAAfAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAHUikucMAAADbAAAADwAA
AAAAAAAAAAAAAAAHAgAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAADAAMAtwAAAPcCAAAAAA==
" o:spid="_x0000_s1035" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 8155; left: 41481; mso-wrap-style: square; position: absolute; v-text-anchor: middle; visibility: visible; width: 9416;" type="#_x0000_t133">
<v:stroke joinstyle="miter">
<v:textbox>
<!--[if !mso]-->
<table cellpadding="0" cellspacing="0" style="width: 100%px;">
<tbody><tr>
<td><!--[endif]-->
<div>
<p align="center" class="MsoNormal" style="text-align: center;"><br /></p>
</div>
<!--[if !mso]--></td>
</tr>
</tbody></table>
<!--[endif]--></v:textbox>
</v:stroke></v:shape></v:group><v:shape coordsize="426309,333633" fillcolor="#4472c4 [3204]" id="Equals_x0020_97" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQBtKgmNxQAAANsAAAAPAAAAZHJzL2Rvd25yZXYueG1sRI/NbsIw
EITvlfoO1lbiBk5B5SdgUNWC6AlE4MBxFW+TqPE6xCa4b48rIfU4mplvNItVMLXoqHWVZQWvgwQE
cW51xYWC03HTn4JwHlljbZkU/JKD1fL5aYGptjc+UJf5QkQIuxQVlN43qZQuL8mgG9iGOHrftjXo
o2wLqVu8Rbip5TBJxtJgxXGhxIY+Ssp/sqtR8LkvdknYbd/O67DBmRxl3eVcKdV7Ce9zEJ6C/w8/
2l9awWwCf1/iD5DLOwAAAP//AwBQSwECLQAUAAYACAAAACEA2+H2y+4AAACFAQAAEwAAAAAAAAAA
AAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQBa9CxbvwAAABUBAAAL
AAAAAAAAAAAAAAAAAB8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQBtKgmNxQAAANsAAAAP
AAAAAAAAAAAAAAAAAAcCAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAMAAwC3AAAA+QIAAAAA
" o:spid="_x0000_s1036" path="m56507,68728r313295,l369802,147199r-313295,l56507,68728xm56507,186434r313295,l369802,264905r-313295,l56507,186434xe" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 3336; left: 12505; mso-wrap-style: square; position: absolute; top: 1977; v-text-anchor: middle; visibility: visible; width: 4263;">
<v:stroke joinstyle="miter">
<v:path arrowok="t" o:connectangles="0,0,0,0,0,0,0,0,0,0" o:connectlocs="56507,68728;369802,68728;369802,147199;56507,147199;56507,68728;56507,186434;369802,186434;369802,264905;56507,264905;56507,186434" o:connecttype="custom">
</v:path></v:stroke></v:shape><w:wrap type="square">
</w:wrap><span lang="EN-US">(D)T = (..((D)e<sub>1</sub>)e<sub>2</sub>)..)e<sub>n</sub><span style="font-size: 10pt;"><o:p></o:p></span></span><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"></span></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtBP1N345o4gymAvMYW5At3I-vxXLnFdupZRACsdHdaLxB1vqIZ6xNIFMamUXhMZxjtD20HjzOgl2_gG7kqOtIwaJ_abBB5OKhj6-5VhzJdEkTBDh3XHUZqLbbC809Z6D6ZQEpBTmgw_Kc/s1760/Transaction1.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="228" data-original-width="1760" height="41" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhtBP1N345o4gymAvMYW5At3I-vxXLnFdupZRACsdHdaLxB1vqIZ6xNIFMamUXhMZxjtD20HjzOgl2_gG7kqOtIwaJ_abBB5OKhj6-5VhzJdEkTBDh3XHUZqLbbC809Z6D6ZQEpBTmgw_Kc/s320/Transaction1.png" width="320" /></a></div><br /><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">If we think of a transaction commit as
comprising a set of elementary operations e, then the transaction log is best
implemented as a serialization of these events to the append storage. We can
think of these serialized packets as objects in the physical database. In an
object-oriented programming language, we naturally have a class of such
objects, and we call this class Physical. <o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">So, at the commit point of a transaction,
we have a list of these objects, and the commit has two effects (a) 7 appending
them to the storage, (b) modifying the database so that other users can see. We
can think of each of these elementary operations as a transformation on the
database, to be applied in the order they are written to the database (so the
ordering within each transaction is preserved).<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">And the transaction itself is the resulting
transformation of the database.<span style="font-size: 10pt;"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><v:group coordsize="53329,8279" o:gfxdata="UEsDBBQABgAIAAAAIQC75UiUBQEAAB4CAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbKSRvU7DMBSF
dyTewfKKEqcMCKEmHfgZgaE8wMW+SSwc27JvS/v23KTJgkoXFsu+P+c7Ol5vDoMTe0zZBl/LVVlJ
gV4HY31Xy4/tS3EvRSbwBlzwWMsjZrlprq/W22PELHjb51r2RPFBqax7HCCXIaLnThvSAMTP1KkI
+gs6VLdVdad08ISeCho1ZLN+whZ2jsTzgcsnJwldluLxNDiyagkxOquB2Knae/OLUsyEkjenmdzb
mG/YhlRnCWPnb8C898bRJGtQvEOiVxjYhtLOxs8AySiT4JuDystlVV4WPeM6tK3VaILeDZxIOSsu
ti/jidNGNZ3/J08yC1dNv9v8AAAA//8DAFBLAwQUAAYACAAAACEArTA/8cEAAAAyAQAACwAAAF9y
ZWxzLy5yZWxzhI/NCsIwEITvgu8Q9m7TehCRpr2I4FX0AdZk2wbbJGTj39ubi6AgeJtl2G9m6vYx
jeJGka13CqqiBEFOe2Ndr+B03C3WIDihMzh6RwqexNA281l9oBFTfuLBBhaZ4ljBkFLYSMl6oAm5
8IFcdjofJ0z5jL0MqC/Yk1yW5UrGTwY0X0yxNwri3lQgjs+Qk/+zfddZTVuvrxO59CNCmoj3vCwj
MfaUFOjRhrPHaN4Wv0VV5OYgm1p+LW1eAAAA//8DAFBLAwQUAAYACAAAACEAZMzzCwwFAABdLAAA
HwAAAGNsaXBib2FyZC9kcmF3aW5ncy9kcmF3aW5nMS54bWzsWl1y2zYQfu9M74DhuyP+iqImcqax
I7+0icdyDgBTkMQJCLIAbMt5yml6sJ6kC4CgKEWSpUSadqawZ2z+AMvFYnc/fFi8fbcsKXoiXBQV
G3nBG99DhOXVtGDzkff5fnwx8JCQmE0xrRgZeS9EeO8uf/3lLR7OOa4XRY5AAhNDPPIWUtbDXk/k
C1Ji8aaqCYN3s4qXWMItn/emHD+D5JL2Qt/v90pcMO9yJeoaS4weefEDomiVfyHTK8yesACRNB92
nzQ60vznJeMhe7rh9aS+5Urz/OPTLUfFdOSB5RguwURer3nRNIPb3kav+UrAcsZL1b6azdASZsAP
+2mWeOhl5IV+EvQHiZFHlhLl0CCJojCN4GM5tBiEaew3DfLFp1dE5IsP+4WAmkYduOioqC+VjjtG
noGPmKHf8OqxRnH0b5sAzAPW8Rs11oadZUFru8wPVZMdwxa1GfP3U51ldsBjWj3nC8zlEF0XnOQS
/ZbnRAg0kRXHc4KgqXUHJcf6gpUpGjfa8II1/e3MZ1GcpHbigySJ+2vK42HNhbwhVYnUxcibgW5X
Src/8JwRWeTX/LHU4YaffhfSqGL7aCtYbeRyoscul++r6YuywgP8Bz+HRCE/wR8leuTltKg9tKj4
181nXNKriuqYwCyHFtBYcmMJKuREvlCizaI/AzZAmM4h/7SNdGxxeE6xSkSEXXyeQCL6CgEy8MEG
XwhX6QqyiB6QqGgxHReUKl0Fnz9cUVAWgwZj/dMYaq0Zmc1gvowh8JBgJF9qMsM5RPB9URKBPpJn
dFeVmHmoxqwS8MIP4bfvR37iQ9zBdeTH8LaQ+WKMy4KC0wUQDMojBIEpsB4oziYcfBfMpIYtL6+V
J0s9k8Z+6vFhRkQPWBBaqAx/ESa+M2vHrP6GWQmb3mKO77reefO+8U7rkeveRbEs2Nl84KzeCy61
GrD2LYhZ5WdtbngUZFLfQSyZjGKTh1BBrjyQsjsyA4gE8ApNtKoFAmlDFEPGZDIwrxZ4SkzkKi/U
8QMf00sK1UN/WgtUkmcQ8a3sRsB22Ua1pr3qauan7dykkX2d2x76yxWTbeeyYBXfNjIKo2q+bNpr
9RvDqGHp9LcbZwKV6gyyvgo0qq1OqbAiOQJpgkGW+oNI42UQRonGFDBPs1AI/DgNw7RBTAc6DnQa
h3agc/qFAmSE1qwOdFqUdaADSHNq0HmN0wU+0KQuqVMPLL7cGPpqoG2NFGqxZj26QWnCJB30+2GX
mFmQCdMkjkLgVA2lbWgZkGtLabd0XpHZHd0hmraR2X1oC9odjLaaOWr+fwTadsexBW2zOEgGoIS2
gwNbB7abYHu/QUVgPewY3o+x8i7YBhtmXRGe1f6DY3iO4UGwtUzUkNSfZ3hAvQ7GnNW+6hGYEwVR
NMj624DX4Y3bUfxuu7KbGB3enGwXuGvW0OGN3UJ15O4M5G4fx4F6xcF4E7eM7xi8SQdJotjjqgJn
iZ7DG4c3e/Hm729/udToUmOnPHPqfa99qRFOXRycGu2hi6OKLXGUBbEPG10uNR5Yl1bTv1a1/98W
991S/CxLcebwxuHN2fAGSF9baNmHPLA7Y5Dnw5+PmAoU+E0d/shiPhzdsUvvIEuhsG8W8Hb9HYf9
SMGPqi9EUdSP9IYSKGlrNfY0WHOCDM5tLrRG+nDDf+zU2I5NWlOUcmdU4HTMyc6orNy4t3GwVtP3
5iCwOr3bvb/8BwAA//8DAFBLAwQUAAYACAAAACEAkn2H4B0HAABJIAAAGgAAAGNsaXBib2FyZC90
aGVtZS90aGVtZTEueG1s7FlLbxs3EL4X6H9Y7L2xZL1iI3JgyXLcxC9ESoocKYnaZcxdLkjKjm5F
cuqlQIG06KEBeuuhKBqgARr00h9jwEGb/ogOuS9SouIHXCAobAHG7uw3w+HM7Mzs8M7dZxH1jjEX
hMVtv3qr4ns4HrExiYO2/2iw/dlt3xMSxWNEWYzb/gwL/+7Gp5/cQesjSpIhQ3w8CHGEPRAUi3XU
9kMpk/WVFTECMhK3WIJjeDZhPEISbnmwMuboBBaI6MpqpdJciRCJ/Q2QKJWgHoV/sRSKMKK8r8Rg
L0YRrH4wmZAR1tjxUVUhxEx0KfeOEW37IHPMTgb4mfQ9ioSEB22/ov/8lY07K2g9Y6JyCa/Bt63/
Mr6MYXy0qtfkwbBYtF5v1JubhXwNoHIR12v1mr1mIU8D0GgEO011sWW2Vrv1DGuA0kuH7K3WVq1q
4Q35tQWdNxvqZ+E1KJVfX8Bvb3fBihZeg1J8YwHf6Kx1tmz5GpTimwv4VmVzq96y5GtQSEl8tICu
NJq1br7bAjJhdMcJX2vUt1urmfASBdFQRJdaYsJiuSzWIvSU8W0AKCBFksSenCV4gkYQk11EyZAT
b5cEIQRegmImgFxZrWxXavBf/er6SnsUrWNkcCu9QBOxQFL6eGLESSLb/n2Q6huQs7dvT5+/OX3+
++mLF6fPf83W1qIsvh0UBybf+5+++efVl97fv/34/uW36dLzeGHi3/3y1bs//vyQeNhxaYqz716/
e/P67Puv//r5pUP6JkdDEz4gERbePj7xHrIINujQHw/55TgGISImx2YcCBQjtYpDfk+GFnp/hihy
4DrYtuNjDqnGBbw3fWop3A/5VBKHxAdhZAH3GKMdxp1WeKDWMsw8mMaBe3E+NXEPETp2rd1FseXl
3jSBHEtcIrshttQ8pCiWKMAxlp56xo4wduzuCSGWXffIiDPBJtJ7QrwOIk6TDMjQiqaSaYdE4JeZ
S0Hwt2Wbvcdeh1HXrrfwsY2EdwNRh/IDTC0z3kNTiSKXyAGKqGnwXSRDl5L9GR+ZuJ6Q4OkAU+b1
xlgIF88Bh/0aTn8Aacbt9j06i2wkl+TIJXMXMWYit9hRN0RR4sL2SRya2M/FEYQo8g6ZdMH3mP2G
qHvwA4qXuvsxwZa7z88GjyDDmiqVAaKeTLnDl/cws+K3P6MThF2pZpNHVord5MQZHZ1pYIX2LsYU
naAxxt6jzx0adFhi2bxU+n4IWWUHuwLrPrJjVd3HWGBPNzeLeXKXCCtk+zhgS/TZm80lnhmKI8SX
Sd4Hr5s270Gpi1wBcEBHRyZwn0C/B/HiNMqBABlGcC+Vehgiq4Cpe+GO1xm3/HeRdwzey6eWGhd4
L4EHX5oHErvJ80HbDBC1FigDZoCgy3ClW2Cx3F+yqOKq2aZOvon90pZugO7IanoiEp/bAc31Po3/
rveBDuPsh1eOl+16+h23YCtZXbLTWZZMdub6m2W4+a6my/iYfPxNzRaaxocY6shixrrpaW56Gv9/
39Mse59vOpll/cZNJ+NDh3HTyWTDlevpZMrmBfoaNfBIBz167BMtnfpMCKV9OaN4V+jBj4DvmfE2
EBWfnm7iYgqYhHCpyhwsYOECjjSPx5n8gsiwH6IEpkNVXwkJRCY6EF7CBAyNNNkpW+HpNNpj43TY
Wa2qwWZaWQWSJb3SKOgwqJIputkqB3iFeK1toAetuQKK9zJKGIvZStQcSrRyojKSHuuC0RxK6J1d
ixZrDi1uK/G5qxa0ANUKr8AHtwef6W2/UQcWYIJ5HDTnY+Wn1NW5d7Uzr9PTy4xpRQA02HkElJ5e
U7ou3Z7aXRpqF/C0pYQRbrYS2jK6wRMhfAZn0amoF1Hjsr5eK11qqadModeD0CrVaN3+kBZX9TXw
zecGGpuZgsbeSdtv1hoQMiOUtP0JDI3hMkogdoT65kI0gOOWkeTpC3+VzJJwIbeQCFOD66STZoOI
SMw9SqK2r7ZfuIHGOodo3aqrkBA+WuXWIK18bMqB020n48kEj6TpdoOiLJ3eQoZPc4XzqWa/Olhx
sim4ux+OT7whnfKHCEKs0aoqA46JgLODamrNMYHDsCKRlfE3V5iytGueRukYSumIJiHKKoqZzFO4
TuWFOvqusIFxl+0ZDGqYJCuEw0AVWNOoVjUtqkaqw9Kqez6TspyRNMuaaWUVVTXdWcxaIS8Dc7a8
WpE3tMpNDDnNrPBp6p5PuWt5rpvrE4oqAQYv7OeouhcoCIZq5WKWakrjxTSscnZGtWtHvsFzVLtI
kTCyfjMXO2e3okY4lwPilSo/8M1HLZAmeV+pLe062N5DiTcMqm0fDpdhOPgMruB42gfaqqKtKhpc
wZkzlIv0oLjtZxc5BZ6nlAJTyym1HFPPKfWc0sgpjZzSzClN39MnqnCKrw5TfS8/MIUalh2wZr2F
ffq/8S8AAAD//wMAUEsDBBQABgAIAAAAIQCcZkZBuwAAACQBAAAqAAAAY2xpcGJvYXJkL2RyYXdp
bmdzL19yZWxzL2RyYXdpbmcxLnhtbC5yZWxzhI/NCsIwEITvgu8Q9m7SehCRJr2I0KvUBwjJNi02
PyRR7Nsb6EVB8LIws+w3s037sjN5YkyTdxxqWgFBp7yenOFw6y+7I5CUpdNy9g45LJigFdtNc8VZ
5nKUxikkUigucRhzDifGkhrRykR9QFc2g49W5iKjYUGquzTI9lV1YPGTAeKLSTrNIXa6BtIvoST/
Z/thmBSevXpYdPlHBMulFxagjAYzB0pXZ501LV2BiYZ9/SbeAAAA//8DAFBLAQItABQABgAIAAAA
IQC75UiUBQEAAB4CAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0A
FAAGAAgAAAAhAK0wP/HBAAAAMgEAAAsAAAAAAAAAAAAAAAAANgEAAF9yZWxzLy5yZWxzUEsBAi0A
FAAGAAgAAAAhAGTM8wsMBQAAXSwAAB8AAAAAAAAAAAAAAAAAIAIAAGNsaXBib2FyZC9kcmF3aW5n
cy9kcmF3aW5nMS54bWxQSwECLQAUAAYACAAAACEAkn2H4B0HAABJIAAAGgAAAAAAAAAAAAAAAABp
BwAAY2xpcGJvYXJkL3RoZW1lL3RoZW1lMS54bWxQSwECLQAUAAYACAAAACEAnGZGQbsAAAAkAQAA
KgAAAAAAAAAAAAAAAAC+DgAAY2xpcGJvYXJkL2RyYXdpbmdzL19yZWxzL2RyYXdpbmcxLnhtbC5y
ZWxzUEsFBgAAAAAFAAUAZwEAAMEPAAAAAA==
" o:spid="_x0000_s1026" style="height: 65.15pt; left: 0px; margin-left: -9pt; margin-top: 26.05pt; position: absolute; text-align: left; width: 419.9pt; z-index: 251699200;"><v:group coordorigin="25786" coordsize="27543,8279" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQAkiD/HwwAAANwAAAAPAAAAZHJzL2Rvd25yZXYueG1sRE9Na8JA
EL0X/A/LCL01mygtEl1DECs9SKFGEG9DdkyC2dmQ3Sbx33cLhd7m8T5nk02mFQP1rrGsIIliEMSl
1Q1XCs7F+8sKhPPIGlvLpOBBDrLt7GmDqbYjf9Fw8pUIIexSVFB736VSurImgy6yHXHgbrY36APs
K6l7HEO4aeUijt+kwYZDQ40d7Woq76dvo+Aw4pgvk/1wvN92j2vx+nk5JqTU83zK1yA8Tf5f/Of+
0GF+nMDvM+ECuf0BAAD//wMAUEsBAi0AFAAGAAgAAAAhANvh9svuAAAAhQEAABMAAAAAAAAAAAAA
AAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAWvQsW78AAAAVAQAACwAA
AAAAAAAAAAAAAAAfAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAJIg/x8MAAADcAAAADwAA
AAAAAAAAAAAAAAAHAgAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAADAAMAtwAAAPcCAAAAAA==
" o:spid="_x0000_s1029" style="height: 8279; left: 25786; position: absolute; width: 27543;"><v:shape fillcolor="#4472c4 [3204]" id="Flowchart_x003a__x0020_Direct_x0020_Access_x0020_Storage_x0020_105" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQDZ5pvqwQAAANwAAAAPAAAAZHJzL2Rvd25yZXYueG1sRE9LasMw
EN0HcgcxgW5CI6eQYtzIIQRCu+imbg8wWFPLWBo5khI7t68Khe7m8b6zP8zOihuF2HtWsN0UIIhb
r3vuFHx9nh9LEDEha7SeScGdIhzq5WKPlfYTf9CtSZ3IIRwrVGBSGispY2vIYdz4kThz3z44TBmG
TuqAUw53Vj4VxbN02HNuMDjSyVA7NFenYLrwdWdtKNf3Ydt05vU9yrlV6mE1H19AJJrTv/jP/abz
/GIHv8/kC2T9AwAA//8DAFBLAQItABQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAAAAAAAAAAAAA
AAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAAAA
AAAAAAAAAAAAHwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhANnmm+rBAAAA3AAAAA8AAAAA
AAAAAAAAAAAABwIAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAAAwADALcAAAD1AgAAAAA=
" o:spid="_x0000_s1033" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 8155; left: 43914; mso-wrap-style: square; position: absolute; v-text-anchor: middle; visibility: visible; width: 9415;" type="#_x0000_t133"><br />
<v:stroke joinstyle="miter">
<v:textbox>
<!--[if !mso]-->
<!--[endif]--></v:textbox>
</v:stroke></v:shape></v:group><v:shape coordsize="426309,333633" fillcolor="#4472c4 [3204]" id="Equals_x0020_106" o:gfxdata="UEsDBBQABgAIAAAAIQDb4fbL7gAAAIUBAAATAAAAW0NvbnRlbnRfVHlwZXNdLnhtbHyQz07DMAyH
70i8Q+QralM4IITa7kDhCAiNB7ASt43WOlEcyvb2pNu4IODoPz9/n1xv9vOkForiPDdwXVagiI23
jocG3rdPxR0oScgWJ8/UwIEENu3lRb09BBKV0ywNjCmFe63FjDSjlD4Q50nv44wpl3HQAc0OB9I3
VXWrjedEnIq03oC27qjHjympx31un0wiTQLq4bS4shrAECZnMGVTvbD9QSnOhDInjzsyuiBXWQP0
r4R18jfgnHvJr4nOknrFmJ5xzhraRtHWf3Kkpfz/yGo5S+H73hkquyhdjr3R8m2lj09svwAAAP//
AwBQSwMEFAAGAAgAAAAhAFr0LFu/AAAAFQEAAAsAAABfcmVscy8ucmVsc2zPwWrDMAwG4Ptg72B0
X5TuUMaI01uh19I+gLGVxCy2jGSy9e1nemrHjpL4P0nD4SetZiPRyNnCruvBUPYcYp4tXC/Htw8w
Wl0ObuVMFm6kcBhfX4Yzra62kC6xqGlKVgtLreUTUf1CyWnHhXKbTCzJ1VbKjMX5LzcTvvf9HuXR
gPHJNKdgQU5hB+ZyK23zHztFL6w81c5zQp6m6P9TMfB3PtPWFCczVQtB9N4U2rp2HOA44NMz4y8A
AAD//wMAUEsDBBQABgAIAAAAIQDyMaIQwgAAANwAAAAPAAAAZHJzL2Rvd25yZXYueG1sRE9NawIx
EL0L/Q9hCt40qaViV6MUW6knxa0Hj8Nmurt0M9lu4pr++0YQvM3jfc5iFW0jeup87VjD01iBIC6c
qbnUcPzajGYgfEA22DgmDX/kYbV8GCwwM+7CB+rzUIoUwj5DDVUIbSalLyqy6MeuJU7ct+sshgS7
UpoOLyncNnKi1FRarDk1VNjSuqLiJz9bDe/7cqfi7vPl9BE3+Cqf8/73VGs9fIxvcxCBYriLb+6t
SfPVFK7PpAvk8h8AAP//AwBQSwECLQAUAAYACAAAACEA2+H2y+4AAACFAQAAEwAAAAAAAAAAAAAA
AAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQBa9CxbvwAAABUBAAALAAAA
AAAAAAAAAAAAAB8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQDyMaIQwgAAANwAAAAPAAAA
AAAAAAAAAAAAAAcCAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAMAAwC3AAAA9gIAAAAA
" o:spid="_x0000_s1034" path="m56507,68728r313295,l369802,147199r-313295,l56507,68728xm56507,186434r313295,l369802,264905r-313295,l56507,186434xe" strokecolor="#1f3763 [1604]" strokeweight="1pt" style="height: 3336; left: 12505; mso-wrap-style: square; position: absolute; top: 1977; v-text-anchor: middle; visibility: visible; width: 4263;">
<v:stroke joinstyle="miter">
<v:path arrowok="t" o:connectangles="0,0,0,0,0,0,0,0,0,0" o:connectlocs="56507,68728;369802,68728;369802,147199;56507,147199;56507,68728;56507,186434;369802,186434;369802,264905;56507,264905;56507,186434" o:connecttype="custom">
</v:path></v:stroke></v:shape><w:wrap type="square">
</w:wrap></v:group><span lang="EN-US">Every Database D is the
result of applying a sequence of transactions to the empty _system Database D0.<o:p style="font-size: 10pt;"></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1PZ8sFLELYm5zTEo3I9YoED32noFTDhpHu3eErv4UznOBHDXu8NiKtxmGxr6vVK_fhhykjiSr1lvSujYjY8eIRNFHP9-WJi-e0-a17xmr7SQikyk111K_VM3VD0sgSTXQ55T3jmrg1tbP/s1930/Transaction2.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="304" data-original-width="1930" height="50" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1PZ8sFLELYm5zTEo3I9YoED32noFTDhpHu3eErv4UznOBHDXu8NiKtxmGxr6vVK_fhhykjiSr1lvSujYjY8eIRNFHP9-WJi-e0-a17xmr7SQikyk111K_VM3VD0sgSTXQ55T3jmrg1tbP/s320/Transaction2.png" width="320" /></a></div><p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Any state of the database is thus the
result of the entire sequence of committed transactions, starting from a known
initial database state corresponding to an empty database. <o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">The sequence of transactions and their
operations is recorded in the log.<span style="font-size: 10pt;"><o:p></o:p></span></span></p><h3 style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Shareable data</span></h3><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Many programming languages (including Java,
Python and C#) currently have shareable implementations of strings. <o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">Specifically, strings in Java, Python and
C# are immutable: if you make a change, you get a new string, and anyone who
had a copy of the previous version sees no change. <o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">In these systems, it is illegal to modify a
string by assigning to a character position instead you need to use a library
function. <o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">The addition operator can be used in these
languages to create a sum of strings. This is basically the model for shareable
data structures. <o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US">For a class to be <i>shareable</i>, all
fields must be read-only and shareable. Constructors therefore need to perform
deep initialisation, and any change to an existing structure needs another
constructor. Inherited fields need to be initialised in the base (or super)
constructor, maybe with the help of a static method.<o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"><span lang="EN-US" style="font-family: "Times New Roman", serif;">This is useful for
databases because databases share so many things: predefined types, properties,
system tables. For example, all databases can share the same starting state, by
simply copying it from the _system database.
</span></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"><span lang="EN-US" style="font-family: "Times New Roman", serif;">Even more importantly all transactions can start
with the current state of the database, without cloning or separately copying
any internal structures. When a transaction starts, it starts with the shared
database state: as it adds physicals, it transforms. Different transactions
will in general start from different states of the shared database.</span></span></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"></span></p><div class="separator" style="clear: both; text-align: center;"><span lang="EN-US"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhS7D6eeO0lzfABtefJKV_hWNhEG4hnnA2VhROUEvPvrcmkFgsGrKohYKPV3WSx3dRCaTaP5vm_UO2VJlGjNCvrLrUUmCfUItJ1eZxUA8ybcDl7p0U25Nb6M5AFo16RN9-0wWjmBBjpgkfX/s1776/Transaction3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="617" data-original-width="1776" height="111" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhS7D6eeO0lzfABtefJKV_hWNhEG4hnnA2VhROUEvPvrcmkFgsGrKohYKPV3WSx3dRCaTaP5vm_UO2VJlGjNCvrLrUUmCfUItJ1eZxUA8ybcDl7p0U25Nb6M5AFo16RN9-0wWjmBBjpgkfX/s320/Transaction3.png" width="320" /></a></span></div><span lang="EN-US"><br /></span><p></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">In the above picture, we know
what the database DB’s state is. Each of concurrent transaction steps T1, T2,
and T3 are, if committed, will create a new version of DB (for example (DB)T2.)
Because of isolation, from the viewpoint of any of these transactions, they
cannot know whether DB has already been updates by another transaction (in
which case, they may no longer fit on the resulting database). In particular,
after T2 commits, T1 and/or T3 will possibly no longer be able to commit.<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"><span lang="EN-US" style="font-family: "Times New Roman", serif;">
</span></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">However, if T1 was able to
commit before, then it will still be able to commit provided it has no conflict
with T2’s changes.<o:p></o:p></p><h3 style="margin-top: 6.0pt; text-align: justify;">Transaction conflict</h3><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">The details of what
constitutes a conflicting transaction are debatable. Most experts would agree
with some version of the following rules: <o:p></o:p></p><p class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->T1 and T2 will
not conflict if they affect different tables or other database objects<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="margin-left: 72.0pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->And only read
from different tables<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->But we can allow
them to change different rows in the same table<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="margin-left: 72.0pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Provided they
read different specified rows<o:p></o:p></p><p class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: Symbol;">·<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Or even different
columns in the same row<o:p></o:p></p><p class="MsoListParagraphCxSpLast" style="margin-left: 72.0pt; mso-add-space: auto; mso-list: l0 level2 lfo1; text-align: justify; text-indent: -18.0pt;"><!--[if !supportLists]--><span style="font-family: "Courier New";">o<span style="font-family: "Times New Roman"; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal;">
</span></span><!--[endif]-->Provided they
read different columns<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">The first rule is sound
enough, although the condition on reading is very important: we would need to
include things like aggregation in our definition of reading. The first rule is
also very easy to implement, especially if tables are shareable structures, as
a simple 64-bit comparison is sufficient!<o:p></o:p></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">
</p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">For the other rules, we would
need to be very clear on what is meant by a “specified row”, and the
non-existence of a row might only be determined by reading the whole table. <span style="font-size: 10pt;"><o:p></o:p></span></p><h3 style="margin-top: 6.0pt; text-align: justify;">Transaction validation</h3><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">At the start of Transaction Commit, there is a validation check, to ensure that the transaction still fits on the current shared state of the database, that is, that we have no conflict with transaction that committed since our transaction started.</p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;">We will see that during commit of a Transaction T, we do a validation check. It ensures that the elementary operations of T can be validly relocated to follow those of any transaction T´ that has committed since the start of T . T planned</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkMWp06xvfa0LxJnbnPyfP55BFj-o9MOgP82gEskSWoGl7lKVJdBqSFa6c27SpcKYh8xBoA5J5pObI20lMCmlRi-3bXJbYClAAigyoSfe_oinHq8rkBUYzJ9ubYrd4BNP-upOO_eFwquug/s1275/Transaction4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="319" data-original-width="1275" height="80" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkMWp06xvfa0LxJnbnPyfP55BFj-o9MOgP82gEskSWoGl7lKVJdBqSFa6c27SpcKYh8xBoA5J5pObI20lMCmlRi-3bXJbYClAAigyoSfe_oinHq8rkBUYzJ9ubYrd4BNP-upOO_eFwquug/s320/Transaction4.png" width="320" /></a></div><br /><div style="text-align: justify;">But now we have</div><div style="text-align: justify;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHN7pEAUTvTXXgclxMZ60QO_7O6jGOU2lKQKEggPlckHHfdkE9ugsPSDqvIzJLtF0B_s7eB_g-9AK_Ozh3fPJrPvhD_1a03nfYGFQEHT18WHJ1wY5A_rwLf8vj02NyY1Ueq1PEqI0Re_DB/s1530/Transaction5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="304" data-original-width="1530" height="64" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHN7pEAUTvTXXgclxMZ60QO_7O6jGOU2lKQKEggPlckHHfdkE9ugsPSDqvIzJLtF0B_s7eB_g-9AK_Ozh3fPJrPvhD_1a03nfYGFQEHT18WHJ1wY5A_rwLf8vj02NyY1Ueq1PEqI0Re_DB/s320/Transaction5.png" width="320" /></a></div><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US">Relocation amounts to swapping the order of
the elementary operations e<sub>i</sub> that comprise transaction T and T’. Two
such cannot be swapped if they conflict. E.g. They change the same object
(write/write conflict). </span>The tests for write-write conflicts involve comparing our list of
physicals with those of the other transactions.<o:p></o:p></p>
<p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><span lang="EN-US">There are also tests for read/write
conflicts between T and T´. </span>For checking read-write conflicts, we collect “read constraints” when we
are making Cursors.<span style="font-size: 10pt;"><o:p></o:p></span></p><p class="MsoNormal" style="margin-top: 6.0pt; text-align: justify;"><br /></p><p class="MsoNormal" style="margin-top: 6pt; text-align: justify;"><span lang="EN-US"><span lang="EN-US" style="font-family: "Times New Roman", serif;"><br /></span></span></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-91041850468925365312021-07-01T12:59:00.132-07:002022-01-14T11:02:44.537-08:00RowSet Review and PyrrhoV7alpha<p>(Revised 14th Jamuary 2022)</p><p>The query processing stage of most relational DBMS deals with Query Optimisation, and computes a strategy for query evaluation taking account of available indexes and so on. This was an important aspect in previous versions of PyrrhoDBMS too.</p><p>In the current redevelopment of PyrrhoDBMS the hope is to domething more ambitious, taking account of the previous entries in this blog, on compile-once views, triggers etc (<a href="https://pyrrhodb.blogspot.com/2019/12/progress-with-pyrhho-v7-alpha-contd.html" target="_blank">3 December 2019</a>), modifiable rowsets (<a href="https://pyrrhodb.blogspot.com/2021/02/modifiable-rowsets.html" target="_blank">20 Feb 2021</a>) and lateral joins (<a href="https://pyrrhodb.blogspot.com/2020/07/lateral-derived-tables-and-pyrrho-v7.html" target="_blank">31 July 2020</a>). In this version the goal of parsing the SQL for CRUD operations is to construct RowSets. When such compiled objects are used there is often additional information such as filters, limiting snad skipping, and/or additional processing such as aggregation or ordering. Each RowSet produces a derived table, starting with one or more source rowsets, base tables or explicit value sets, which may in general have been computed using different (definer's) privileges.</p><p>Many such stages of traversal require intermediate rowsets to be built, for ordering, subqueries, distinct, grouping and window operations. Each such building operation provides an index whose properties can be used to oprimise the results of aggregations. Each join of a compiled rowset offers the opportunity to check for functional dependency between left and right operands. Each additional inequality where-condition raises the opportnity for truncating rowset traversal by means of an ad-hoc index. </p><p>Applying aggregation, ordering and filtering to the top-level RowSet all offer the opportunity to pass filters down to earlier stages of the evaluation, and/or use different indexes from those that seemed most suitable at compile time. In addition, RowSet Review can be applied during merges and joins, using the additional intermediate results information. The review process can benefit from cardinality information obtained during build. </p><p>And of course the Rowset Review process uses the fact that all of the RowSets are immutable, that that the process of review is non-destructive abd behaves like an evaluation stack.</p><p>All of this is a very different approach to rowset evaluation than was used in previous versions of Pyrrho, and will mean that the current alpha stage of Pyrrho redevelopment will extend further into the future. But I offer no apologies for this extension of the project, believing the the pointers it offers for future DBMS design might one day be of wider interest.</p><p>Some implementations (e.g. JPA) use the word Query for what we call a RowSet: it makes sense now to merge the two sets of classes in PyrrhoV7 and the syntax definitions are being updated to use syntax identifiers of form RowSetXX instead of QueryXX. I note that (a) the SQL standard calls the result of a SELECT a derived table, not a query, although it uses <query expression> etc in addition to "row set", like previous versions of Pyrrho, and (b) "Query optimisation" sounds as if it relates to a source-level rewriting of the SQL rather than an improved evaluation strategy, so that the term "RowSet review" captures the improvement mechanism rather better.</p><p>In the PyrrhoSvr code parsing of a select statement resulted in a Query structure for which a RowSet structure was later built. From now on, there is no separate Query class. The overall structure of a select statement is (very roughly) SELECT SelectList FROM TableExpression. The RowSet resulting from the parse cannot properly be constructed until the TableExpression has been parsed. But until that time, the SelectList has been defining the Domain of this |RowSet, replacing subexpressions as their references are resolved. This simplification brings several advantages to the implementation, as (a) a lot of DBObject reconstruction is avoided during parsing, and (b) it gets rid of ad hoc Domains. From now on, Domains are defined by syntax and start out with a lexical uid, and . Naturally, the SourceIntro document will be updated to explain this process.</p><p>The above new ideas will eventually see the light of day in the alpha code in the PyrrhoV7alpha folder at https://github.com/MalcolmCrowe/ShareableDataStructures</p><p><br /></p><p><br /></p><p><br /></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-16060341081954035742021-05-30T06:48:00.003-07:002021-05-30T07:06:18.747-07:00Benchmarking PyrrhoV7alpha<p> It is natural to wonder whether Pyrrho v7's unusual data structures and approach to transactions are practical. Since 2018 PyrrhoDB has been tested using a modified version of the <a href="http://tpc.org/TPC_Documents_Current_Versions/pdf/tpc-c_v5.11.0.pdf" target="_blank">TPC-C benchmark</a></p><p>The TPC-C benchmark simulates an OLTP system for ordering items by telephone from an e-business. The business operates a number of warehouses, with 30000 customers at each divided into 10 districts. There are 100000 items available. There are normal speed tests, e.g. what is the top speed for a sequence of transactions? Pyrrho's performance here on a PC is modest at 10 new-order transactions per second.</p><p>If the specification is followed more closely, there is one clerk per warehouse to deal with a mix of tasks including new order, payment, stock enquiry, and delivery. The clerk's behaviour is simulated so that tasks take a realistic amount of real time (e.g. 23 seconds for a new order with between 5 and 15 different items). The specification sets these out in great detail. For one warehouse no DBMS following the rules can complete more than 17 new orders in 10 minutes.</p><p>To provide greater challenge for the DBMS's transaction mechanism, Pyrrho sets the number of warehouses to 1, but increases the number of clerks for that warehouse to 50 to 100. Pyrrho always requires serialisable transactions, so after 10 clerks, the chances of transaction conflict rise sharply. All commercial DBMS have trouble with this test, and performance generally collapses well before 30 clerks. </p><p>With <a href="https://github.com/MalcolmCrowe/ShareableDataStructures" target="_blank">StrongDBMS</a> the throughput continued to increase to 100 clerks, when CPU resources became a problem. This link gives access not only to software for StrongDBMS's version of the test, but also versions for other DBMS we tried. The Pyrrhov7alpha folder in this repository contains the current alpha source code for PyrrhoV7, with the version of software used for the test described below.</p><p>We have <a href="http://www.thinkmind.org/index.php?view=article&articleid=dbkda_2020_1_50_50030" target="_blank">analysed</a> the reasons for Strong's unexpected performance, and it relates to the use of optimistic concurrency mechanisms. Pyrrho uses similar mechanisms but up to version 6.3 its results on this test were poor, leading to the development of PyrrhoV7, which seeks to learn lessons from StrongDBMS's implementation. A full account of this process was given in a <a href="https://www.iaria.org/conferences2021/ProgramDBKDA21.html" target="_blank">tutorial</a> at DBKDA 2021.</p><p>With PyrrhoV7 alpha, results with 50 clerks have always been <a href="https://youtu.be/0YaU59LvgLs" target="_blank">impressive</a>. At the current stage in development, however, Pyrrho's rowset review mechanism, still under development, does not yet carry out a good implementation of the TPCC StockLevel task, which is a relatively rare CPU-intensive task that conflicts with a great many ongoing transactions. Without this task, CPU and memory usage for server and clients remain low even at 100 clerks (1GB server memory, peak 6% CPU). Experimentally, peak throughput occurs with around 60 clerks.</p><p>The results below were obtained using the server version dated 30 May 2021.</p><p><table border="1" cellpadding="0" cellspacing="0" class="MsoTableGrid" style="border-collapse: collapse; border: none; mso-border-alt: solid windowtext .5pt; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-yfti-tbllook: 1184;">
<tbody><tr style="mso-yfti-firstrow: yes; mso-yfti-irow: 0;">
<td style="border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p align="center" class="MsoNormal" style="line-height: normal; margin-bottom: 0cm; text-align: center;"><b>Clerks<o:p></o:p></b></p>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p align="center" class="MsoNormal" style="line-height: normal; margin-bottom: 0cm; text-align: center;"><b>NewOrders Committed<o:p></o:p></b></p>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p align="center" class="MsoNormal" style="line-height: normal; margin-bottom: 0cm; text-align: center;"><b>Conflicts reported<o:p></o:p></b></p>
</td>
</tr>
<tr style="mso-yfti-irow: 1;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">1<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">17<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">0<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 2;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">2<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">29<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">15<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 3;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">5<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">62<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">74<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 4;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">10<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">91<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">254<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 5;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">20<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">108<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">678<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 6;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">50<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">135<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">2009<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 7;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">75<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">133<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">3088<o:p></o:p></p>
</td>
</tr>
<tr style="mso-yfti-irow: 8; mso-yfti-lastrow: yes;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 78.95pt;" valign="top" width="105">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">100<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 126.35pt;" valign="top" width="168">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">105<o:p></o:p></p>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 120.5pt;" valign="top" width="161">
<p class="MsoNormal" style="line-height: normal; margin-bottom: 0cm;">4089<o:p></o:p></p>
</td>
</tr>
</tbody></table></p><p>This page will be updated when the test includes the StockLevel task.</p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-86338976232104850862021-02-20T00:08:00.041-08:002021-04-12T09:19:58.132-07:00Modifiable rowsets<p>In V7 of Pyrrho I plan to have a more systematic approach to modifiable rowsets, which are useful in view-mediated data integration. Comments on the following proposals are welcome. Update: (12 April 2021) Working implementations of these ideas (alpha code) have now been posted to GitHub.</p><p>V7 uses immutable, shareable rowsets (all typed values are also immutable and shareable). Compiled objects including table-valued functions and views have precompiled rowsets that are instantiated when accessed. Such instantiations are merged into the surrounding context, so that Pyrrho uses rowset review where other DBMS (and previous versions of Pyrrho) use query optimisation.</p><p class="MsoNormal"><span style="font-family: inherit;">Some
rowsets can be used to make changes to their base tables, and this feature is
useful for views. As a rule of thumb this requires rowsets whose results expose
simple rows and columns, possibly with a monotonic invertible adapter function, and thus
all Yes entries in this table depend on this kind of additional requirement and the
need to satisfy constraints and authorisation requirements. Such an operation
adds to the transaction results a set of modifications for each of the individual
tables involved. There are no entries below for rowsets with 0 or 1 base tables:</span><span style="font-size: 10pt;"><o:p></o:p></span></p><table border="1" cellpadding="0" cellspacing="0" class="MsoNormalTable" style="border-collapse: collapse; border: none; mso-border-alt: solid windowtext .5pt; mso-border-insideh: .5pt solid windowtext; mso-border-insidev: .5pt solid windowtext; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-yfti-tbllook: 1184;">
<tbody><tr>
<td style="border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p align="center" class="MsoNormal" style="text-align: center;"><b><span style="font-family: inherit;">SubClass<o:p></o:p></span></b></p>
</td>
<td style="border-left: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p align="center" class="MsoNormal" style="text-align: center;"><b><span style="font-family: inherit;">Insert<o:p></o:p></span></b></p>
</td>
<td style="border-left: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p align="center" class="MsoNormal" style="text-align: center;"><b><span style="font-family: inherit;">Update<o:p></o:p></span></b></p>
</td>
<td style="border-left: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p align="center" class="MsoNormal" style="text-align: center;"><b><span style="font-family: inherit;">Delete<o:p></o:p></span></b></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">DistinctRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">DocArrayRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">EmptyRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">EvalRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">ExplicitRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">GroupingRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">IndexRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;">(Yes)</p></td><td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">(Yes)</td><td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">(Yes)</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">JoinRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">MergeRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Intersection only<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">OldTableRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">OrderedRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">RestRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr><tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">RoutineCallRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">RowSetSection<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">SelectRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;">See below</p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;">See below</p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;">Yes</p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">SelectedRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">Yes<o:p></o:p></span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">SqlRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">SystemRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">TableRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;">(Yes)</p></td><td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">(Yes)</td><td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">(Yes)</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">TransitionRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">TrivialRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">ValueRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;"> </span></p>
</td>
</tr>
<tr>
<td style="border-top: none; border: 1pt solid windowtext; mso-border-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 99.15pt;" valign="top" width="132">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">WindowRowSet<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<o:p></o:p></span></p>
</td>
<td style="border-bottom: 1pt solid windowtext; border-left: none; border-right: 1pt solid windowtext; border-top: none; mso-border-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt; width: 89.6pt;" valign="top" width="119">
<p class="MsoNormal" style="text-align: justify;"><span style="font-family: inherit;">No<span> </span><o:p></o:p></span></p>
</td>
</tr>
</tbody></table><p>
</p><p class="MsoNormal"><span style="font-family: inherit;"> It will be obvious in most cases what these RowSet classes are for. TransitionRowSet and OldTableRowSet are used in trigger implementation and are not directly accessible. A SelectRowSet has columns that are expressions, and only certain expressions are invertible to retrieve the underlying column values, while a SelectedRowSet picks and re-arranges columns from its source. RestRowSets are used in the implementation of RESTViews.</span></p><p class="MsoNormal"><span style="font-family: inherit;"><br /></span></p><p><br /></p><p><br /></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-14485726575337985442021-01-01T23:22:00.002-08:002021-04-12T09:16:15.967-07:00Progress with Pyrrho v7 alpha<p> See code <span style="background-color: white; color: #333333; font-family: georgia, serif; font-size: 13px;">on </span><a href="https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha" style="background-color: white; color: #999999; font-family: georgia, serif; font-size: 13px; text-decoration-line: none;">https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha</a></p><p>Today's version (2 January 2021, updated 12 April) includes a preliminary implementation of RESTView technology, which is a way of creating a single SQL database over the Web, using RESTful services that can be interfaced with over DBMS. At the moment, only Pyrrho allows definition of a "REST View", which is a virtual table whose contents are requested on demand, and is a good way of implementing view-mediated (logical) data integration. For details, see the Pyrrho manual and the documentation on GitHub. Obviously access to databases using REST interfaces needs a secure design, and this can be most easily achieved using standard SQL role permissions and Basic HTTP authentication over a secure transport.</p><p>REST View technology was demonstrated in previous versions of Pyrrho, still available on www.pyrrhodb.com. But for reasons documented elsewhere, I am currently upgrading Pyrrho to use shareable immutable data structures throughout, and this version, currently Pyrrhov7alpha, is taking time.</p><p>The main advantage of the REST View concept is that queries that include references to REST Views should be automatically optimised to minimise the amount of data that needs to be transferred between servers. For version 7 of Pyrrho, this important aspect is work in progress: and further updates should appear in GitHub over the next months or two.</p><p>References</p><p><span face="Arial, sans-serif" style="background-color: white; color: #222222; font-size: 13px;">Crowe, M., Begg, C., Laux, F. and Laiho, M., 2017. Data validation for big live data.</span></p><p><span face="Arial, sans-serif" style="background-color: white; color: #222222; font-size: 13px;">Offia, C.E. and Crowe, M., 2019. A theoretical exploration of data management and integration in organisation sectors. </span><i style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px;">Int. J. Database Manag. Syst.(IJDMS)</i><span face="Arial, sans-serif" style="background-color: white; color: #222222; font-size: 13px;">, </span><i style="background-color: white; color: #222222; font-family: Arial, sans-serif; font-size: 13px;">11</i><span face="Arial, sans-serif" style="background-color: white; color: #222222; font-size: 13px;">(1), pp.37-56.</span></p><p><span face="Arial, sans-serif" style="background-color: white; color: #222222; font-size: 13px;"><br /></span></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-49910283319818071492020-10-04T00:11:00.000-07:002020-10-04T00:11:01.225-07:00Mandatory Access Control in Pyrrho V7<p><span style="font-family: inherit;">From
December 2018 Pyrrho has offered a simulation of Bell-LaPadula security, following the Orange Book protocols for mandatory access control. The development of Pyrrho v8 alpha has now reached completed this stage. The current state of the source code and associated documentation is on <a href="https:/github.com/MalcolmCrowe/ShareableDataStructures">GitHub</a> as usual. There is a document describing Mandatory Access Control, and this post repeats some of those details.</span></p><p><span style="font-family: inherit;">Mandatory access control is based on the concepts of (a) <b>classification</b> of information and database objects from<b> level</b>s D (public) to A (top secret), (b) <b>clearance</b> of individual users to access classified information, and (c) <b>enforcement</b> of access rules on database tables (Select. Insert. Update, Delete). </span></p><p><span style="font-family: inherit;">Classification can be applied at the level of database tables, table columns, and individual records, and both clearance and classification at levels above D can specify permitted groups and topics for access. The database has a <b>security administrator</b> (in Pyrrho this is the database owner) who can audit and modify any aspect of the security model. All access to classified information (i.e. above level D) is instantly recorded in the database's transaction log giving the user's identity, the time, the tables accessed, and the key if any, even if the user made no changes.</span></p><p><span style="font-family: inherit;">The document <a href="https://github.com/MalcolmCrowe/ShareableDataStructures/blob/master/PyrrhoV7alpha/doc/Detailed%20Mandatory%20Access%20Control.pdf">Detailed Mandatory Access Control</a> includes a simple example. Here are some extracts:</span></p><p></p><h3>A. Logged in with MALCOLM1\Malcolm (not the server account)<o:p></o:p></h3>
<p class="MsoNormal">1. Starting with empty database mac <o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> create table A(B int,C char)<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> create table D(E char primary key)
security level D groups Army Navy references Defence scope read<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> create table F(G char primary key,H
char security level C)<o:p></o:p></b></span></p>
<p class="MsoNormal">2. Create some users with and without clearance<o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> grant "mac" to
"MALCOLM1\Student"<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> grant "mac" to
"MALCOLM1\Fred"<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> grant security level B groups Army
references Defence Cyber to "MALCOLM1\Student"<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> table "Sys$User"<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|----------------|-----------|-----------|-----------------------|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|Pos|Name<span style="mso-spacerun: yes;">
</span>|SetPassword|InitialRole|Clearance<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|----------------|-----------|-----------|-----------------------|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|26
|MALCOLM1\Malcolm|<span style="mso-spacerun: yes;"> </span>|mac<span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span>|<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|366|MALCOLM1\Student|<span style="mso-spacerun: yes;"> </span>|mac<span style="mso-spacerun: yes;"> </span>| B{ARMY}[CYBER,DEFENCE]|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|416|MALCOLM1\Fred<span style="mso-spacerun: yes;"> </span>|<span style="mso-spacerun: yes;">
</span>|mac<span style="mso-spacerun: yes;"> </span>|<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|----------------|-----------|-----------|-----------------------|<o:p></o:p></span></p>
<p class="MsoNormal">3. Add some rows with and without classification<o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> insert into A values(2,'Two')<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">1 records affected in mac<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> insert into A values(3,'Three')
security level C<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">1 records affected in mac<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> insert into D values('Test')<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">1 records affected in mac<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL> <b>insert into F
values('MI6','sis.gov.uk')<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">1 records affected in mac<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas;">SQL><b> table "Sys$Classification"<o:p></o:p></b></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|-----------|----------------------|---------------|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|Pos|Type<span style="mso-spacerun: yes;"> </span>|Classification<span style="mso-spacerun: yes;"> </span>|LastTransaction|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|-----------|----------------------|---------------|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|553|Record<span style="mso-spacerun: yes;"> </span>| C<span style="mso-spacerun: yes;"> </span>|537<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|154|Table<span style="mso-spacerun: yes;"> </span>| D{ARMY,NAVY}[DEFENCE]|138<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|313|TableColumn|
C<span style="mso-spacerun: yes;"> </span>|248<span style="mso-spacerun: yes;"> </span>|<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-bottom: 0cm; margin-bottom: 0cm; margin-top: 0cm; mso-add-space: auto; mso-margin-bottom-alt: 8.0pt; mso-margin-top-alt: 0cm;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;">|---|-----------|----------------------|---------------|<b><o:p></o:p></b></span></p><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="font-family: Consolas; font-size: 8.0pt; line-height: 107%;"><br /></span></div><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="line-height: 107%;"><span style="font-family: inherit;">Then Fred can see just one column in table F and cannot access table D, but can add new records to both tables A and F/ </span></span></div><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="font-family: inherit;"><br /></span></div><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="font-family: inherit;">Student can see everything so can make changes just now only in table D, whose enforcement is only on read. But Student can add new records to all of the tables. The document gives the full story....</span></div><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="font-family: inherit;"><br /></span></div><div style="margin-bottom: 0cm; margin-top: 0cm; text-align: left;"><span style="font-family: inherit;"><br /></span></div><span style="font-family: Calibri, sans-serif;"></span><p></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-45345899935995821442020-09-19T01:00:00.015-07:002020-10-03T23:34:25.507-07:00ACID Transaction performance with Pyrrho v7<p>Pyrrho uses optimistic algorithms and yet ensures true serialization for ACID transactions, even in conditions of high concurrency. According to many database textbooks, this should be unlikely or even impossible. Nevertheless, Pyrrho v7 achieves this goal, with the help of some novel programming techniques and approaches, with ACID performance much better than standard commercial databases.</p><p>In this blog post I want to provide a brief overview of the evidence for this achievement, and the techniques that enable it.</p><p>Pyrrho is of course a relational SQL database. First, we assume here that the goal of concurrency algorithms is to serialize concurrent ACID transactions. Pyrrho demonstrates actual serialization, not just serializability, since the database file is constructed as a serial file, where each committed transaction is appended separately to the file, enabling easy verification of the serialization at any later time. (A consequence of this approach is that the database contains a full history of every commit, and many professionals dislike their mistakes to be visible for all time.) The many ways of accessing the log file for verification purposes are described fully in the Pyrrho manual. The current state of the database is maintained in memory, and normal SQL access methods for the current data are enhanced by many system tables.</p><p>Moving on from the desirability or otherwise of a full serialized transaction log, what is meant here by conditions of high concurrency? There is a standard benchmark for online transaction processing maintained for many years by the Transaction Processing Council, and full details of this benchmark are available from https://tpc.org . The particular benchmark I refer to here is TPC-C, whose specification is available on <a href="http://www.tpc.org/tpc_documents_current_versions/pdf/tpc-c_v5.11.0.pdf">this link</a>. It was developed over twenty years ago, and models a telephone based ordering system where warehouses take orders from customers, organise delivery, process payments etc. Each warehouse has a clerk to operate the system, and there is a standard set of tasks that the clerks carry out.</p><p>There is one SQL database for the whole enterprise. Clerks are not superhuman, and it takes 23 seconds at least for a clerks to take the details of an order over the telephone (orders are for quantities of between 5 and 15 different products), somewhat less time for payments etc. It has always been an interesting test for DBMS comparisons because the benchmark design includes some important aspects that cause some difficulty for a DBMS. The standard mix of tasks results in 4% of transaction concurrency between different warehouses, and the performance target for a DBMS is the completion rate of new orders for the whole system. The 23 second requirement above means that for one warehouse this number is 16 new orders in 10 minutes, but standard DBMS report thousands of new orders per second when the number of warehouses becomes large.</p><p>I have modified this test by having multiple clerks per warehouse, in order to create a greater challenge for the DBMS. The testing software is written in C# and is available for numerous DBMS at <a href="https:/github.com/MalcolmCrowe/ShareableDataStructures">https:/github.com/MalcolmCrowe/ShareableDataStructures</a> . It is fair to say that this modification really shows up the weaknesses of all DBMS! All DBMS tested with this modified benchmark show an eventual collapse in performance if there are 10 clerks or more for a single warehouse, as the DBMS is forced to abort transactions because of concurrency conflicts. The testing program records all commit requests made to the database (in the order they are sent to the DBMS).</p><p>But Pyrrho v7 can outperform them all, with performance on a single PC increasing up to 50 clerks for one warehouse. Try it yourself: the code is available at the above location. Full explanations and further details are forthcoming in <a href="https://www.iaria.org/conferences2020/DBKDA20.html">DBKDA 2020</a>, with previous bulletins in previous years of this conference. The screenshot below shows 50 clerks (see the full <a href="https://youtu.be/0YaU59LvgLs">video</a>), and 338 new orders in 10 minutes despite most commits failing. As mentioned above, the serialization of transactions is verified by the transaction log. The figures are explained in conference papers. (Another optimistic DBMS, StrongDBMS, is also documented, which last year performed well for 100 clerks, but it lacks many features of standard SQL.)</p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMqrfZkeSkjPOFggECsCJ0IUlC88-DQUKV3fbEOVtfQyHsq5EJpBiav1YoB1Y4h801tJXtvKCYhAJOnMLkyW6JPmYOaG8qHNJx7nQymgtRgTyAhnxM3sV7DoaDszHVa1AW8KT_3AEYh-bJ/s902/Capture.JPG" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="549" data-original-width="902" height="339" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMqrfZkeSkjPOFggECsCJ0IUlC88-DQUKV3fbEOVtfQyHsq5EJpBiav1YoB1Y4h801tJXtvKCYhAJOnMLkyW6JPmYOaG8qHNJx7nQymgtRgTyAhnxM3sV7DoaDszHVa1AW8KT_3AEYh-bJ/w556-h339/Capture.JPG" width="556" /></a></div><br /><p><br /></p>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-48803146309011491772020-07-31T08:45:00.002-07:002020-07-31T08:45:56.485-07:00Lateral Derived Tables and Pyrrho v7<div><br /></div><div>This post discusses a new feature in v7 of Pyrrho, namely a simple implementation of lateral derived tables, that does not require the LATERAL keyword. Lateral derived tables are specified in section 7.6 "Table Reference" of the SQL standard, but are well introduced in the MySQL 8.0 manual at <a href="https://dev.mysql.com/doc/refman/8.0/en/lateral-derived-tables.html">https://dev.mysql.com/doc/refman/8.0/en/lateral-derived-tables.html</a> .</div><div><br /></div><div>That page gives an example problem where the concept is useful: <font face="inherit">"<span style="background-color: white; color: #555555;">Given a table of people in a sales force (where each row describes a member of the sales force), and a table of all sales (where each row describes a sale: salesperson, customer, amount, date), determine the size and customer of the largest sale for each salesperson.</span><span style="background-color: white; color: #555555;"> "</span></font></div><div><span style="background-color: white; color: #555555;"><font face="inherit"><br /></font></span></div><div><span style="background-color: white;"><font face="inherit">Now a naive solution might look like this:</font></span></div><div><p class="MsoNormal"><span style="mso-fareast-language: EN-US;">create table
SalesPerson(pid int primary key)<o:p></o:p></span></p>
<p class="MsoNormal">create table
Sales(sid int primary key, spid int, cust int, amount int)</p>
<p class="MsoNormal">select *
from SalesPerson, (select cust,
amount from Sales where spid = pid order by
amount desc fetch first 1 rows only)</p><p class="MsoNormal">According to the MySQL manual page, this is not permitted because <font face="inherit">"<span style="background-color: white;">A derived table cannot normally refer to (depend on) columns of preceding tables in the same </span><code class="literal" style="background: rgb(255, 255, 255); border: 0px; box-sizing: inherit; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">FROM</code><span style="background-color: white;"> clause. " The page goes on to discuss a number of solutions which either are very complicated or require the LATERAL keyword.</span></font></p><p class="MsoNormal"><font face="inherit"><span style="background-color: white;">Pyrrho v7 will automatically detect the need for a lateral derived table (or "lateral join") and will form the required join without using the LATERAL keyword. For example, the above naive solution is accepted and correctly computed by the current alpha build of Pyrrho at </span></font> <a href="https://github.com/MalcolmCrowe/ShareableDataStructures">https://github.com/MalcolmCrowe/ShareableDataStructures</a> . The feature is not discussed in the Pyrrho manual, because no special syntax is required.</p><p class="MsoNormal">I'd welcome comments on this feature, and a reference in the SQL standard for the rule that MySQL gives. Write to me at malcolm.crowe@uws.ac.uk .</p><span style="background-color: white;"><font face="inherit"></font></span></div>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-54026387524257331332020-06-29T05:52:00.003-07:002021-01-01T23:04:59.009-08:00Further progress with v7 alpha(for latest post see: 2 January 2021)<br />
<span style="background-color: white; color: #333333; font-family: georgia, serif; font-size: 13px;">on </span><a href="https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha" style="background-color: white; color: #999999; font-family: georgia, serif; font-size: 13px; text-decoration-line: none;">https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha</a><br />
<br />
An important goal in v7 of Pyrrho is to compile SQL code once only, on definition by the user or on load on a database cold-start. Another is to use shareable immutable data structures in the server wherever possible, in the manner described in the above GitHub repository. By the end of 2019, Database, Query and Transaction had these properties. The current version extends this philosophy to RowSet and Cursor objects, and the current version passes a set of tests including stored procedures, triggers, constraints, cascade operations, and structured types.<br />
<br />
The documentation in the repository includes full details of how this is done. The Pyrrho manual from previous versions applies almost unchanged to v7, and this version will reach beta stage when all examples in the Pyrrho manual have been implemented for v7. The next stage in this process will be to implement role-based security.<div><br /></div><div>I look forward to demonstrating the performance of the current version at DBKDA 2020. Comments to malcolm.crowe@uws.ac.uk, including PyrrhoDB in the subject line.<br />
<br /></div>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-17771569248793774832019-12-03T04:38:00.000-08:002020-03-28T23:43:09.010-07:00Progress with Pyrrho v7 alpha, contdToday's version (28 March 2020) on <a href="https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha">https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha</a><br />
shows check constraints, cascades and triggers working.<br />
V7 documentation is provided with the source code.<br />
<br />
There is a new section in the SourceIntro.pdf document about multi-threading, uids, and dynamic memory layout. This has been substantially improved since the December 2019 version to prepare<br />
for the next stage of implementation, which includes Persistent Stored Modules.<br />
<br />
The main technical changes are to make more of Pyrrho's data structures immutable and shareable: now including RowSets and Cursors which are now TypedValues.<br />
<br />
I hope to have a new full v7 version for the pyrrhodb.com website in the near future. The following is taken from the SourceIntro document in the alpha distribution, under the heading <b>Stored Persistent Modules. </b><br />
<br />
<div style="margin-top: 6.0pt; text-align: justify;">
This heading includes Trigger
and sored Procedure definitions, which are parsed once only by the server<a href="file:///E:/PyrrhoDB70/Pyrrho/doc/SourceIntro.doc#_ftn1" name="_ftnref1" style="mso-footnote-id: ftn1;" title=""><span style="font-family: "Times New Roman",serif;">[1]</span></a>.
Both use the SQL stored persistent modules language as described in the SQL standard,
including the handling of conditions (exceptions). When such modules are
invoked, they run in the definer’s role as specified by the SQL standard.</div>
<br />
<div style="margin-top: 6.0pt; text-align: justify;">
Following the design outlined
in this document, although the transaction log contains only the source form of
trigger and stored procedure code, while the in-memory database contains a
compiled version. From version 7 parsing is done once only, and following
parsing everything is referred to by uid, not by using string identifiers. As
their name implies, uids are unique in the database, but they are private to
the implementation, and are subject to change is later versions of the DBMS. The
transaction log contains only the source code of these modules, and the format is
forward and backward compatible. </div>
<br />
<div style="margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 36.0pt; margin-right: 0cm; margin-top: 6.0pt; text-align: justify;">
<span style="font-size: 9.0pt; mso-ansi-language: EN-GB;">There are differences in
operation of the different versions, however. Up to version 6.3 of the DBMS (file
format 5.1) the source code contained database object positions instead of the
definer’s name for database objects. This approach is supported in version 7 of
the DBMS for database files created with previous versions. Databases created
with version 7 or later (file format >5.1) will contain the source code
exactly as given by the definer. This is generally supported by previous
versions of the DBMS, but objects will display differently in the Log$ system
tables. </span></div>
<br />
<div style="margin-top: 6.0pt; text-align: justify;">
The in-memory data structures resulting
from parsing include SqlValues, Queries, and Executables. Persistent modules exist
in one of three forms, as follows:</div>
<br />
<ul style="margin-top: 0cm;" type="disc">
<li style="color: black; font-style: normal; font-weight: 400; margin-top: 6pt; text-align: justify;">Source code that has been
deserialised from the database file on Load() is compiled into data
structures that use uids based on lexical positions of source identifiers
in the database file. If the server is restarted after committing the
definition, the corresponding compiled code will be of this form.</li>
<li style="color: black; font-style: normal; font-weight: 400; margin-top: 6pt; text-align: justify;">For source code that has
been defined by client interaction, and committed to the database, the
compiled version will use uids allocated sequentially from within the
range of file positions where the commit has occurred, until the server is
restarted.</li>
<li style="color: black; font-style: normal; font-weight: 400; margin-top: 6pt; text-align: justify;">For source code that has
not yet been committed, the compiled version will use temporary uids above
5×2<sup>60</sup> allocated according to the lexical position in the client
input. This version is recursively converted to the above version on
Commit.</li>
</ul>
<br />
<div style="margin-top: 6.0pt; text-align: justify;">
Unless you are debugging the
server, you should notice no difference between these versions. The uids that
differ are not generally visible, and the in-memory compiled code structures are
otherwise identical. </div>
<br />
<div style="margin-top: 6.0pt; text-align: justify;">
CheckConstraints are simpler
as they consist merely of an SqlValueExpr that is tested to validate a given
value.</div>
<br />
<br />
<div style="mso-element: footnote-list;">
<br clear="all" />
<hr align="left" size="1" width="33%" />
<div id="ftn1" style="mso-element: footnote;">
<a href="file:///E:/PyrrhoDB70/Pyrrho/doc/SourceIntro.doc#_ftnref1" name="_ftn1" style="mso-footnote-id: ftn1;" title=""><span><span lang="EN-US"><span style="mso-special-character: footnote;"><span><span lang="EN-US" style="font-family: "Times New Roman",serif; font-size: 10.0pt; mso-ansi-language: EN-US; mso-bidi-language: AR-SA; mso-fareast-font-family: "Times New Roman"; mso-fareast-language: EN-US;">[1]</span></span></span></span></span></a><span lang="EN-US"> </span><span style="mso-ansi-language: EN-GB;">Up to version 6.3 of
the DBMS source code was parsed on each use.</span><br />
</div>
</div>
<b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br />
<b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br />
<br />Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-40939412972181986402019-11-21T02:31:00.000-08:002019-11-21T02:31:10.402-08:00Progress with Pyrrho v7 alphaThe alpha code for PyrrhoDB v7 on <a href="https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha" style="-webkit-text-stroke-width: 0px; color: #0066cc; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-decoration: underline; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" target="_blank">GitHub</a> was updated on 20 November 2019, which probably continues to demonstrate the concurrency with the Tpcc benchmark reported previously in this blog.<br />
The alpha version comes with a test application called PyrrhoTest, which will be extended in time to verify all sample code from <a href="http://pyrrhodb.com/">pyrrhodb.com</a>. The GitHub site contains updated documentation: the Pyrrho manual and an introduction to the source code.<br />
Pyrrho v7 aims to be compatible with databases developed with previous versions, and, apart from using optimistic concurrency throughout, complies closely with the ISO SQL standard.<br />
The current state of the v7 alpha implementation includes default values, generated columns, not-null and integrity constraints, alter and drop, and restrict/cascade behaviour for drop, update and delete in addition to joins and subqueries. Alters are role-dependent, laying the groundwork for a full implementation of role-based object renaming and the SQL security model.<br />
The next phases of implementation will include check constraints and triggers.Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-28598990581054217272019-09-25T12:47:00.000-07:002019-09-25T21:06:29.000-07:00Why Pyrrho performs so well in the TPC-C benchmark testsI have been asked how it can be that commercial DBMS, and also PostgreSQL, show up so badly in the TPC-C benchmark tests that I have <a href="https://github.com/MalcolmCrowe/ShareableDataStructures" target="_blank">published</a> on GitHub.<br />
<br />
To begin with, the TPC-C benchmark normally has 1 clerk per warehouse, so that the conflict rate is around 4%. In my tests I deliberatiely increase the concurrency challenge by using multiple clerks for a single warehouse. When the number of clerks goes above 10, most New Order tasks will fail with a write-write conflict on NEXT_O_ID as this is set per district and there are only 10 districts. Worse, the single row in the WAREHOUSE table contains an amount W_YTD which is updated by the payment task, and fields from this row are read by all the NewOrder tasks and others so that a great many more tasks are aborted because of read/write conflicts. In all of the products tested, apart from Pyrrho and StrongDBMS, read/write conflicts are detected at the row level or wider.<br />
<br />
Both Pyrrho and StrongDBMS see no conflict between the payment and NewOrder task because Payment is the only task that accesses W_YTD, and one of the available tests in the ReadConstraint for detecting read/write conflicts is a set of <i>fields</i> in a specific single row of a table.<br />
<br />
There are actually three levels of read/write conflict detection in these DBMS. The following comment in the source code at ReadConstraint.cs dates from about 2005:<br />
<br />
<span style="color: #38761d;"> /// ReadConstraints record all of the objects that have been accessed in the current transaction<br /> /// so that this transaction will conflict with a transaction that changes any of them.<br /> /// However, for records in a table, we allow specific non-conflicting updates, as follows:<br /> /// (a) (CheckUpdate) If unique selection of specific records cannot be guaranteed, then <br /> /// we should report conflict if any column read is updated by another transaction. <br /> /// (b) (CheckSpecific) If we are sure the transaction has seen a small number of records of tb, <br /> /// selected by specific values of the primary or other unique key, then <br /> /// we can limit the conflict check to updates of the selected records (if any), <br /> /// or to updates of the key TableColumns.<br /> /// (c) (BlockUpdate) as (a) but it is known that case (b) cannot apply.</span><br />
<span style="color: lime;"></span><span style="color: #38761d;"></span><br />
If the isolation level is reduced to repeatable-read or read-committed, most of the competing products achieve performance comparable with Pyrrho and StrongDBMS.<br />
<br />
I remain very satisfied with the results of these tests since they show that Pyrrho and StrongDBMS achieve such high scores on concurrency tests despite, or even because of, using immutable data structures and optimistic concurrency.Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-47403119554148995402019-09-16T23:11:00.002-07:002019-09-16T23:11:47.416-07:00TPCC benchmark with Pyrrho v7At present, successive updates to PyrrhoDB v7 alpha are on <a href="https://github.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha" target="_blank">GitHub</a> . As of today, this location contains the 14 September 2019 version, and a version of TpccPyrrho. The TPC-C benchmark test is for OLTP for a warehouse, where the clerk works through a task sequence including new orders, with realistic time delays. In 10 minutes the clerk handles 16 new orders along with other tasks.<br />
<br />
In order to demonstrate exceptional handling of concurrency, this version of the benchmark uses multiple clerks per warehouse. This introduces high levels of concurrency and many transactions should fail. With <a href="http://www.strongdbms.com/" target="_blank">StrongDBMS</a> I demonstrated performance superior to commercial databases, and now can do the same with the alpha version of PyrrhoDB. The GitHub repository includes versions of the benchmark for several popular DBMS so this claim can be verified by anyone interested.<br />
<br />
The results for Pyrrho v7 alpha are as follows:<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">
Recreate DB: 1:02</span><br />
<br />
<span style="mso-fareast-language: EN-US;">
Fill stock: 2:02</span><br />
<br />
<span style="mso-fareast-language: EN-US;">
Fill districts: 6:15</span><br />
<br />
<span style="mso-fareast-language: EN-US;">
Cold start with initial warehouse: 1:30</span><br />
<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">F:\PyrrhoDB7\Pyrrho>tpccpyrrho</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 1 loaded at
15/09/2019 12:04:32</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Started at
15/09/2019 12:04:40 with 1 clerks</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 2 loaded at 15/09/2019
12:04:40</span><br />
<br />
<span style="mso-fareast-language: EN-US;">At 15/09/2019
12:14:40 Commits 16, Conflicts 0 0</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Last fid=2</span><br />
<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">F:\PyrrhoDB7\Pyrrho>tpccpyrrho</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 1 loaded at
15/09/2019 12:17:56</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Started at
15/09/2019 12:18:03 with 10 clerks</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 11 loaded at
15/09/2019 12:18:03</span><br />
<br />
<span style="mso-fareast-language: EN-US;">At 15/09/2019
12:28:03 Commits 145, Conflicts 0 95</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Last fid=11</span><br />
<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">F:\PyrrhoDB7\Pyrrho>tpccpyrrho</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 1 loaded at
15/09/2019 12:32:41</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Started at
15/09/2019 12:33:33 with 100 clerks</span><br />
<br />
<span style="mso-fareast-language: EN-US;">fid 101 loaded at
15/09/2019 12:35:01</span><br />
<br />
<span style="mso-fareast-language: EN-US;">At 15/09/2019
12:43:33 Commits 313, Conflicts 0 2920</span><br />
<br />
<span style="mso-fareast-language: EN-US;">Last fid=101</span><br />
<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">F:\PyrrhoDB7\Pyrrho></span><br />
<br />
<br />
<br />
<span style="mso-fareast-language: EN-US;">During the
benchmark test for 100 clerks my desktop machine reported the CPU utilisation
was around 40% and the memory utilisation 50%.</span><br />
<br />
<br />
PyrrhoDB v7 should reach beta version by December and include all of the usual database features as in previous versions of the DBMS.Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-23214778787642359932019-09-02T02:43:00.000-07:002019-09-02T02:43:14.197-07:00Pyrrho v7 alpha availableThe <a href="https://pyrrhodb.uws.ac.uk/PyrrhoV7alpha.zip" target="_blank">2 September alpha code of PyrrhoDB v7</a> is now available<br />
So far it can manage creation and CRUD operations on simple tables, but has a full set of data types and system tables. There is an updated introduction to the source code in the doc folder.<br />
Work continues, comments welcome.<br />
<br />Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-5467608362261464862019-08-20T11:20:00.002-07:002019-08-20T11:20:46.118-07:00Pyrrho V7 progress
<br />
A draft version of the “Introduction to the Source Code”
document for v7.0 is available <a href="https://pyrrhodb.uws.ac.uk/SourceIntro7.0.pdf" target="_blank">here</a> .<br />
<br />
So far PyrrhoSvr.exe is under 800KB, and will probably stay below 1MB.
It is quite different from version 6.3.<br />
<br />
<br />
<br />
By contrast the user manual Pyrrho.pdf has almost no
changes, apart from dropping the idea of multi-database connections. <br />
<br />
Database files from version 6.3 (OSP and Pro) should work
with PyrrhoSvr v7.0. The reverse will not be the case as I hope that Pyrrho
v7.0 will allow the development of database files before users are defined and
will enable databases to be renamed.<br />
<br />
<br />
<br />
Almost all of the internal operation has changed:<br />
<br />
<ul style="margin-top: 0cm;" type="disc">
<ul style="margin-top: 0cm;" type="circle">
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">Identifiers (and the
Ident class) are used only for Parsing: uids are used everywhere else</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">BList has been added to
BTree and both are easier to use</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">There is a Basis class
for making work with immutable/shareable classes more efficient and
intuitive</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">IO operations (Level1)
have been remodelled following the StrongDBMS architecture</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">The Physical level 2 is
not only for serialisation to the transaction log file (PhysBase has
gone)</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">The logical database
layer (“Level 3”) now includes Transaction and Database and their
components, and everything at this level is immutable and shareable</span></li>
<li style="color: black; font-size: 11pt; font-style: normal; font-weight: 400; margin-left: 0cm;"><span style="mso-fareast-font-family: "Times New Roman";">All queries and SQL
code fragments are parsed exactly once (and for each role on grant), are then
immutable/shareable, and don’t need further analysis. </span></li>
</ul>
</ul>
<br />
I will upload an alpha version soon. I plan to
make Tpcc a first priority, then all of the examples in the Pyrrho manual,
ending with the RESTView example probably sometime next year. The Embedded
edition can wait for now.<br />
<br />
<b></b><i></i><u></u><sub></sub><sup></sup><strike></strike>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-24605048258895558832019-06-24T00:27:00.002-07:002019-06-24T00:27:27.852-07:00Version 7 is coming (soon)<div>
Starting in autumn 2018 I have been developing StrongDBMS (strongdbms.com, Twitter #StrongDBMS) which incorporates many of PyrrhoDB's ideas, but handles concurrency better than other DBMS I have managed to test. The reasons and source code are written up in GitHub, see shareabledata.org .These tests also showed up some weaknesses in Pyrrho.</div>
<div>
Both Strong and Pyrrho use a minimal set of locks to manage concurrency and ensure ACID properties: one lock is for the DBMS itself, and one for each database file. Unfortunately, in versions up to 6.3, Pyrrho transactions can involve more than one database, and the database is stored in a sequence of files (with file names including sequence numbers 001 etc if required). Both of these "improvements" in Pyrrho make verification of ACID properties more difficult.</div>
<div>
I will produce a cleaned up version 7 of Pyrrho that will be backwards compatible with Pyrrho 6.3, apart from lacking multi-database connections and supporting only one file per database. </div>
<div>
<br /></div>
Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-29450669486023335592018-12-13T09:25:00.001-08:002019-01-05T04:57:18.765-08:00Mandatory Access ControlPyrrho now provides a free-to-use simulation of Bell-LaPadula security, similar to the US Department of Defense Orange Book. The basic idea is well-explained in Wikipedia and popular database textbooks and there corrent implementations of this security model in Oracle 18.<br />
A feature of the system is that a table can contain rows with different security classifications, and users will be able to see a subset of these detemined by their security clearance. Users can create or modify data that matches their clearance.<br />
The basic idea is that there are security levels D,C,B and A, and security is managed by the database owner (the security administrator SA). The SA can give users a security clearance, and can give <span style="background-color: white; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">a classification based on these levels to </span>objects such as tables and rows in the database.<br />
By default all access to tables is then subject to security clearance, but the SA can limit enforcement in a table to any combination of read, insert, update and delete. In addition the SA can specify two sets of identifiers (Pyrrho calls these groups and references), so that security clearance and classification can be enhanced using subsets of these identifiers.<br />
To whet your appetite, here is a simple test script [as revised 5 January 2019]:<br />
<br />
A. Logged in as database owner <br />
1. Starting with empty database "mac"<br />
create table A(B int,C char)<br />
create table D(E char primary key) security level D groups Army Navy references Defence scope read<br />
create table F(G char primary key,H char security level C)<br />
revoke "mac" from public <br />
2. Create some users with and without clearance. (On Windows prefix the user names with Domain\)<br />
grant "mac" to "Student"<br />
grant "mac" to "Fred"<br />
grant security level B groups Army references Defence Cyber to "Student"<br />
3. Add some rows with and without classification<br />
insert into A values(2,'Two')<br />
insert into A values(3,'Three') security level C<br />
insert into D values('Test')<br />
insert into F values('MI6','sis.gov.uk')<br />
4. Check we can see two rows in A, one row in D and two columns in F<br />
table A<br />
table D<br />table F<br />
<br />
B. Logged in as Fred<br />
5. Check we can only see one row in A, one column in F, and nothing in D<br />
table A<br />
table D<br />table F<br />
6. Check we can add a row in A, D and F<br />insert into A values(4,'Four')<br />insert into D values('Fred wrote this')<br />insert into F values('UWS')<br />
<br />
<br />
C. Logged in as Student<br />
7. Check we can see three rows in A, two rows in D and two columns in F<br />table A<br />table D<br />table F<br />
<br />
8. Check we can' only make changes in table D (enforcement in D is only for read)<br />
update A set c = 'No' where b=2<br />
update A set c = 'No' where b=3<br />
update A set c = 'No' where b=4<br />
update D set E='Fred?' where E<>'Test'<br />update F set H='www.sis.gov.uk' where G='MI6'<br />update F set H='www.uws.ac.uk' where G='UWS'<br />
9. Check we can add and update rows in all three tables<br />
insert into A values(5,'Fiv')<br />
update A set c='Five' where b=5<br />
insert into D values('Another')<br />
insert into F values('BBC','bbc.co.uk')<br />update F set H='www.bbc.co.uk' where G='BBC'<br />
10. Check we can see our rows and changes<br />
table A<br />
table D<br />table F<br />
<br />
D. Logged in as Fred<br />11. Check Fred can't see the new rows<br />table A<br />table D<br />table F<br />
<br />
E. Logged in as database owner<br />
12. Check all tables including the security information<br />
select B,C,security from A<br />
select E,security from D<br />
select G,H,security from F<br />
select * from A where security=level c<br />
update A set security=level C where security=level B<br />
update F set security=level D where G='BBC'<br />table "Sys$Classification"<br />
<br />
F. Logged in as Student<br />
13. Check we can still see our row in A<br />
select * from a where b=5<br />
14. Check we can no longer update our rows in A or F<br />
delete from A where b=5<br />
update F set H='bbc.com' where G='BBC'<br />
<br />
G. Logged in as Fred<br />15. Check we can see the row about the BBC<br />
<br />
H. Logged in as database owner<br />
16. Check that auditing has been happening<br />table "Sys$Audit"<br />
<br />
Full details of Pyrrho's implementation are in the manual at section 3.4.2 and the syntax pages on pyrrhodb.com have been updated to include the syntax extensions. <span style="background-color: white; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">The SA is able to manage all of this with the help of a set of system tables such as Sys$Classification. A commercial vendor such as Oracle provides many tools to assist in this process.</span><br />
<span style="background-color: white; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">The implementation in Pyrrho is new and no doubt will evolve over the next weeks. Comments please to malcolm.crowe@uws.ac.uk . Also follow me @MalcolmCrowe #PyrrhoDBMS .</span><br />
<span style="background-color: white; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">(Update 5 Jan 2019: the manual has been updated to remove an incorrect assertion about changes to security clearance. Such changes can have no effect on ongoing transactions.)</span>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-19296212588614662672018-11-23T00:44:00.000-08:002018-11-28T14:00:06.503-08:00Recording access to sensitive data<br />
<div style="line-height: normal;">
Today there is considerable
interest in access auditing, and a requirement in some jurisdictions for companies
to record use of sensitive data.</div>
<div style="line-height: normal;">
Pyrrho already indelibly records changes to all data together with the user/role and time of changes, and watches reading of data during transactions to construct simple constraints on a transaction being committed. </div>
<div style="line-height: normal;">
As a matter of fact, few experts agree with this feature, since it means the inclusion of a read operation in a transaction will prevent the transaction being committed a concurrent transaction commits a modification of any of the data that has been read. Pyrrho enforces this approach however, because the user whose transaction is prevented from committing is the same one who (presumably deliberately) included the read operation in the transaction.</div>
<div style="line-height: normal;">
The present discussion also considers read operations but in a different way. Here we want to distinguish sensitive data (say at the data type level) and immediately record access to it (by anyone other than the database owner), whether or not the current operation is ever committed. </div>
<div style="line-height: normal;">
These features [updated: 27 November] are available in Pyrrho version 6.3. The audit record is merged into the transaction log and a system table gives access to all the details.<br />
From the manual:<br />
<span style="font-size: x-small;">Sec 1.5:</span>
<br />
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Version
6.3 adds support for “sensitive” data, for which any access is auditable. Columns,
domains and types can be declared SENSITIVE<a href="file:///E:/PyrrhoDB63/Pyrrho/doc/Pyrrho.docx" name="_ftnref1" style="mso-footnote-id: ftn1;" title=""><span><span style="mso-special-character: footnote;"><span><span style="font-family: "Times New Roman",serif; font-size: 10.0pt; mso-ansi-language: EN-GB; mso-bidi-language: AR-SA; mso-fareast-font-family: SimSun; mso-fareast-language: ZH-CN;">[1]</span></span></span></span></a>.
Sensitive values are not assignment-compatible with anything that is not
sensitive, and there is a sensitive property inherited by any object that
contains a sensitive data type. This means for example that the sum of
sensitive data is still sensitive. The transaction log will contain a record of
every access to sensitive values (apart from by the database owner), even if the
transaction is rolled back. These details are visible in the Sys$Audit system
table (see section 8.3.1).</span></div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Sec 7.4:</span></div>
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;"><div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<div style="margin-bottom: .0001pt; margin-bottom: 0cm; margin-left: 78.0pt; margin-right: 0cm; margin-top: 6.0pt; text-align: justify; text-indent: -78.0pt; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Type</span><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;"><span style="mso-spacerun: yes;"> </span>= <span style="mso-tab-count: 1;"> </span>(StandardType
| DefinedType | <i style="mso-bidi-font-style: normal;">Domain</i>_id | <i style="mso-bidi-font-style: normal;">Type</i>_id | </span><span style="font-family: "Arial Unicode MS",sans-serif; font-size: 10.0pt; mso-ansi-language: EN-GB;">REF’</span><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">(‘TableReference’)’) [UriType]
[</span><span style="font-family: "Arial Unicode MS",sans-serif; font-size: 10.0pt; mso-ansi-language: EN-GB;">SENSITIVE</span><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">] .</span></div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
Sec 8.3.1:</div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<h3>
8.3.1 Sys$Audit</h3>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse; border: none; mso-border-alt: solid windowtext .5pt; mso-border-insideh: .75pt solid windowtext; mso-border-insidev: .75pt solid windowtext; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-yfti-tbllook: 480;">
<tbody>
<tr style="mso-yfti-firstrow: yes; mso-yfti-irow: 0;">
<td style="border: solid windowtext 1.0pt; mso-border-bottom-alt: .75pt; mso-border-color-alt: windowtext; mso-border-left-alt: .5pt; mso-border-right-alt: .75pt; mso-border-style-alt: solid; mso-border-top-alt: .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Field</span></b></div>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">DataType</span></b></div>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-bottom-alt: .75pt; mso-border-color-alt: windowtext; mso-border-left-alt: .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: .5pt; mso-border-style-alt: solid; mso-border-top-alt: .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Description</span></b></div>
</td>
</tr>
<tr style="mso-yfti-irow: 1;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Pos</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The location of this access
record in the transaction log</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 2;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">User</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The defining position of the
accessing user</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 3;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Table</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The defining position of the
sensitive table or view object</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 4; mso-yfti-lastrow: yes;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-bottom-alt: .5pt; mso-border-color-alt: windowtext; mso-border-left-alt: .5pt; mso-border-right-alt: .75pt; mso-border-style-alt: solid; mso-border-top-alt: .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Timestamp</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Int</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-bottom-alt: .5pt; mso-border-color-alt: windowtext; mso-border-left-alt: .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: .5pt; mso-border-style-alt: solid; mso-border-top-alt: .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The time of the access in
ticks</span></div>
</td>
</tr>
</tbody></table>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Audit
records are only for committed sensitive data. Entries come from physical Audit
records, and are added immediately on access (do not wait for transaction
commit). </span></div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<h3>
8.3.2 Sys$AuditKey</h3>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse; border: none; mso-border-alt: solid windowtext .5pt; mso-border-insideh: .75pt solid windowtext; mso-border-insidev: .75pt solid windowtext; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-yfti-tbllook: 480;">
<tbody>
<tr style="mso-yfti-firstrow: yes; mso-yfti-irow: 0;">
<td style="border: solid windowtext 1.0pt; mso-border-bottom-alt: .75pt; mso-border-color-alt: windowtext; mso-border-left-alt: .5pt; mso-border-right-alt: .75pt; mso-border-style-alt: solid; mso-border-top-alt: .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Field</span></b></div>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">DataType</span></b></div>
</td>
<td style="border-left: none; border: solid windowtext 1.0pt; mso-border-bottom-alt: .75pt; mso-border-color-alt: windowtext; mso-border-left-alt: .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: .5pt; mso-border-style-alt: solid; mso-border-top-alt: .5pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div align="center" style="text-align: center;">
<b style="mso-bidi-font-weight: normal;"><span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Description</span></b></div>
</td>
</tr>
<tr style="mso-yfti-irow: 1;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Pos</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The location of the access
record in the transaction log</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 2;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Seq</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Int</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The ordinal position of the
key (0 based)</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 3;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Col</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: solid windowtext .5pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">The defining position of the
key column</span></div>
</td>
</tr>
<tr style="mso-yfti-irow: 4; mso-yfti-lastrow: yes;">
<td style="border-top: none; border: solid windowtext 1.0pt; mso-border-bottom-alt: .5pt; mso-border-color-alt: windowtext; mso-border-left-alt: .5pt; mso-border-right-alt: .75pt; mso-border-style-alt: solid; mso-border-top-alt: .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.45pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Key</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-alt: solid windowtext .75pt; mso-border-bottom-alt: solid windowtext .5pt; mso-border-left-alt: solid windowtext .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 79.55pt;" valign="top" width="106">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Char</span></div>
</td>
<td style="border-bottom: solid windowtext 1.0pt; border-left: none; border-right: solid windowtext 1.0pt; border-top: none; mso-border-bottom-alt: .5pt; mso-border-color-alt: windowtext; mso-border-left-alt: .75pt; mso-border-left-alt: solid windowtext .75pt; mso-border-right-alt: .5pt; mso-border-style-alt: solid; mso-border-top-alt: .75pt; mso-border-top-alt: solid windowtext .75pt; padding: 0cm 5.4pt 0cm 5.4pt; width: 267.45pt;" valign="top" width="357">
<div style="text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">A string representation of
the key value at this position</span></div>
</td>
</tr>
</tbody></table>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
</div>
<div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;">Key
information for audit records comes from the filters used to access a sensitive
object. For example, if a record is inserted in a table, there is no applicable
filter, the audit record will apply to the whole table, and there will be no
key information here.</span></div>
</span><div style="margin-top: 6.0pt; text-align: justify; text-justify: inter-ideograph;">
<span style="font-size: 10.0pt; mso-ansi-language: EN-GB;"><span style="-webkit-text-stroke-width: 0px; background-color: white; color: black; display: inline !important; float: none; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">Comments by email are welcome.</span><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike></span></div>
<br />
<div style="mso-element: footnote-list;">
<br clear="all" />
<hr align="left" size="1" width="33%" />
<div id="ftn1" style="mso-element: footnote;">
<span style="font-size: x-small;"><a href="file:///E:/PyrrhoDB63/Pyrrho/doc/Pyrrho.docx" name="_ftn1" style="mso-footnote-id: ftn1;" title=""><span lang="EN-US"><span lang="EN-US" style="font-family: "Times New Roman",serif;">[1]</span></span></a><span lang="EN-US"> </span>SENSITIVE is a
reserved word in SQL that normally applies to cursor sensitivity. The usage in
Pyrrho described here is quite different, and the keyword comes at the end of a
type clause (see section 7.4).</span><br />
</div>
</div>
<br />
<br /></div>
<br />
<div style="line-height: normal;">
<br /></div>
<b></b><i></i><u></u><sub></sub><sup></sup><strike></strike>Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-54411119076004484362018-11-21T12:19:00.003-08:002018-11-21T12:19:43.182-08:00Rethinking Shareable Data StructuresI have been recently developing a set of data structures following on from <a href="https://www.google.co.uk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=2ahUKEwjY5teuo-beAhXLD8AKHc13AjcQFjAAegQIDhAC&url=https%3A%2F%2Fwww.cs.cmu.edu%2F~rwh%2Ftheses%2Fokasaki.pdf" target="_blank">Okasaki's Purely Functional Data Structures</a>. There is a lot to be gained by using immutable data structures, that is, where all the fields are public readonly in C# or public final in Java. Strings in C# and Java already have this property and it turns out to be remarkably easy to develop all the usual data structure types with this property. Something of the kind had already started to happen in Pyrrho: many of Pyrrho's data structures are immutable, and Pyrrho uses Bookmarks instead of Iterators. Specifically, the benefits (as with strings) are<br />
<ul>
<li> a snapshot is obtained by a simple assignment, so rollback is a breeze</li>
<li> structures can be modified while a traversal continues with the previous state#</li>
<li> they are thread-safe and safe to pass as a parameter in C# or Java, so that</li>
<li> these data structures never need to be locked</li>
</ul>
The price to be paid is extra work for the garbage collector: this is a reasonable trade-off.<br />
So the time seemed ripe for a serious approach to <a href="https://twitter.com/hashtag/ShareableDataStructures" target="_blank">#ShareableDataStructures</a> and the fruits of these labours are emerging at <a href="http://github.com/MalcolmCrowe/ShareableDataStructures" target="_blank">github.com</a> . Eventually the classes will be rich enough to implement a DBMS, and the plan is to implement everything in C# and Java, and then Python later. Efforts in the DBMS direction are currently called <a href="https://twitter.com/hashtag/StrongDBMS" target="_blank">#StrongDBMS</a> . A lot will depend on the performance of the <a href="http://tpc.org/tpcc" target="_blank">TPCC</a> benchmark.<br />
It is natural to ask what this might mean for Pyrrho. It does seem like a natural evolution (Pyrrho 7.0 maybe), but some of the Pyrrho code would be a real nuisance to transform. Time will tell.<br />
<br />
<br />
<br />Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-86501794912479210712018-10-02T02:26:00.002-07:002018-10-02T02:26:45.586-07:00Window FunctionsA basic set of window functions are supported in PyrrhoDBMS. The full set of OLAP functions as defined in ISO 9075 used to be supported and can be again if there is demand: email me if you think this would be useful or if you find any issues (my direct email at UWS is in the pyrrhodb.com download).Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0tag:blogger.com,1999:blog-4899156161526860882.post-51523318576825231952018-08-11T00:26:00.002-07:002018-09-04T00:45:08.077-07:00Latest version of Pyrrho 6.2This version fixes a number of long-standing bugs in Pyrrho, including the following significant areas:<br />
<ul>
<li>Exit handlers</li>
<li>Check constraints</li>
<li>Triggers</li>
<li>OSPStudio</li>
<li>Row count</li>
</ul>
<div>
The Java Connector (PyrrhoJC) is also being fixed for Java SE, and more changes are expected.<br />
In addition, some syntax error messages have been made more helpful. Many thanks for those who have submitted performance reports - I have tried your patience by taking so long to fix them.</div>
<div>
Please send me details of any problems you find (malcolm.crowe@uws.ac.uk).</div>
Malcolm Crowehttp://www.blogger.com/profile/09753616974538155811noreply@blogger.com0