This paper describes how materialized views could be used in distributed Real-Time Database Management System. We provide algorithm for dynamic materialized views building and cost evaluation. The main difference of provided method is that we take into account temporal properties of base relations and data manipulation operations. Experimental part provides algorithm which builds materialized view for given subset of physical query execution plans.
Real-time database management systems are the database management systems which can provide reliable queries execution in predictable time. Real-time databases use timing constraints to provide valid query results. Inability of conventional databases to work in such circumstances is the main reason to use real-time databases in a wide range of modern industrial applications.
The main are of our interests is the process control applications and using real-time database .management systems to store data for SCADA systems and they components. Modern real-time system should be able to store temporal data, handle time-critical queries, support priority scheduling and interact in dynamic environment. Our previous work was devoted to the scheduling policies in real-time database management systems. In this work we have concentrated on effective queries processing in distributed environment with some restrictions. The restrictions to the testing environment reflect some features of the commonly used computational system in the domain area we are interested in – process control.
Let us review the main features of the computational system which we are using in test environment: computational system is heterogeneous – hosts have different workload and different functions. There are 3 type of nodes – “server”, “sensor” and “user”; Our research area is placed in the intersection of different areas such as transactions processing, queries optimization, real-time databases, active and temporal database management systems. Common transaction handling aspects in Real-Time DBMS were considered in [1, 2, and 4]. Issues with Timing constraints were described in [3]. Work [5] describes commonly use optimization techniques. We have used some of these techniques in implementation of our query subsystem. Modern line of investigations in multi-query optimizations which used in materialized views support subsystem represented in [6]. Works [7] and [8] are concerned with queries processing which uses both conventional relations and materialized views to produce query result. Our work [9] and [10] describes real-time database management system prototype and transaction handling policies used in our experiments. In materialized views support system we have used elements of the lattice theory [11] to describe some properties of the materialized views support subsystem.
The materialized views management subsystem uses the following input information: query plans batch; source database structure; statistical information provided by main server database;
During subsystem initialization materialized views management subsystem transforms input query batch to internal format which helps to minimize execution and update costs. We use lattice representation based query batch as optimal structure for update traces. Internal representation contains mapping from physical query plan items to materialized data items and update support structure.
One of tasks is transformation from physical query plan to internal representation. Usually query execution plan represented by Directed Acyclic Graph (DAG). Formally query execution plan used in our experiments could be represented as follows:
G p Top , Op , Dp , Rp , (
Rp – arcs set which represents relations between nodes;
This model has the following restrictions: Operational nodes could be connected only with data nodes and data nodes could be connected only with operational nodes; Operational nodes have only one upcoming arc and one ore more incoming arcs (for conventional relation operations no more then 2 arcs) Data nodes can have no more then one upcoming and one incoming arc; Data nodes can represent not only conventional relations but also other data nodes like indexes or hashes; Here To ={Join, Union, Projection, Selection}, O = {Join(A,B), Join(AB,C)}, D = {A, B, C, AB, ABC},
R = {(A, Join(A,B)), (B, Join(A,B)), (Join(A,B), AB), (AB, Join(AB, C)), (C, Join(AB, C)), (Join(AB, C), ABC)}
A, B, С – source database relations and AB, ABC – results of the join operation.
Physical query execution plan in our subsystem is represented as
G pRT TpRT , O pRT , D pRT , R pRT , (
TpRT ={ScanSelect,
NestedLoopsIndexJoin, HashJoin}, a set of operational nodes types;
D RT d j, x : j 1, l, l D RT , x X RT p p OBJ (3) — data nodes set which represents the pair: data node index j and data object x which belongs to X RT OBJ all database objects;
o i, m, Ao : i 1, n, n O RT , O pRT m TpRT , p (4) Ao ao Axi | xi X ORBTJ — operational nodes set. Each node consists of node identifier, transaction type and set of attributes used in transaction execution;
R pRT r oi , d j : oi O pRT , d j D pRT r d j , oi : oi O pRT , d j D pRT (5) — set of relations between operational and data nodes. These relations are relations of consequence. Set RpRT represents ordering relationship and the G pRT model itself is partially ordered on consequence relation.
Query execution batch Query execution batch is represented as Pqueries G plans , Qqueries , RQP , (6) where Qqueries — a set of the parameterized queries which are used for quick access to the materialized results;
G plans
— set of query execution plans generated
for each query. Each query plan is represent as G p ,(
RQP rQP : rQP q, G p , q Qqueries , G p G plans — set of relations which represents mapping between initial query and appropriate subset of query execution plans.
During materialized views management system initialization query execution plans batch is transformed to the internal representation suitable for regular update in real-time mode. For this purpose query plan elements are sorted in and combined into single batch where elements are ordered by inclusion relation to minimize updates count. In our system materialized views batch is represented as lattice which is defined as:
L (V * , R ) , (6) where V * – lattice nodes set which corresponds to
R
– model signature which specifies ordering relationship on lattice nodes set.
This model should satisfy to the following restrictions [11]: model should have antireflexiveness property– a V * , a, a R (7); model should have asymmetric property a,b V , a,b R b, a R (8); a, b, c V , a, b R and b, c R model should have transitivity property (9); – – a, c R
Every node v* V * represents object which could be materialized. Each lattice node is based on query execution plan node and could be defined as follows: v* v', AV ,Ccost , X data , (10) where v' DPRT OPRT node from
G p G plans dependency between lattice node and query execution plan node is used during query evaluation.
– operational or data graph nodes set. This Ao , v' O RT AV P – aV | aV Ax, x X ORBTJ , v' DPRT database relation attributes set from the attributes to be materialized. Here Ao – set of attributes used in operational node for cases when this lattice node is based on operational nodes set. Ax – x relation schema, which is base relation for data node for cases when lattice node is based on data node of the query execution plan;
Ccost Creuse , Cupdate , Cretrieve – set of cost estimates for this materialized view node, where Creuse – cost of materialized view node reuse in cases if node will be materialized, Cupdate – data update cost for cases when node is materialized, Cretrieve – data retrieving cost for cases when node is not materialized and appropriate query is executed on main database server. These estimates could be enhanced but it was enough for our prototype;
X data x | x X ORBTJ –data relations set created for data materialization in this node. This set is empty for cases when data should not be materialized in current node. If this set is not empty it contains set of data objects which contains base operational nodes result.
Figure 2 represents internal materialized views representation generated by visualisation part of our lattice building test application
This part describes method used for transformation query execution plans batch to the internal materialized views representation. This method is based on building lattice using transitive closure for identifying base nodes.
Algorithm contains three main parts: Building generating sets. Each potential node has corresponding generating set which contains set of attributes used in operational or data node.
Building lattice which corresponds to rules (7), (8) and (9) Cost evaluation for each node and identifying nodes to be materialized.
Generative sets building algorithm
Let V *
materialized view set to be filled. At the first step this set is empty. Let 1.1 Build attributes set Ad A( x), x X ORBTJ , which is subset of the base relation schema.
v* v', AV , Ccost , X data where 1.2
v' d , AV Ad , X data
* Subroutine Add ( A , A )
V V 1. i 0 , n R 2. If i n , then move to the step 3, else move to the step 8 3. If ri rx, y : x A , then move to the step 4, V else move to the step 7 4. If y A* , then move to the step 9, else move to
V the step 5 5. z AV* y
* 6. If z A , then move to the step 9, else move to
V the step 7 7. i i 1 , move to the step 2 8. Add relation r A , A* to the R signature
V V
Let us review main iterative algorithm 1. i 0 , n V * 2. If i n , then move to the step 3, else move to the step 12 3. j 0 4. If j n , then move to the step 5, else move to 2. For each operational node o i, m, A O RT o P 2.1 Create node v* v' , AV , Ccos t , X data , where the step 11 5. AV* AVi AVj v' o , AV Ao , X data
3. Create node v , which has AV
AV vi* , i1, V * X data . This node represents structural unit – superset of all attributes.
As the result we have V * set, which is the basis for lattice building.
Lattice signature building algorithm AV vi* , vi* V * , i 1, n, n V *
Second step goal is to build lattice signature R which represents inclusion relation defined on V * set. This step contains consecutive pair wise intersection for sets.
If intersection result is not empty set then new set is used as new node in lattice. And this new node is added as base for two nodes used in intersection.
This algorithm could be divided into two parts: Subroutine which adds relation to the relation set and checks new relations to satisfy (7), (8) and (9) restrictions;
looked through.
Let us review add subroutine: set elements are
6. If AV* , then move to the step 7, else move to the step 10
7. If AVk AV* : AVk V * , then move to the step
10. j j 1, move to the step 4 11. i i 1 , move to the step 2 12. Exit
This algorithm is used to find the most frequently used nodes. But sometimes (for example in cases when there are not so much candidates to the materialization) we can use method less strict method. This enhances base set for cost estimation and could give us more efficient result for small lattice.
The algorithm for building additional nodes 1. Vc*urrent V * 2. If Vc*urrent 0 , then move to the step 3, else move to the step 17 3. i 0 , n Vc*urrent 4. If i n , then move to the step 5, else move to the step 16 5. j 0 6. If j n , then move to the step 7, else move to the step 15 7. AV* AVi AVj 8. If AV* , then move to the step 9, else move to the step 14
9. If AVk AV* : AVk Vc*urrent , the move to the step 12, else move to the step 10 10. Add AV* to the V * set 11. Add AV* to the Vn*ext set for the next iteration 12. Call Add( AVi , AVk ) 13. Call Add( AVj , AVk ) 14. j j 1, move to the step 6 15. i i 1 , move to the step 4 16. Vc*urrent Vn*ext , move to the step 2 17. Exit
This algorithm uses the same subroutine Add as previous algorithm.
Cost estimation for lattice nodes
We use iterative cost estimation method which evaluates cost for each node using optimal cost evaluation for base nodes. The criterion function is defined as F
minCost ' vq ,Tuse (11) vqVquery
Cost’ is subsequent query execution estimation and is defined as: Cost ' v, Tuse min C reuse X data Cupdate X data , Tuse , X data C retrieve X data , Tuse , X data (12)
v'V '
Cretrieve
minCost v' ,Tuse , (13) where V ' V * ,V ' v': r rv, v', r R – is set of node which are base nodes for current node.
Proposed materialized views model was used in distributed real-time database management system prototype for client transactions performance evaluation. For debugging and visual representation of the materialized views special demonstration program was developed which uses algorithms described in section 4 and builds picture represented in figure 2. Algorithms from section 4 were implemented both in real-time DBMS prototype and in test application.
In experimental investigation we plan to focus on 3 main directions: experiments with the test application which can visualize internal materialized views representation – this part needed to investigate various combinations of the query batches; set of experiments with transaction handling policies to verify what parameters should be used in “user” nodes and “server” nodes; set of experiments with different objects to be materialized – the main idea of this part is to investigate how temporary objects (such as temporary indexes and hashes) could be used to increase query processing effectiveness.
For now we have completed first part of experiments – building visual representation of the materialized views based on the user queries (you can see example picture in Figure 2).
As further work we consider performing experiments on rest two directions using implemented algorithms as part of the distributed database management system prototype. For now we have prepared test database which schema corresponds to the typical database used in process control.
Another direction of the further work is integration of the proposed algorithms to the commercial system which will provide database-like access to the OPCserver data with ability to transfer data to the mainstream database management systems. and Information Science and Engineering. Volume 1, Number 2, 2007 [9] A. V. Zharkov. Distributed Real-Time Database Management System Prototype for Transaction Handling Methods Simulation. In Proceedings of scientific and technical conference "Microsoft Technologies in Programming Theory and
Practice". N. Novgorod, 2007 [10] Zharkov A. Performance Evaluation of Transaction Handling Policies on Real-Time DBMS Prototype. Proceedings of the Fourth Spring Young Researcher's Colloquium on Database and Information Systems (SYRCoDIS'2007). Institute for System Programming of the Russian Academy of Sciences. Moscow, 2007. http://CEUR
WS.org/Vol-256/ [11] Birkhoff G. Lattice theory. Providence. Rhode Island. 1967