Haitham Yaish
email: haitham.yaish@student.uts.edu.au

Madhu Goyal

George Feuerlicht
email: george.feuerlicht@uts.edu.au

Proxy Service for Multi-tenant Database Access

Keywords: Software as a Service, SaaS, Multi-tenancy, Multi-tenant Database, Relational Tables, Virtual Relational Tables, Elastic Extension Tables

The database of multi-tenant Software as a Service (SaaS) applications has challenges in designing and developing a relational database for multi-tenant applications. In addition, combining relational tables and virtual relational tables to make them work together and act as one database for each single tenant is a hard and complex problem to solve. Based on our multi-tenant Elastic Extension Tables (EET), we are proposing in this paper a multi-tenant database proxy service to combine multitenant relational tables and virtual relational tables, to make them act as one database for each single tenant. This combined database is suitable to run with multi-tenant SaaS single instance applications, which allow tenants designing their database and automatically configuring its behavior during application runtime execution. In addition, these applications allow retrieving tenants data by simply calling functions from this service which spare tenants from spending money and efforts on writing SQL queries and backend data management codes, and instead allowing them to focus on their business and to create their web, mobile, and desktop applications. The feasibility and effectiveness of the proposed service are verified by using experimental data on some of this service functions.

Introduction

Configuration is the main characteristic of multi-tenant applications that allow SaaS vendors running a single instance application, which provides a means of configuration for multi-tenant applications. This characteristic requires a multi-tenant aware design with a single codebase and metadata capability. Multi-tenant aware application allows each tenant to design different parts of the application, and automatically adjust and configure its behavior during runtime execution without redeploy the application [START_REF] Bezemer | Multi-Tenant SaaS Applications: Maintenance Dream or Nightmare?[END_REF]. Multi-tenant data has two types: shared data, and tenant's isolated data. By combining these data together tenants can have a complete data which suits their business needs [START_REF] Domingo | CLOUDIO: A Cloud Computing-Oriented Multi-tenant Architecture for Business Information Systems[END_REF] [START_REF] Guoling | Research on Independent SaaS Platform[END_REF].

There are various models of multi-tenant database schema designs and techniques which have been studied and implemented to overcome multi-tenant database challenges [START_REF] Yaish | An Elastic Multi-tenant Database Schema for Software as a Service[END_REF]. Nevertheless, these techniques are still not overcoming multi-tenant database challenges [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF]. NoSQL stands for Not Only Structured Query Language, is a non-relational database management system. This technique avoids join operations, filtering on multiple properties, and filtering of data based on the results of a subqueris. Therefore, the efficiency of NoSQL simple query is very high, but this is not the case for complex queries [START_REF] Bobrowski | Optimal Multitenant Designs for Cloud Apps[END_REF][10] [START_REF] Dimovski | Database management as a cloud-based service for small and medium organizations[END_REF]. Salesforce.com [START_REF] Weissman | The design of the force.com multitenant internet application development platform[END_REF], the pioneer of SaaS Customer Relationship Management (CRM) applications has developed a storage model to manage its virtual database structure by using a set of metadata, universal data table, and pivot tables. Also, it provides a special object-oriented procedural programming language called Apex, and two special query languages: Sforce Object Query Language (SOQL) and Sforce Object Search Language (SOSL) to configure, control, and query the data from Salesforce.com storage model [9].

We have proposed a novel multi-tenant database schema design to create and configure multi-tenant applications, by introducing an Elastic Extension Tables (EET) which consists of Common Tenant Tables (CTT) and Virtual Extension Tables (VET) . The database design of EET technique is shown in the Appendix. This technique enables tenants creating and configuring their own virtual database schema including: the required number of tables and columns, the virtual database relationships for any of CTTs or VETs, and the suitable data types and constraints for a table columns during multi-tenant application run-time execution [START_REF] Yaish | An Elastic Multi-tenant Database Schema for Software as a Service[END_REF]. In this paper, we are proposing a multi-tenant database proxy service called Elastic Extension Tables Proxy Service (EETPS) to combine, generate, and execute tenants' queries by using a codebase solution that converts multi-tenant queries into a normal database queries.

Our EETPS provides the following new advancements:  Allowing tenants to choose from three database models. First, multi-tenant relational database. Second, combined multi-tenant relational database and virtual relational database. Third, virtual relational database.  Avoiding tenants from spending money and efforts on writing SQL queries, learning special programing languages, and writing backend data management codes by simply calling functions from our service which retrieves simple and complex queries including join operations, filtering on multiple properties, and filtering of data based on subqueries results. In our paper, we explored two sample algorithms for two functions of our service, and we carried out four types of experiments to verify the practicability of our service.

The rest of the paper is organized as follows: section 2 reviews related work. Section 3 describes Elastic Extension Tables Proxy Service, section 4 describes two sample algorithms of the Elastic Extension Tables Proxy Service, section 5 gives our experimental results and section 6 concludes this paper and descries the future work.

Related Work

There are various models of multi-tenant database schema designs and techniques which have been studied and implemented to overcome multi-tenant database challenges like Private Tables, Extension Tables, Universal [START_REF] Yaish | An Elastic Multi-tenant Database Schema for Software as a Service[END_REF]. Nevertheless, these techniques are still not overcoming multi-tenant database challenges [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF]. Salesforce.com, the pioneer of SaaS CRM applications has designed and developed a storage model to manage its virtual database structure by using a set of metadata, universal data table, and pivot tables which get converted to objects that the Universal Data Dictionary (UDD) keeps track of them, their fields and relationships, and other object definition characteristics. Also, it provides a special object-oriented procedural programming language called Apex which does the following. First, declare program variables, constants, and execute traditional flow control statements. Second, declare data manipulation operations. Third, declare the transaction control operations. Then Salesforce.com compiles Apex code and stores it as metadata in the UDD [START_REF] Weissman | The design of the force.com multitenant internet application development platform[END_REF]. In addition, it has its own Query Languages, first, Sforce Object Query Language (SOQL), which retrieve data from one object at a time. Second, Sforce Object Search Language (SOSL), which retrieve data from multiple objects simultaneously [9] [START_REF] Weissman | The design of the force.com multitenant internet application development platform[END_REF]. NOSQL is a non-relational database management system which designed to handle storing and retrieving large quantities of data without defining relationships. It has been used by cloud services like MongoDB, Cassandra, CouchDB, Google App Engine Datastore, and others. This technique avoids join operations, filtering on multiple properties, and filtering of data based on subqueries results. Therefore the efficiency of its simple query is very high, but this is not the case for complex queries. Moreover, unless configuring NoSQL consistency models in protective modes of operation, NoSQL will not assure the data consistency and it might sacrifice data performance and scalability [4][10]. Indrawan-Santiago [START_REF] Weissman | The design of the force.com multitenant internet application development platform[END_REF] states that NoSQL should be seen as a complimentary solution to relational databases in providing enhanced data management capability, not as a replacement to them.

Elastic Extension Tables Proxy Service

In this paper, we are proposing a multi-tenant database proxy service to combine, generate, and execute tenants' queries by using a codebase solution which converts multi-tenant queries into normal database queries. This service has two objectives, first, to enable tenants' applications retrieve tuples from CTTs, retrieve combined tuples from two or more tables of CTTs and VETs, or retrieve tuples from VETs. Second, to spare tenants from spending money and efforts on writing SQL queries and backend data management codes by simply calling functions from this service, which retrieves simple and complex queries including join operations, union operations, filtering on multiple properties, and filtering of data based on subqueries results. This service gives tenants the opportunity of satisfying their different business needs and requirements by choosing from any of the following three database models which are also shown in Fig. 1.  Multi-tenant relational database: This database model eligible tenants using a ready relational database structure for a particular business domain database without any need of extending on the existing database structure, and this business domain database can be shared between multiple tenants and differentiate between them by using a Tenant ID. This model can be applied to any business domain database like: CRM, Accounting, Human Resource (HR), or any other business domains.  Combined multi-tenant relational database and virtual relational database: This database model eligible tenants using a ready relational database structure of a particular business domain with the ability of extending on this relational database by adding more virtual database tables, and combine these tables with the existing database structure by creating virtual relationships between them.  Multi-tenant virtual relational database: This database model eligible tenants using their own configurable database through creating their virtual database structures from the scratch, by creating virtual database tables, virtual database relationships between the virtual tables, and other database constraints to satisfy their special business requirements for their business domain applications. The EETPS provides functions which allow tenants building their web, mobile, and desktop applications without the need of writing SQL queries and backend data management codes. Instead, retrieving their data by simply calling these functions, which return a two dimensional array (Object [] []), where  is the number of array rows that represents a number of retrieved tuples, and  is the number of array columns that represents a number of retrieved columns for a particular virtual table. These functions were designed and built to retrieve tenants' data from the following tables:

 One table either a CTT or a VET.

 Two tables which have one-to-one, one-to-many, many-to-many, or selfreferencing relationships. These relationships can be between two VETs, two CTTs, or one VET and one CTT.  Two tables which may have or not have relationships between them, by using different types of joins including: Left Join, Right Join, Inner Join, Outer Join, Left Excluding Join, Right Excluding Join, and Outer Excluding Join. The Join operation can be used between two VETs, two CTTs, or one VET and one CTT.  Two tables or more which may have or not have relationships between them, by using the union operator that combines the result-set of these tables whether they are CTTs or VETs.  Two or more tables which have relationships between them, by using filters on multiple tables, or filtering data based on the results of subqueries. Moreover, the EETPS functions have the capabilities of retrieving data from CTTs or VETs by using the following query options: Logical Operators, Arithmetic operators, Aggregate Functions, Mathematical functions, Using Single or Composite Primary Keys, Specifying Query SELECT clauses, Specifying Query WHERE Clause, Specifying Query Limit, and Retrieving BLOB and CLOB Values.

Sample Algorithms of the Elastic Extension Tables Proxy Service

In this section, two sample algorithms will be explored, Single Table Algorithm, and Union Tables Algorithm.

Single Table Algorithm

This algorithm retrieves tuples from a CTT or a VET. There are three different cases in this algorithm, first, retrieving tuples from a VET by specifying certain primary keys. Second, retrieving tuples from a VET by specifying certain table row IDs which are stored in 'table_row' extension table. Third, retrieving all tuples of a CTT or a VET. In this section we will explore the main algorithm and some of the subsidiary algorithms of the Single Table Algorithm including: the algorithm of the second case that mentioned in this paragraph, and Store Tuples in Array Algorithm. In addition, we will explore an example for each of these algorithms.

Single Table Main Algorithm. This main algorithm is outlined in Program Listing 1. The algorithm determines which of the three cases mentioned above will be applied by checking the passed parameters, and based on these parameters one of a three different query statement will be constructed, and then this query statement will be passed to 'getQuery' algorithm which will return SQL query results from 'table_row', 'table_row_blob', and 'table_row_clob' extension tables and store these results in a set. Then, this set will be passed to Store Tuples in Array Algorithm which will store the results in a two dimensional array, where the number of array rows represents a number of retrieved tuples, and the number of array columns represents a number of retrieved columns for a particular table.

Definition 1 (Single

Table Row

Query Algorithm. This subsidiary query algorithm is used to retrieve tuples for a tenant from a VET. The database query which is used in this algorithm uses UNION operator keyword to combine the result-set of three SELECT statements for three tables: table_row, table_row_blob, and table_row_clob if the VET only contains BLOB and/or CLOB, however if the VET does not contain BLOB and CLOB then the UNION operator will not be used in the query.

Definition 2 (Table Row Query Algorithm).

T denotes a tenant ID, B denotes a table name,  denotes a set of table row IDs, S denotes a string of the SELECT clause parameters, W denotes a string of the WHERE clause, F denotes a first result number of the query limit, M denotes the maximum amount of the query limit which will be retrieved, Q denotes the table type (CTT or VET), and  denotes a string of the select statement. , , S, W, F, M andQ Store Tuples in Array Algorithm. This subsidiary algorithm is used to store the retrieved data from a CTT or a VET into a two dimensional array, the number of array rows represents a number of retrieved tuples, and the number of array columns represents a number of retrieved columns for a table. The column names get stored in the first element of this two dimensional array, and the data in these columns get stored in the rest elements of the array.

Input. T, B,

Definitions 3 (Store Tuples in Array Algorithm

). T denotes a tenant ID, B denotes a table name,  denotes a set of retrieved tuples from a CTT or a VET where each of these tuples is presented as τ and each column of τ is presented as χ , which means τ is a set of χ where τ = { χ1, χ2, …, χn}. δ denotes a set of column names of a CTT or a VET,  denotes a two dimensional array to store the retrieved tuples, and τ n (χ m) denotes a value stored in χ m of τ n. Input. T, B, and . Output. .

Example. This example explores how the Single Table Algorithm retrieves virtual tuples from one VET.

There are three cases that this algorithm is handling which mentioned above in this section. In this example we will explore the case where we pass a certain table Row ID to the algorithm. In this example we will pass the following five input parameters: The two dimensional array that is shown in Fig. 2 (c) illustrates how the previous result which is shown in Fig. 2 (b) is stored in a well structured two dimensional array. The column names are stored in the first row elements, and the first tuple is stored in the second row elements of the array. Compared with the previous results of the tuples that is shown in Fig. 2 (b), this two dimensional array stores the virtual tuple in a structure which is very similar to any physical tuple that is structured in any physical database table, which in return will facilitate accessing virtual tuples from anyVET.

Union Tables Algorithm

In this section, we will explore the union function, which retrieves a combined result-set of two or more tables whether they are CTTs or VETs, and stores the resultset in an array. In addition, we will explore an example of this algorithm. The input parameters of this algorithm will determine a tenant, a set of CTTs and/or VETs that the union function needs to retrieve data from, SELECT clauses, and WHERE clauses which are required for each table. Program Listing 5 is showing the detailed algorithm. This algorithm will store the retrieved tuples in an array by using the subsidiary algorithm that mentioned in the Program Listings 3.

Definition 4 (Union Tables Algorithm).

T denotes a tenant ID,  denotes a set of CTTs and VET names, where each of these tables has got one or more tuples ( = { τ 1, τ 2, …, τ m}), each tuple is presented as τ and each column of τ is presented as χ, which means τ is a set of χ where τ = { χ1, χ2

Example. This example explores how the Union Table Algorithm retrieves tuples

from two tables, the first one CTT and the second one VET. In this example we will pass to the algorithm the following six input parameters:

1. A tenant ID value, which equals 1000. 2. A set of table IDs (  ) which equals {product, 17} where 'product' is a CTT that is shown in Fig. 3(a) and the ID 17 is the ID which represents the 'sales_fact' VET that is shown in Fig. 3

(b). 3. A set of table columns (  ), which equals {{shr_product_id, price}, {58,61}},

where this set contains two other sets, the first one contains the columns of 'product' CTT, and the second one contains the IDs of 'sales_fact' VET. ID 58 represents the virtual 'product_id' column and ID 61 represents the virtual 'unit_price' column. 4. The set of WHERE clauses of the tables (W) are empty, because this example has not got any WHERE clauses parameter passed to the function to filter the tables queries. 5. The first number of the query limits (F), which equals 0. 6. The maximum amount of the query limits (M), which equals 1.

After we passed the parameters to the function, the function iterated the set of tables (  ) , the first table in the set was 'product_id' CTT, the function executed the query which is shown in Program Listing 6 to retrieve the tuples of this table, and the results of this query are shown in Fig. 3 (c). The second table in the set was the 'sales_fact' VET with ID equals 17, the function executed the query in Program Listing 7 and 8. The query in Program Listing 7 was used to retrieve the indexes of the 'sales_fact' VET from 'table_index' extension table, and the query in Program Listing 8 was used to retrieve the virtual tuples from 'sales_fact' VET by using the passed parameters and the 'table_row_id' which were retrieved from the query that shown in Program Listing 7. The results of the two queries of Program Listing 7 and 8 are shown in Fig. 3 (d) and(e).

Finally, the output of the queries of the CTT and the VET that mentioned above are stored in two dimensional array as shown in Fig. 3 (f), the two elements [0] [0] and [0] [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF] represent the column names, the Union functions shows generic names like column1, and column 2, however the other functions which our service provides show column names of CTT and VET. The two elements [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF] [0] and [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF] [1] represent the column's values of the CTT, and the two elements [START_REF] Aulbach | Multitenant Databases for Software as a Service: Schema Mapping Techniques[END_REF] [0] and [START_REF] Aulbach | Multitenant Databases for Software as a Service: Schema Mapping Techniques[END_REF]

Performance Evaluation

After developing the EETPS, we carried out four types of experiments to verify the practicability of our service. These experiments were classified according to the complexities of the queries which used in these experiments including: simple, simple-to-medium, medium, and complex. The four experiments show comparisons between the response time of retrieving data from CTTs, VETs, or both CTTs and VETs. We have evaluated the response time through accessing the EETPS which converts multi-tenant queries into normal database queries, instead of accessing the database directly.

Experimental Data Set

The EETPS has designed and developed to serve multi-tenants in one instance application. However, in this paper the aim of the experiments is to evaluate the performance differences between retrieving the data of CTTs, VETs, or both CTTs and VETs together for one tenant. In our experiment settings we used one machine and we ran the following four types of experiments: In these four experiments we ran the test on eleven queries twice, the first test was to retrieve only 1 tuple, and the second test was to retrieve a 100 of tuples by using the same queries. The queries that we ran on CTTs are the same queries we ran on VETs, and CTT-and-VET in order to have accurate comparisons. The structures of these queries are shown in Fig. 4. We recorded the execution time of these queries experiments based on six data sets for all the four types of experiments that we ran. The first data set contained 500 tuples, the second data set contained 5,000 tuples, the third data set contained 10,000 tuples, the fourth data set contained 50,000 tuples, the fifth data set contained 100,000 tuples, and the last data set contained 200,000 tuples. All of these data sets were for one tenant.



Experimental Setup

Our EETPS was implemented in Java 1.6.0, Hibernate 4.0, and Spring 3.1.0. The database is PostgreSQL 8.4 and the application server is Jboss-5.0.0.CR2. Both of database and application server is deployed on the same PC. The operating system is windows 7 Home Premium, CPU is Intel Core i5 2.40GHz, the memory is 8GB, and the hard disk is 500G.

Experimental Results

In all the experimental diagrams we provided in this section the vertical axes which are the execution time in seconds, and the horizontal axes which are the total number of tuples that stored in a tenant's tables. Each of the four retrieves 1 tuple and 100 of tuples, and we will show in this section the average execution time of the six data sets of these tuples which are related to CTTs, VETs, and CTTs and VETs, and show the differences between them. These experimental diagrams are shown in Fig 5 -12.

We found in our experimental results that the average performance of the CTT and the VET for Exp.1 can be considered the same, and the VETs, the CTTs and the CTT-and-VET for Exp. 2 can be considered the same as well. In addition, we found that the average performance for Exp. 3 for the VETs, and the CTT-and-VET can be considered slightly higher than the CTTs, but the average performance of the VETs is the highest difference between the three types of tables. The average performance difference between the CTTs and the VETs for retrieving 1 tuple is 280 milliseconds, and for retrieving 100 tuples is 396 milliseconds. In the last experimental results Exp. 4 we found that the average performance for the CTT-and-VET can be considered higher than the CTTs by approximately 1.2 seconds, and for the VETs can be considered higher than the CTTs by approximately 1.5 seconds. The details of the experimental results summary are shown in Table 1 and2

Conclusion

In this paper, we are proposing a multi-tenant proxy service for the EET to combine, generate, and execute tenants' queries by using a codebase solution that converts a multi-tenant query into a normal database query. This service has two objectives, first, allowing tenants to choose from three database models: multi-tenant relational database, combined multi-tenant relational database and virtual relational database, and virtual relational database. Second, sparing tenants from spending money and efforts on writing SQL queries and backend data management codes by calling our service functions which retrieve simple and complex queries including join operations, filtering on multiple properties, and filtering of data based on subqueries results. In our paper, we explored two sample algorithms for two functions, and we carried out four types of experiments to verify the practicability of our service. These experiments were classified according to the complexities of the queries which used in these experiments including: simple, simple-to-medium, medium, and complex. The four experiments show comparisons between the response time of retrieving data from CTTs, VETs, or both CTTs and VETs. In our experimental results we found that the average performance of CTTs, VETs, and CTT-and-VET for the simple queries and the simple-to-medium queries are considered almost the same. Also, we found that the average performance of the medium queries for VETs, and CTT-and-VET is considered slightly higher than CTTs, but VET are the highest between the three types of tables. In the last experimental results of complex query we found that the average performance for CTT-and-VET is considered higher than CTTs by approximately 1.2 seconds, and for VETs is considered higher than CTTs by approximately 1.5 seconds. The cost of complex query is acceptable in favor of obtaining a combined relational database and virtual relational database for multi-tenant applications, which in return these combined databases provide a means of configuration for multi-tenant applications, reduce the Total Cost of Ownership (TCO) on the tenants, and reduce the ongoing operational costs on the service providers.

Our future work will focus on optimizing virtual data retrieval from our EET for simple and complex queries by using a highly-optimized executing query plans and logic, and add more functions to insert, updated, delete tuples from CTT and VET.

Fig. 1 .

 1 Fig. 1. EETPS database models.

  . Output. . 1.  = SELECT tr.table_column_name, tr.value, tr.table_row_id, tr.serial_id FROM table_row tr WHERE tr.tenant_id = T AND tr.db_table_id = B AND tr.table_row_id IN () AND table_column_id in (S) AND W UNION SELECT trb.table_column_name, trb.value, trb.table_row_blob_id,trb.serial_id FROM table_row_blob trb WHERE trb.tenant_id = T AND trb.db_table_id = B AND trb.table_row_blob_id IN () UNION SELECT trc.table_column_name, trc.value, trc.table_row_clob_id, trc.serial_id FROM table_row_clob trc WHERE trc.tenant_id = T AND trc.db_table_id = B AND trc.table_row_clob_id IN () ORDER BY 3, 4 LIMIT M OFFSET F 2. Return  2 The program listings of Table Row Query Algorithm.

  SELECT tr.table_column_name, tr.value, tr.table_row_id, tr.serial_id FROM table_row tr WHERE tr.tenant_id = 100 AND tr.db_table_id = 7 AND trb.table_row_id IN (2) 4 The Program Listing of the query generated by using the Single Table Algorithm

  .

Fig. 2 .

 2 Fig. 2. The 'store' VET and some tuples retrieved from it and stored in an array.

  [START_REF] Aulbach | A Comparison of Flexible Schemas for Software as a Service[END_REF] represent the column's values of the VET.SELECTproduct_id, price FROM product WHERE tenant_id = 1000 LIMIT 1; SELECT tr.table_column_id ,tr.value ,tr.table_row_id, tr.serial_id FROM table_row tr WHERE tr.tenant_id =1000 AND tr.db_table_id = 17 AND tr.table_row_id IN (352871) AND tr.table_column_id in (58,61) ORDER BY 3,4 LIMIT 2 OFFSET 0 8 The program listing of the query which retrieved the tuples of the 'sales_fact' VET.

Fig. 3 .

 3 Fig. 3. The 'product' CTT and the 'sales_fact' VET data structures.

Fig. 4 .

 4 Fig. 4. The structures of the queries executed in our experiments.

Fig. 7 . 1 Fig. 10 .

 7110 Fig. 7. 1-to-M 1 Tuple

Fig. 11 .

 11 Fig. 11. Left Join 1 Tuple

Fig. 12 .

 12 Fig. 12. Left Join 100 Tuples

  Table Main Algorithm). T denotes a tenant ID, B denotes a table name,  denotes a set of tablerowIDs,  denotes a set of primary keys, S denotes a string of the SELECT clause parameters, W denotes a string of the WHERE clause, F denotes a first result number of a query limit, M denotes the maximum amount of a query limit which will be retrieved, Q denotes the table type

	1. if Q = CTT then
	2.	C ← retrieve tuples from a CTT by using T, , S,
		W, F, and M to filter the query results
	3. else
	4.	if  ≠ null then
	5.	V ← retrieve tuples from a VET by using T, , S,
		W, F,	and M to filter the query results
	6.	else if  ≠ null then
	7. /* This statement calls Table Row Query Algorithm */
	8.	V ← retrieve tuples from a VET by using T, , S,
		W, F, and M to filter the query results
	9.	else
	10.	I ← retrieve the indexes of B by using ta-
		ble_index extension table
	11. end if
	12. if B has I then
	13.	V ← retrieve tuples from a VET by using T, I,
		S, W, F, and M to filter the query results
	14.	else
	15.	V ← retrieve tuples from a VET by using T, S,
		W, F, and M to filter the query results
	16.	end if
	17. end if
	18. /* This statement calls Store Tuples in Array Algo-
	rithm */
	19. store C or V in 
	20. Return 

(CTT or VET), I denotes a set of VET indexes, C denotes a set of retrieved tuples from a CTT, V denotes a set of retrieved tuples from a VET, and  denotes a two dimensional array that stores the retrieved tuples.

1

The program listings of Single Table Algorithm.

  1. δ ← retrieve the column names of B from table_column extension table by using T to filter the query results 2. Initialize  [size of ] [size of δ] The program listings of Store Tuples in Array Algorithm.

	3. i ← 0
	4. For all column names	δ Do
	5.	 [0][i] = δi
	6.	i ← i + 1
	7. end for
	8. n ← 0
	9. for all τ	 Do
	10. m ← 0
	11. For all column names	δ Do
	12.	 [n+1][m] = τ n(χ m)
	13.	m ← m + 1
	14. end for
	15. n ← n + 1
	16.end for
	17.Return 

3

  1. A tenant ID value, which equals 100. 2. A table ID value, which equals 7. 3. A table row ID value, which equals 2. 4. The SELECT clause parameter (S) is empty, this means that the query will retrieve all the columns of the 'store' VET. 5. The WHERE clause (W) is empty, this means that the query is not filtered by the WHERE clause. Fig. 2 (a) shows the 'store' VET which we will retrieve tuples from. The query in Program Listing 4 is generated by using the Single Table Algorithm to retrieve a virtual tuple from the 'store' VET based on the passed parameters. Fig. 2 (b) shows the result of the virtual tuples that retrieved from table_row extension table by using this query listed in Program Listing 4. This virtual tuple is divided into three physical tuples, each of these physical tuples stores a column name and its value, and all of these tuples are sharing one 'table_row_id' which equals 2. The query in Program Listing 4 does not contain the UNION part of the query to retrieve BLOB and CLOB values because the 'store' VET structure does not contain any of them.

  , …, χn}.  denotes a set of table columns which are related to the set  and the columns are ordered according to the table orders, W denotes a set of WHERE clauses which are related to the set  and the columns are ordered according to the table orders of , F denotes a first result number of a query limit, M denotes a maximum amount of a query limit which will be retrieved, Q denotes the table type (CTT or VET), C denotes a set of retrieved tuples from CTT, V denotes a set of retrieved tuples from VET,  denotes a two dimensional array which stores the retrieved tuples, and τ n (χ m) denotes a value stored in χ m of τ n.

	Input. T, , , W, F, and M.
	Output. .
	1. i ← 0
	2. For all tables	 Do
	3.	if Q = CTT then
	4.	C ← retrieve τ from a CTT by using , W, F, and M
		to filter the query results
	5.	else
	6.	V ← retrieve tuples from a VET by using , W, F,
		and (M * size of ) to filter the query results
	7.	end if
	8.	n ← 0
	9.	for all τ	i Do
	10.	m ← 0
	11.	For all column names	τ Do
	12.	[n+1][m] = τ n(χ m)
	13.	m ← m + 1
	14.	end for
	15.	n ← n + 1
	16. end for
	17. i ← i + 1
	18.end for
	19.Return 

5

The program listings of Union Tables Algorithm.

  Simple query experiment (Exp. 1): In this experiment we called a function which retrieved data from a CTT by executing Query 1 (Q1), and retrieved the same data from a VET by executing Query 2 (Q2).  Simple-to-medium query experiment (Exp. 2): In this experiment we called a function which retrieved data from two CTTs by executing Query 3 (Q3), two VETs by executing Query 4 (Q4), and CTT-and-VET by executing Query 5 (Q5). Each of these two tables combination has got one-to-many relationship between them.  Medium query experiment (Exp. 3): In this experiment we called a function which retrieved data from two tables by using a union operator for two CTTs by executing Query 6 (Q6), for two VETs by executing Query 7 (Q7), and for CTTand-VET by executing Query 8 (Q8).  Complex query experiment (Exp. 4): In this experiment we called a function which uses a left join operator that joined two CTTs by executing Query 9 (Q9), two VETs by executing Query 10 (Q10), and CTT-and-VET by Query 11 (Q11).

Table 1 .

 1 . This table shows the experimental results of retrieving 1 tuple in milliseconds.

	Retrieving	CTT VET CTT-and-	Difference Between	Difference Between
	1 Tuple		VET	CTT-and-VET	CTT and CTT-and-VET
	Exp. 1	Q 1 Q 2
		117 161		44
	Exp. 2	Q 3 Q 4	Q 5
		146 155	149	9	3
	Exp. 3	Q 6 Q 7	Q 8
		231 511	340	280	109
	Exp. 4	Q 9 Q 10 Q 11
		403 1930 1632	1527	1229

Table 2 .

 2 This table shows the experimental results of retrieving 100 tuples in milliseconds.

	Retrieving	CTT VET CTT-and-	Difference Between	Difference Between
	100 Tuples			VET	CTT-and-VET	CTT and CTT-and-VET
	Exp. 1	Q 1	Q 2
		204	206		2
	Exp. 2	Q 3	Q 4	Q 5
		331	355	343	24	12
	Exp. 3	Q 6	Q 7	Q 8
		245	641	388	396	143
	Exp. 4	Q 9	Q 10 Q 11
		560	2112 1856	1552	1296

Number of Tenant's Tuples

Input.T, B, , , S, W, F, M and Q. Output. .

The program listing of the query which retrieved the tuples of the 'product' CTT.SELECTtable_row_id FROM table_index WHERE ten-ant_id=1000 AND db_table_id=17 AND (table_column_id=61 OR table_column_id=58) LIMIT 1

[START_REF] Du | Research on Data Layer Structure of Multi-tenant Ecommerce System[END_REF] The program listing of the query which retrieved the indexes of the 'sales_fact' VET from 'table_index' extension table.


Alain Casali
email: alain.casali@lif.univ-mrs.fr

Christian Ernst
email: ernst@emse.fr

Extracting Correlated Patterns on Multicore Architectures

In this paper, we present a new approach relevant to the discovery of correlated patterns, based on the use of multicore architectures. Our work rests on a full KDD system and allows one to extract Decision Correlation Rules based on the Chi-squared criterion that include a target column from any database. To achieve this objective, we use a levelwise algorithm as well as contingency vectors, an alternate and more powerful representation of contingency tables, in order to prune the search space. The goal is to parallelize the processing associated with the extraction of relevant rules. The parallelization invokes the PPL (Parallel Patterns Library), which allows a simultaneous access to the whole available cores / processors on modern computers. We finally present first results on the reached performance gains.

Introduction and Motivation

In the past couple of years, innovations in hardware architecture, like hyperthreading capabilities or multicore processors, have begun to allow parallel computing on inexpensive desktop computers. This is significant in that standard software products will soon be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing (the main area for parallel computing). Consequently, there is a growing interest in the research field of parallel data mining algorithms, especially in association rules mining (ARM). By exploiting multicore architectures, parallel algorithms may improve both execution time and memory requirement issues, the main objectives of the data mining field.

Independently of this framework, we soon developed a KDD system based on the discovery of Decision Correlation Rules with large and specialized databases (Casali and Ernst,1). These rules are functional in semiconductor fabrication capabilities. The goal is to discover the parameters that have the most impact on a specific parameter, the yield of a given product ... Decision Correlation Rules (DCRs) are similar to Association Rules. But, as it will be shown, there are huge technical differences, and the overall computation times of DCRs are in the end much better. Furthermore, after implementing DCRs using "conventional sequential algorithms", we decided to adapt this approach to multicore implementation possibilities. This paper is organized as follows. In Section 2, we recall current features of multicore programming. Section 3 is dedicated to related work: we present (i) an overview of Association Rules Mining over a multicore architecture and (ii) what Decisional Correlation Rules are. Section 4 describes the concepts used for multicore decision rules mining and our algorithm. In Section 5 we show the results of first experiments. Finally, in the final Section, we summarize our contribution and outline some research perspectives.

Recent advances in multicore programmation

Multicore processing is not a new concept, however only recently has the technology has become mainstream with Intel or AMD introducing commercially available multicore chips in 2008. At that date, no software environment able to take advantage simultaneously of the different existing processors had been proposed, let alone produced for the commercial market.

The situation radically changed in 2010. We present in this section these new opportunities, showing the covered aspects in the C++ language used in our developments. We first introduce what the approaches towards parallelization were until only a few years ago. We then present quickly the Lambda Calculus, a new programming paradigm integrated into the last C++ norm and essential to understand multicore prorammation. And we finally expose the PPL environment, which allows effective multicore programmation in a simple way.

Parallelization issues on modern desktop computers

For about twenty years, parallelizing tasks on personal computers consisted essentially in the development of multithreaded code, by adding or not higher abstraction levels on the base threaded layers. This often required complex coordination of threads, and introduced difficulties in finding bugs due to the interweaving of processing of data shared between the threads. Although threaded applications added limited amounts of performance on single-processor machines, the extra overhead of development was difficult to justify on the same machines.

But given the increasing emphasis on multicore chip architectures, developers unable to design software to fully exploit the resources provided by multiple cores will now quickly reach performance ceilings.

Multicore processing has thus affected the ability of actual computational software development. Many modern languages do not support multicore functionality. This requires the use of specialized libraries to access code written in languages such as C. There are different conceptual models to deal with the problem, for example using a coordination language and program building blocks (programming libraries and/or higher order functions). Each block may have a different native implementation for each processor type. Users simply program using these abstractions, and an intelligent compiler then chooses the best implementation based on the context (Darlington,2).

Many parallel programming models have been recently proposed (Cilk++, OpenMP, OpenHMPP, ...) for use on multicore platforms. Intel introduced a new abstraction for C++ parallelism called TBB. Former and more organization oriented research efforts include the Codeplay Sieve System, Cray's Chapel, Sun's Fortress, and IBM's X10. A comparison of some OpenXXX approaches can be found in (Hamidouche and al.,3).

But the majority of these models roughly bases on the intelligent transformation of general code into multithreaded code. A new, even if simple idea, has been proposed by the OpenMP consortium in FORTRAN in 1997, based on the fact that looping functions are the key area where splitting parts of a loop across all available hardware resources may increase application performance. The Open Multiprocessing Architecture Review Board (or OpenMP ARB) became an API that supports shared memory multiprocessing programming in C++. It consists of a set of compiler directives, library routines, and environment variables that influence run-time behavior. In order to schedule a loop across multiple threads, the OpenMP pragma directives were introduced in 2005 to explicitly relay to the compiler more about the transformations and optimizations that should take place. The example chosen to illustrate our purposes is the computation of the sum of an integer vector: vector<int> v = ...; int sum = 0; #pragma omp for for (int i = 0; i < v.size(); i++) { #pragma omp atomic sum += v[i]; }

The first directive requests that the for loop should be executed on multiple threads, while the second is used to prevent multiple simultaneous writes to the sum variable ... This approach has then be adapted to multicore programmation, as illustrated hereafter. Let us previously underline that parallelism also has its limits. It is widely admitted that applications that may benefit from using more than one processor necessitate (i) operations that require substantial amount of processor time, measured in seconds (or larger denominations) rather than milliseconds and (ii) one or more loops of some kind, or operations that can be divided into discrete but significant units of calculation that can be executed independently of one another.

A new programming paradigm: the Lambda Calculus

The example above without parallelization issues can be re-written as follows: vector<int> v = ...; int sum = 0; for (int i = 0; i < v.size(); i++){ sum += v[i]; } A declarative looping technique generalized the syntax for STL containers: the for each function has been introduced in a first C++ 0x draft, so the code can be re-written in: vector<int> v = ...; int sum = for_each(v.begin(), v.end(), Adder());

The third argument is a functor: a class overloading the () operator. In our example, the functor has to perform the addition. This approach did not result in much success for many reasons, the two main of which include: (i ) developers must implement the functor, but defining a whole class in order to finally execute a single instruction is a bit verbose; (ii ) using a named function is sub-optimal because confusion may arise with the "C" pointer function syntax.

Recognizing these shortcomings, the C++ draft provided a simplified syntax based on Lambda functions. The associated formalism is a computational model invented by Alonzo Church in the 1930s, which directly inspired both the syntax and the semantics of most functional programming languages (Mitchell,4). The basic concept of the λ calculus is the "expression", recursively defined as follows:

<expression>:= <name>-<function>-<application> <function>:= λ <name>.<expression> <application>:= <expression><expression> The λ calculus in its most basic form has two operations: (i) Abstractions, which correspond to anonymous functions, and (ii) Applications, which exist to apply the function. Abstraction is performed using the λ operator, giving the lambda calculus its name. Anonymous functions are often called "lambdas", "lambda functions" or "lambda expressions": these remove all the need for the scaffolding code, and allow a predicate function to be defined in-line in another statement. The current example can thus be re-written as follows:

vector<int> v = ...; int sum = 0; for_each(v.begin(), v.end(),[&sum](int x) {sum += x;} );
The syntax of a lambda function is reasonably straight-forward, of the form:

[lambda-capture] (parameter-list) {->} return-type {statement-list}

In the example, the first element of the lambda in the square brackets is called the capture specification: it relays to the compiler that a lambda function is being created and that the local variable sum is being captured by reference. The final part is the function body.

Therefore, lambdas behave like function objects, except for we cannot access the class that is generated to implement a lambda in any way other than using the lambda. Consequently, any function that accepts functors as arguments will accept lambdas, but any function only accepting function pointers will not.

These and much more features of lambda functions have been included in the C++11 language norm, allowing a more declarative programming style, taking advantage of (STL) algorithms in a much simpler and cleaner form. Lambda functions allow the inline definition of a function body in the code section in which it is to be logically used. As well as providing strong hints to the compiler about potential real time optimizations, lambda functions make discerning the intent about what a section of code is doing much easier.

Multicore programmation using the PPL

In a different way than the OpenMP consortium, Microsoft developed its own "parallel" approach in the 2000s within an internal work group called Parallel Extensions. Since 2010, and the relevant versions of the .NET framework and Visual Studio, Microsoft enhanced support for parallel programming by providing a runtime tool and a class library among other utilities. The library is composed of two parts: Parallel LINQ (PLINQ), a concurrent query execution engine, and Task Parallel Library (TPL), a task parallelism component of the .NET framework. This component hides entirely the multi-threading activity on the cores: the job of spawning and terminating threads, as well as scaling the number of threads according to the number of available cores, is done by the library itself. The main concept is here a Task, which can be executed independently.

The Parallel Patterns Library (PPL) is the corresponding available tool in the Visual C++ environment, and is defined within the Concurrency namespace. The PPL operates on small units of work (Tasks), each of them being defined by a λ calculus expression. The PPL defines almost three kinds of facilities for parallel processing: (i) templates for algorithms for parallel operations, (ii) class templates for managing shared resources, and (iii) class templates for managing and grouping parallel tasks.

The library provides essentially three algorithms defined as templates for initiating parallel execution on multiple cores:

-The parallel for algorithm is the equivalent of a for loop that executes loop iteration in parallel, -The parallel for each algorithm executes repeated operations on a STL container in parallel,

-The parallel invoke algorithm executes a set of two or more independent Tasks in parallel, in the sense of different programs within the same runtime environment.

Our current example re-written using parallel capabilities: vector<int> v = ...; int sum = 0; parallel_for_each(v.begin(), v.end(), [&sum](int x) { // make sure <sum> is shared between the "cores"... sum += x; } );

Let us underline again that if the computation on each iteration is very short, there will be inevitably important overhead in allocating the task to a core on each iteration. Which may severely erode any reduction in execution times. This will also be the case if the overall loop integrates important shared resources management, as will be shown in Section 4. This means that upgrading from sequential to parallel computing must be done very carefully.

Related Work

Due to the variety of the algorithms (and their specific internal data structures) there does not exist any general model allowing parallel ARM computation. Main techniques are described in Section 3.1. They just are actual models optimized for the usage of multicore architecture. Developers have to write their own thread managers (Herlihy and Shavit,5). Section 3.2 presents the main results about what Decision Correlation Rules are and how can we compute them using a single processor.

Association Rules Mining using Multicore Support

Current research can be divided into three main categories: (i) adaptation of the A-Priori algorithm, (ii) vertical mining, and (iii) pattern-growth method.

A-Priori based algorithms: Most of the parallel ARM algorithms are based on parallelization of A-Priori (Agrawal and Srikant,6) that iteratively generates and tests candidate itemsets from length 1 to k until no more frequent itemsets are found. These algorithms can be categorized into Count Distribution, Data Distribution and Candidate Distribution methods (Agrawal and Shafer, 7), ( Han and Kamber,8). The Count Distribution method partitions the database into horizontal partitions, that are independently scanned, in order to obtain the local counts of all candidate on each process. At the end of each iteration, the local counts are summed up a into the global counts so that frequent itemsets can be found. The Data Distribution method utilizes the main memory of parallel machines by partitioning both the database and the candidate itemsets. Since each candidate is counted by only one process, all processes have to exchange database partitions during each iteration in order, for each process, to obtain the global counts of the assigned candidate itemsets. The Candidate Distribution method also partitions candidate itemsets but replicates, instead of partition and exchanging, the database transactions. Thus, each process can proceed independently.

Vertical mining: To better utilize the aggregate computing resources of parallel machines, a localized algorithm (Zaki et. al,9) based on parallelization of Eclat was proposed and exhibited excellent scalability. It makes use of a vertical data layout by transforming the horizontal database transactions into vertical tidlists of itemsets. By 1-item, the tid-list of an itemset is a sorted list of IDs for all transactions which contain the 1-itemset. Frequent k-itemsets are organized into disjoint equivalence classes by common (k -1)-prefixes, so that candidate (k +1)-itemsets can be generated by joining pairs of frequent k-itemsets from the same classes. The support of a candidate itemset can then be computed simply by intersecting the tid-lists of the two component subsets. Task parallelism is employed by dividing the mining tasks for different classes of itemsets among the available processes. The equivalence classes of all frequent 2-itemsets are assigned to processes and the associated tid-lists are distributed accordingly. Each process then mines frequent itemsets generated from its assigned equivalence classes independently, by scanning and intersecting the local tid-lists.

Pattern-Growth Method: The pattern-growth method derives frequent itemsets directly from the database without the costly generation and test of a large number of candidate itemsets. The detailed design is explained in the FP-growth algorithm (Han et al.,10). Basically, it makes use of a frequent-pattern tree structure (FP-tree) where the repetitive transactions are compacted. Transaction itemsets are organized in that frequency-ordered prefix tree such that they share common prefix part as much as possible, and re-occurrences of items/itemsets are automatically counted. Then the FP-tree is pruned to mine all frequent patterns (itemsets). A partitioning-based, divide and conquer strategy is used to decompose the mining task into a set of smaller sub-tasks for mining confined patterns in the so-called conditional pattern bases. The conditional pattern base for each item is simply a small database of counted patterns that co-occur with the item. That small database is transformed into a conditional FP-tree that can be processed recursively (Zaiane et al., 11, Pramudiono and Kitsuregawa 12, Li and Liu 13).

Decision Correlation Rules

Brin et al. ( 14) have proposed the extraction of correlation rules. The platform is no longer based on the support nor the confidence of the rules, but on the Chi-Squared statistical measure, written χ 2 . The use of χ 2 is well-suited for several reasons: (i) it is a more significant measure in a statistical way than an association rule, (ii) the measure takes into account not only the presence but also the absence of the items and (iii) the measure is non-directional, and can thus highlight more complex existing links than a "simple" implication. Unlike association rules, a correlation rule is not represented by an implication but by the patterns for which the value of the χ 2 function is larger than or equal to a given threshold.

Let r be a binary relation over a set of items R = I ∪ T . I represents the items of the binary relation used as analysis criteria and T is a target attribute. For a given transaction, the target attribute does not necessarily have a value. The computation of the value for the χ 2 function for an item X ⊆ R is based on its contingency table. In order to simplify the notation, we introduce, in a first step, the lattice of the literalsets associated with X ⊆ R. This set contains all the literalsets that can be built up given X, and having |X|.

Definition 1 (Literalset Lattice). Let X ⊆ R be a pattern, we denote by P(X) the literalset lattice associated with X. This set is defined as follows:

P(X) = {Y Z such that X = Y ∪ Z and Y ∩ Z = ∅} = {Y Z such that Y ⊆ X and Z = X\Y }.
Definition 2 (Contingency Table ). For a given pattern X, its contingency table, noted CT (X), contains exactly 2 |X| cells. Each cell yields the support of a literalset Y Z belonging to the literalset lattice associated with X: the number of transactions including Y and containing no 1-item of Z.

In order to compute the value of the χ 2 function for a pattern X, for each item Y Z belonging to its literalset lattice, we measure the difference between the square of the support of Y Z and its expectation value (E(Y Z)), and divide by the average of Y Z (E(Y Z)). Finally, all these values are summed.

χ 2 (X) = Y Z∈P(X) (Supp(Y Z) -E(Y Z)) 2 E(Y Z) , (1)
Brin et al. ( 14) have shown that there is a single degree of freedom between the items. A table giving the centile values in function of the χ 2 value for X can be used in order to obtain the correlation rate for X. Definition 3 (Correlation Rule). Let M inCor (≥ 0) be a threshold given by the end-user and X ⊆ R a pattern. If χ 2 (X) ≥ M inCor, then X is a valid correlation rule. If X contains an item of T , then the obtained rule is called a Decision Correlation Rule (DCR).

Moreover, in addition to the previous constraint, the Cochran criteria (Moore,15) is used to evaluate whether a correlation rule is semantically valid: all literalsets of a contingency table must have an expectation value not equal to zero and 80% of them must have a support larger than 5% of the whole population.

This last criterium has been generalized by Brin et al. (14) as follows: M inP erc of the literalsets of a contingency table must have a support larger than M inSup, where M inP erc and M inSup are thresholds specified by the user. Definition 5 (Contingency Vector). Let X ⊆ R be a pattern. The contingency vector of X, denoted CV (X), groups the set of the literalset equivalence classes belonging to P(X) ordered according to the lectic order.

Since the union of the equivalence classes [Y Z] of the literalset lattice associated with X is a partition of the TIds, we ensure that a single transaction identifier belongs only to one single equivalence class. Consequently, for a given pattern X, its contingency vector is an exact representation of its contingency table. To derive the contingency table from a contingency vector, it is sufficient to compute the cardinality of each of its equivalence classes. If the literalsets, related to the equivalence classes of a CV , are ordered according to the lectic order, it is possible to know, because of the binary coding used, the literal relative to a position i of a contingency vector (i ∈ [0; |X| -1]). This is because the literal and the integer i have the same binary coding. The following proposition shows how to compute the CV of the X ∪ A pattern given the CV of X and the set of identifiers of the relation containing pattern A.

Proposition 1. Let X ⊆ R be a pattern and A ∈ R\X a 1-item. The contingency vector of the X ∪ A pattern can be computed given the contingency vectors of X and A as follows:

CV (X ∪ A) = (CV (X) ∩ [A]) ∪ (CV (X) ∩ [A]) (2)
In order to mine DCRs, we have proposed in (Casali and Ernst,1) the LHS-Chi2 algorithm (see Alg. 1 for a simplified version). This algorithm is based both (i) on a double recursion in order to browse the search space according to the lectic order and (ii) on CVs.

The CREATE_CV function is used, given the contingency vector of a pattern X and the set of the transaction identifiers containing a 1-item A, to build the contingency vector of the pattern X ∪ A. The CtPerc predicate checks the relaxed Cochran criteria.

Extracting Correlated Patterns in Parallel

As it is easy to apprehend when regarding last section, the use of a recursive algorithm in a multicore programming environment is an effective challenge. This Alg. 1 LHS-Chi2 Algorithm.

Input: X and Y two patterns

Output: {itemset Z ⊆ X such that χ 2 (Z) ≥ M inCor} 1: if Y = ∅ and |X| ≥ 2 and ∃t ∈ T : t ∈ X and χ 2 (X) ≥ M inCor then 2: Output X, χ 2 (X) 3: end if 4: A := max(Y ) 5: Y := Y \{A} 6: LHS-Chi2(X,Y) 7: Z := X ∪ {A} 8: VC(Z) := CREATE CV(CV(X),Tid(A)) 9: if CtP erc(CV (Z), M inP erc, M inSup) then 10:
LHS-Chi2(Z,Y) 11: end if because recursion cannot be measured in terms of number of loops to perform. However, parallelizing existing algorithms is an important consideration as well. We first tried to replace the recursive calls by calls to appropriate threads, which quickly appeared as an impossible solution. Another possible approach was based on the well known fact that each recursive algorithm can be rewritten in a iterative format. However, the while loop used to run over the used stack may not be evaluated in terms of a for loop due to the absence of explicit boundaries.

Finally, and in order to solution the problem, we recalled that we first compared our LHS-Chi2 algorithm to a Levelwise one, based on the same monotone and anti-monotone constraints but which did not include Contingency Vectors management. The main reason of the obtained performance gains is that pruning the search space using the lectic order is much more elegant than using the Levelwise order but has no impact nor on the results nor on the performances. On the other hand, generating the candidates at a given level is a bounded task, limited by the number of existing 1-items. This is why we decided to go back to the Levelwise order to prune in a parallel way the search space, and to keep the Contingency Vectors in order to manage the constraints.

The corresponding result is presented hereafter in the form of three functions. The overall algorithm, called PLW Chi2 (where PLW stands for Parallel Levelwise), demonstrates the parallel features of our method. The second function dowork level constitutes each single Task executed in parallel. Finally, a particular aspect of such a Task is detailed in a third function, associated to specific shared resource management issues. We first present these functions through simplified code and comment them in a second stage. void PLW_Chi2 (unsigned short X[], unsigned short sX, unsigned short sI) // X[] : set of computed 1-items // sX : number of valid 1-items within X[] // sI : total number of 1-items in X[] { unsigned long cit, nit; // number of candidates at level l and (l+1) cit = sX; for (unsigned char curlev = 2; curlev <= MaxLv && cit > 0; curlev++) { nit = 0L; T_Res aRes; combinable<unsigned long> lnit; parallel_for(0u, (unsigned) cit, [curlev, X, sX, &aRes, &lnit] (int i) { dowork_level (curlev, X, sX, i, sI, &aRes); lnit.local() += aRes.nit; // ... }); nit = lnit.combine(plus<unsigned long>()); // ... cit = nit; update_shared_resources (); } } Parallelization takes place at each level (curlev variable) of the Levelwise search algorithm. The number of launched Tasks at level l directly depends of the number of existing candidates at level (l -1), e.g. cit. Each Task corresponds principally to a call to the dowork level function, which performs the work it is intended to do, and collects some statistics during the call through the aRes object. We interest us here only to a particular statistic, the lnit member of the aRes object, which sums the number of discovered candidates to be examined at the next level. Because each Task computes its own candidates for the next level, the method has to pay attention to the possible interference which could take place during the overall parallel computation on such a "shared" variable, which can be seen here as an aggregation pattern.

We use therefore a two-phase approach: First, we calculate partial results locally on a per-Task basis. Then, once all of the per-Task partial results are at disposal, we sequentially merge the results into one final accumulated value. The PPL provides a special data structure that makes it easy to create per-Task local results in parallel, and merge them as a final sequential step. This data structure is the combinable class. In the above code, the final accumulated object is the lnit object, which decomposes into local to each Task lnit.local() sub-objects. After the parallel for loop achieves, the final sum is produced by invoking the combine() method on the global object. We shall not enter into the implementation details of this function. First because the code is most C likely and is easy to understand. And second because it does not include any specific parallel or shared memory features. So we shall only explain its overall functionalities. The for loop is used here to produce all the candidates of the current stage (the tCand variable). This is done by "adding" the possible existing 1-items to the base itemset managed by the function, and identified by the nel "number" (we shall discuss this aspect later). Once having generated such a candidate, we verify first if the different constraints underlying to our method are verified or not by the candidate. If it is the case, we compute its Contingency Vector (the whole is done by the compute CV function). We second (try to) memorize the candidate in order to reuse it at the next level, and we add the candidate to the results if it contains one item of the target attribute.

The last function we present is store CV. We focus moreover on a very specific section of code dedicated to the storage of results: Let us first explain the functionality involved in the last if statement. kitemsets verifying the whole defined constraints and including one item belonging to the target column have to be included into the results. This is managed through their insertion into data files (one is associated to each value of k). During the parallellization process, each Task may write to one of these files each time it discovers a new valid itemset. What raises another shared resource problem, addressed by the PPL by the use of critical sections (a well-known concept in multi-threading developments), as shown in the above code. When encountering such an instruction at run-time, the OS will not authorize any other Task to execute before the "lock" has been released.

To finish this presentation, some explanations concerning the way we manage the memorization of candidates (and associated information such as Contingency Vectors). The main shared data structure in our developments is a tree storing the k-itemsets of "interest". The corresponding node structure, given in C: Each time a Task discovers a candidate verifying the whole constraints, the candidate is inserted into the tree. The insertion by itself uses the critical section concept we just introduced. Because the stored itemsets (patterns) are lexicographically organized within the tree, each of them can be referred to by a node number (what explains the nel "number" introduced above). Finally, after evaluating the candidates, the exploring process will retain them or not. In the latter case, the tree structure may be garbaged, which is done by the update shared resources function called at the end of our global PLW Chi2 method.

Experimental Analysis

As briefly mentioned in the Introduction Section, this work has been initially applied on concrete data measurement files provided by two industrial manufacturing partners in the area of Microelectronics : STMicroelectronics (STM) and ATMEL (ATM, which became LFoundry). The results of the realized experimental series are presented on 2 plans to be followed. They are associated with an analysis of 2 files among those supplied by both manufacturers. The first one (STM) contains 1241 columns and 296 lines. The second (ATM) consists of 749 columns and 213 lines. We chose a target attribute among a few possible columns. In both cases, the presented diagrams show the execution times of two methods when M inSup varies while M inP erc (0.34 for the STM file and 0.24 for the ATM one) and M inCor (1.6 resp. 2.8) are fixed. The signification of these parameters were given in section 3.2. Figures 1(a) and 1(b), extracted from (Casali and Ernst, 1), show the execution times of a standard Levelwise algorithm and the LHS-Chi2 algorithm on a non core computer (a HP Workstation with a 1.8 GHz processor and 4 Gb RAM, working under a Windows XP 32 bits OS). The difference between the two methods is that the Levelwise method uses no contingency vectors but standard computation of contingency tables. As the graphs point it out, the response times of the LHS-Chi2 method are between 30% and 70% better than Levelwise. An increasing windowing of the results is provided for subsequent sub-intervals of M inSup.

Figures 2(a) and 2(b) show the same execution times using the LHS-Chi2 algorithm and the presented PLW-Chi2 algorithm on a 4 core computer (a DELL Workstation with a 2.8 GHz processor and 12 Gb RAM working under the Windows 7 64 bits OS).

As it is easy to understand, the LHS-Chi2 method works here about two times faster on the multicore architecture, this not because of the number of cores (which are not used) but because of the computer basic enhanced capabilities. When regarding to the performances of the PLW-Chi2 method, there is a gain factor of about 3.5, which is to compare to the number of available cores, which is 4. In other words, the parallelization of the LHS-Chi2 algorithm raises performance gains practically equals to the number of cores, the (little) loss being due to the shared memory management issues.

Conclusion and future work

In this paper, we present a new approach to discover correlated patterns, based on the usage of multicore architectures. Our approach is based on two concepts: Contingency Vectors, an alternate representation of contingency tables, and the Parallel Patterns Library (PPL). One of the advantages of Contingency Vectors is that they allow the Chi-squared computation of a k-itemset directly from one of its subsets. However, the usage of the PPL has two disadvantages: on one hand we need to use lambda calculus, and on the other hand, the parallelization of recursive algorithms is hard (we do not control neither the number of cores, nor the depth of the tree), even if we derecursify the algorithm. That is why we have chosen to implement a Levelwise algorithm which implements these two concepts. Experiments are convincing because our new algorithm obtains a time gain factor of about 3.5 (when using 4 cores) in comparison with the recursive version.

For future works, we intend to develop a new version of the recursive algorithm using a bitmap representation for a Contingency Vector, thus we can minimize disk I/O, and, for finer control processors, build our own thread manager.

Definition 4 (

 4 Equivalence Class associated with a literal). Let Y Z be a literal. Let us denote by [Y Z] the equivalence class associated with the literal Y Z. This class contains the set of transaction identifiers of the relation including Y and containing no value of Z (i.e., [Y Z] = {i ∈ T id(r) such that Y ⊆ T id(i) and Z ∩ T id(i) = ∅}).

  Mot; /* the pattern */ unsigned char *pVC; /* pointer to the Contingency Vector */ T_NM *frere; /* pointer to next node at same level */ T_NM *fils; /* pointer to next node at lower level */ ... } T_NM;

Fig. 1 .

 1 Fig. 1. Execution times with a single processor.

Fig. 2 .

 2 Fig. 2. Execution times with 4 cores.

  The dowork level function is for its part roughly implemented as follows:

	unsigned short vmin, tCand[MaxLv + 1]; // a candidate
	unsigned long j, k;
	unsigned char *theVC; // a CV
	// other declarations and initializations ...
	// get current itemset
	vmin = get_pattern (nc, tCand, pX, cX, nel, sIX);
	j = 0;	// get j, index of the first 1-item to add to the itemset
	while (j < cX && pX[j] <= vmin) j++;
	for (k = j; k < cX; k++)
	{
	// add a 1-item to the current itemset to produce a candidate
	tCand[0] = pX[k];
	// compute its CV if the constraints are valid
	theVC = compute_CV (tCand, nc, ...);
	// memorize the candidate and add it to results if applies
	store_CV (tCand, nc, theVC, pRes, ...);
	// update statistics
	(pRes.nit)++; //...
	}
	}
	void dowork_level (
	unsigned char nc, unsigned short pX[], unsigned short cX,
	unsigned long nel, unsigned short sIX, T_Res& pRes)
	{