Modifiable rowsets

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.

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.

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:

SubClass	Insert	Update	Delete
DistinctRowSet	No	No	No
DocArrayRowSet	Yes	Yes	Yes
EmptyRowSet
EvalRowSet	No	No	No
ExplicitRowSet
GroupingRowSet	No	No	Yes
IndexRowSet	(Yes)	(Yes)	(Yes)
JoinRowSet	Yes	Yes	Yes
MergeRowSet	Intersection only	Yes	Yes
OldTableRowSet
OrderedRowSet	Yes	Yes	Yes
RestRowSet	Yes	Yes	Yes
RoutineCallRowSet
RowSetSection	No	Yes	Yes
SelectRowSet	See below	See below	Yes
SelectedRowSet	Yes	Yes	Yes
SqlRowSet
SystemRowSet
TableRowSet	(Yes)	(Yes)	(Yes)
TransitionRowSet
TrivialRowSet
ValueRowSet
WindowRowSet	No	No	No

 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.

Progress with Pyrrho v7 alpha

 See code on https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha

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.

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.

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.

References

Crowe, M., Begg, C., Laux, F. and Laiho, M., 2017. Data validation for big live data.

Offia, C.E. and Crowe, M., 2019. A theoretical exploration of data management and integration in organisation sectors. Int. J. Database Manag. Syst.(IJDMS), 11(1), pp.37-56.

Mandatory Access Control in Pyrrho V7

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 GitHub as usual. There is a document describing Mandatory Access Control, and this post repeats some of those details.

Mandatory access control is based on the concepts of (a) classification of information and database objects from levels D (public) to A (top secret), (b) clearance of individual users to access classified information, and (c) enforcement of access rules on database tables (Select. Insert. Update, Delete). 

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 security administrator (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.

The document Detailed Mandatory Access Control includes a simple example. Here are some extracts:

A. Logged in with MALCOLM1\Malcolm (not the server account)

1. Starting with empty database mac

SQL> create table A(B int,C char)

SQL> create table D(E char primary key) security level D groups Army Navy references Defence scope read

SQL> create table F(G char primary key,H char security level C)

2. Create some users with and without clearance

SQL> grant "mac" to "MALCOLM1\Student"

SQL> grant "mac" to "MALCOLM1\Fred"

SQL> grant security level B groups Army references Defence Cyber to "MALCOLM1\Student"

SQL> table "Sys$User"

|---|----------------|-----------|-----------|-----------------------|

|Pos|Name            |SetPassword|InitialRole|Clearance              |

|---|----------------|-----------|-----------|-----------------------|

|26 |MALCOLM1\Malcolm|           |mac        |                       |

|366|MALCOLM1\Student|           |mac        | B{ARMY}[CYBER,DEFENCE]|

|416|MALCOLM1\Fred   |           |mac        |                       |

|---|----------------|-----------|-----------|-----------------------|

3. Add some rows with and without classification

SQL> insert into A values(2,'Two')

1 records affected in mac

SQL> insert into A values(3,'Three') security level C

1 records affected in mac

SQL> insert into D values('Test')

1 records affected in mac

SQL> insert into F values('MI6','sis.gov.uk')

1 records affected in mac

SQL> table "Sys$Classification"

|---|-----------|----------------------|---------------|

|Pos|Type       |Classification        |LastTransaction|

|---|-----------|----------------------|---------------|

|553|Record     | C                    |537            |

|154|Table      | D{ARMY,NAVY}[DEFENCE]|138            |

|313|TableColumn| C                    |248            |

|---|-----------|----------------------|---------------|

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/ 

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....

ACID Transaction performance with Pyrrho v7

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.

In this blog post I want to provide a brief overview of the evidence for this achievement, and the techniques that enable it.

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.

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 this link. 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.

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.

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 https:/github.com/MalcolmCrowe/ShareableDataStructures . 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).

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 DBKDA 2020, with previous bulletins in previous years of this conference. The screenshot below shows 50 clerks (see the full video), 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.)

Lateral Derived Tables and Pyrrho v7

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 https://dev.mysql.com/doc/refman/8.0/en/lateral-derived-tables.html .

That page gives an example problem where the concept is useful: "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. "

Now a naive solution might look like this:

create table SalesPerson(pid int primary key)

create table Sales(sid int primary key, spid int, cust int, amount int)

select * from SalesPerson,  (select cust, amount from Sales where spid = pid  order by amount desc fetch first 1 rows only)

According to the MySQL manual page, this is not permitted because "A derived table cannot normally refer to (depend on) columns of preceding tables in the same FROM clause. " The page goes on to discuss a number of solutions which either are very complicated or require the LATERAL keyword.

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  https://github.com/MalcolmCrowe/ShareableDataStructures . The feature is not discussed in the Pyrrho manual, because no special syntax is required.

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 .

Further progress with v7 alpha

(for latest post see: 2 January 2021)
on https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha

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.

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.

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.

Progress with Pyrrho v7 alpha, contd

Today's version (28 March 2020) on https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha
shows check constraints, cascades and triggers working.
V7 documentation is provided with the source code.

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
for the next stage of implementation, which includes Persistent Stored Modules.

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.

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 Stored Persistent Modules. 

This heading includes Trigger and sored Procedure definitions, which are parsed once only by the server[1]. 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.

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.

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.

The in-memory data structures resulting from parsing include SqlValues, Queries, and Executables. Persistent modules exist in one of three forms, as follows:

• 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.
• 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.
• For source code that has not yet been committed, the compiled version will use temporary uids above 5×2⁶⁰ allocated according to the lexical position in the client input. This version is recursively converted to the above version on Commit.

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.

CheckConstraints are simpler as they consist merely of an SqlValueExpr that is tested to validate a given value.

---

[1] Up to version 6.3 of the DBMS source code was parsed on each use.