DEVELOPING A TOOL TO

VERIFY TRIGGERS IN DBMS
1

Supervisor : Assoc Prof. Dr. Truong Ninh Thuan
Co-supervisor : MSc. Le Hong Anh
Student : Dang Minh Dung


2

Outline
1. Motivation
2. Background
3. S2B tool
4. Conclusion and future works


3

Motivation

No table employee yet.
Example 1
Some SQL statements are only
checked when they execute.

 How we can verify the
correctness of database systems
with triggers in early design phase?

Infinite loop
Example 2


4

Motivation
 In a previous work [1], a new method was introduced by
using Event-B formal method to solve above issue.

 Our contribution is building a tool (called S2B) which can
automatic translate form database systems to event-b models
and partly supports modelling process with the Rodin platform.

[1] Hong Anh Le, and Ninh Thuan Truong. "Modeling and verifying DML triggers using event-B." Intelligent Information and
Database Systems. Springer Berlin Heidelberg, 2013. 539-548


5

Database systems
 Tables (T)
 Constraints (C)
 Triggers (G)
 ECA (Event – Condition – Action) form

TRIGGER <trigger_name>
Event


<event>

Condition

Generalize
Actions

WHEN <conditions>
BEGIN
<actions>
END;


Event-B

6

Event-B is a formal method for system-level modelling and analysis.
Key features:
•

using set theory as modelling notation

•

using refinement to represent systems at different level

•

Using mathematical proof to verify consistency


 Context
A context describes the static part of a Event-B model.

 Machine
A machine describes the dynamic behaviour of a Event-B model.

o Event
Event describe when and how machine state changes over the time.
Event also has the form of an EAC.

 Rodin
The Rodin Platform is an Eclipse-based IDE for Event-B.


7

S2B Tool
 Main function: translate from database system to
event-b model.
 Other function: Detect some compilation errors.

S2B tool architecture


8

Database Adapter
 Functionality: connect to database and dump its
schema.

 Input: database URL for example:

E:\SQL-to-EventB\res\test\db\demo.db

 Output: database schema in SQL statements form.
 Currently, our tool only support SQLite.
 Using JDBC to connect to database
 Use following statement to get schema:
SELECT sql FROM
(SELECT * FROM sqlite_master UNION ALL
SELECT * FROM sqlite_temp_master)
WHERE type!='meta'
ORDER BY tbl_name, type DESC, name


9

SQL Extractor
 Functionality: eliminate redundant information and
transform schema into a standard form.
 2 steps:
o Parsing SQL statements
o Normalizing database models

 Step 1: Parsing SQL statements
o Using ANTLR library.
o Define SQLite grammar then ANTLR generate lexer and parser
o Output: Abstract Syntax Tree (AST)

Abstract Syntax Tree



10

SQL Extractor
 Step 2: normalizing database models.
o Reasons for normalizing database models.
 AST is sequential access
 Exists opposite statements as CREATE, ALTER, DROP in schema
 Unnecessary statements as DML statements (INSERT, UPDATE,
DELETE)
 We want to create a unified format across DBMS schema.

o Use visitor design pattern to travel AST.
 Extend default visitor.
 Use symbol table to manager identifiers.

o Output: database models – a unified form of schema.
o After SQL extractor module, we can detect some
compilation errors…


S2B Translator

11

 Functionality: translate form database model to
event-b model.
 Base on bellow translation rules[1]:
Database definitions


Event-B concepts

Rule 1

𝑑𝑏 = 𝑇, 𝐶, 𝐺

Rule 2

Table 𝑡 ∈ 𝑇

𝑇𝑎𝑏𝑙𝑒 = 𝑇𝑦𝑝𝑒1 × 𝑇𝑦𝑝𝑒2 × ⋯ × 𝑇𝑦𝑝𝑒𝑛

Rule 3

Primary key constraint

Invariant 𝑝𝑘: 𝑑𝑜𝑚(Type1 × ⋯ × 𝑇𝑦𝑝𝑒𝑖 ) ⤖
𝑟𝑎𝑛(Typei+1 × ⋯ × 𝑇𝑦𝑝𝑒𝑛 )

Rule 4

Constraint 𝑐 ∈ 𝐶

Invariant 𝑖

Rule 5

Trigger 𝑔 ∈ 𝐺


Event 𝑒

𝑑𝑏𝐶𝑜𝑛𝑡𝑒𝑥𝑡, 𝑑𝑏𝑀𝑎𝑐ℎ𝑖𝑛𝑒

[1] Hong Anh Le, and Ninh Thuan Truong. "Modeling and verifying DML triggers using event-B." Intelligent Information and
Database Systems. Springer Berlin Heidelberg, 2013. 539-548


12

S2B Translator
MACHINE dbMachine
SEES dbContext
VARIABLES
t1_rec
t2_rec
t1_pk
t2_pk
INVARIANTS
inv1 : t1_rec ∈ P(table1)
inv2 : t2_rec ∈ P(table2)
inv3 : t1_pk ∈ TYPE1 ⤖ TYPE2
inv4 : t1_pk ∈ TYPE3 ⤖ TYPE4
inv5 : I
EVENTS
Event G1 =
...
Event G2 =
...
END


A part of Event-B specification of database system


13

S2B Translator
 Trigger and event both have the form of an ECA (EventCondition-Action)
 A trigger is translated to an Event-B event:

TRIGGER <trigger_name>
<event>

EVENT <event_name>
WHEN
<event>

WHEN <conditions>
BEGIN

<conditions>
THEN

<actions>
END;

<actions>
END



14

S2B Translator
 Translation of trigger actions:
SQL

EVENT-B

INSERT INTO T
VALUES (value1, value2, … valuen)

ANY r
WHEN r ∈ T ∧ e ∧ c
THEN T := T ∪ r
END

DELETE FROM T
WHERE (column1 = some_value)

ANY v
WHEN v ∈ TYPE 1 ∧ e ∧ c
THEN T := {v} ⩤ T
END

UPDATE T
SET column1 = value1,
column2 = value2,…
WHERE (column1 = some_value)

ANY u

WHEN u ∈ T ∧ e ∧ c
THEN T := T ◁ u
END

⩤ : is domain subtraction operator

◁ : is relational override operator


S2B Translator

15

 In order to
•

decouple translation implementations form database model

•

Create a common API for all database elements

We apply visitor design pattern.
 Translation rules are implemented directly.


16

S2B Translator
// S2BTranslator.java

public void translateSchema(Schema database){

 Translating algorithm

rodinPrj = new RodinProject(database.getName());
preTranslate();
for (Table tbl : database.getTables()) {

Translate each table

translate(tbl);
}
for (Trigger trg : database.getTriggers()) {
translate(trg);

Translate each trigger

}
postTranslate();
}
public void translateTable(Table table){

Implementation of table translation

...
}
public void translateTrigger(Trigger trigger){

Implementation of trigger translation


...
}


17

Event-B Builder
 Functionality: export event-b models into a Rodin project.
 Rodin files are XML-base files.
 Using a template engine call StringTemplate to help
generating Rodin files.


18

Experiments
 Experiments

Generated Event-B project after imported into Rodin

S2B tool Parse
GUI Tree Inspector
Packages in S2B tool


19

Conclusion and future works
 Conclusion
o First step building successfully S2B tool.

o Partly support modelling database systems.

 Future works
o Expends translations rule
o Decouple rules into separated files.
o Support other DBMSs.


20

Thanks for listening.