LeoBase

Introduction

Capabilities

History

New technologies

Example

Marketing

Investment

An example of practical application of LeoBase

We can give a lot of examples, but we will consider a rather simple one which can demonstrate some LeoBase advantages over existing DBMS. Moreover, this example will illustrate the application of LeoBase in the field where it is impossible or difficult to use most existing DBMS.

This example is a part of the solution in the field of cartography which is based on LeoBase technologies and was tested in practice in 1994. Computer equipment that was indispensable to carry out tasks with the use of Oracle and inaccessible for different reasons (high prices, etc.) caused the use of LeoBase as an alternative to existing DBMS.

Problem description and its solution

It is necessary to conduct search for objects included in arbitrarily assigned geometrical area. To simplify the perception, we will describe an example where it is necessary to find simple objects (line segment) included in a frame. While searching for more complicated objects in geometrical areas which are described by complex formulas, the same algorithm is used.

To simplify the description of the algorithm of the  solution to the problem, we will use only one table of integer data (let’s call it stretch) in which integer data are coordinates of line fragments that are described by four variables (x1, x2, y1, y2). It is necessary to remember that in this example the algorithm is over when a set of records which are relevant to search criteria is determined for the table stretch. In real conditions the table stretch is linked to a variety of other tables and received results should be projected onto all the tables linked to the table stretch.

Problem definition . There is a set of line segments that are characterized by their coordinates (x1, y1, x2, y2). It is necessary to determine a set of line fragments which are completely or partly included in a specified frame with the coordinates (Rx1, Ry1, Rx2, Ry2). See below a picture.

Realization of algorithm.

There are 3 types of line segments:

1)     The coordinates of at least one of end point satisfy the conditions Rx1<x<Rx2 и Ry1<y<Ry2 and these line segments are included in the frame.

2)     The coordinates of all points of a segment meet at least one condition Rx2<x, Rx1>x, Ry2<y, Ry1>y and these line segments are not precisely included in the frame.

3)     Line segments for which it is necessary to determine whether they are included in the frame. Moreover, the formula of line is used for calculations and it is determined by enumeration whether line segments are included in the frame.

Let’s consider all 3 types of line segments and it is necessary to remember that Rx1, Ry1, Rx2, Ry2 describe the coordinates of the specified frame.

Line segments that are precisely included in the frame.

As you can see on the picture, the line segments ‘O1’ is precisely included in the frame, because one of its end points is included in the frame.

SQL_Yes:  Select  stretch.*   from stretch where  Where_yes

Where_Yes:

           ( ( x1 between rx1 and rx2) and (y1 between ry1 and ry2))

                 Or

        ( ( x2 between rx1 and rx2) and (y2 between ry1 and ry2))

Line segments that are not precisely included in the frame

As is seen on the picture, there are two such line segments ‘O4’, ‘O5’, because both coordinates ‘y’ of the line segment ‘O4’ are less than ‘Ry1’ and both coordinates ‘x’ of the line segment ‘O5’ are more than Rx2.

SQL_No: Select  stretch.*   from stretch where

Where_no:

           ((x1 <  rx1) and (x2< rx2))

                    Or

           ((x1 > rx2) and (x2> rx2))

                    Or

           ((y1 < ry1) and (y2 < ry1))

                    Or

           ((y1 > ry2) and (y2 > ry2))

It is not known whether line segments are included in the frame

SQL_Quest:

Select  stretch.*   from stretch where Where_Quest

Where_Quest:

(Not where_yes) And (Not where_no)

The algorithm for a relational DBMS.

1) The query sql_quest with compiling a temporary table, the so-called query result table.

2) Traversing through the table sql_quest and removing those records which are not included in the frame (each line segments is compared with the coordinates of the frame with the use of the formula of line) and decreasing the amount of records in sql_quest.

3) Combining sql_quest with the query sql_yes and getting the final result.

The algorithm for LeoBase.

1) Result_yes = the result of the query sql_yes. Result_yes is an integer array.

2) Result_yes = the result of the query sql_no.

3) Result_query = (the result of the query Select  stretch.*  from stretch) Sub  (result_yes) Sub (result_no)

4) Then traversing all records of result_query and determining with the use of the formula of line whether points of a line segment is included in the frame (whether a line segment intersects the frame) and those line segments that intersect the frame are removed from a set result_query.

5) Result = result_query or result_yes

It should be noted that while processing the algorithm, LeoBase does not compile a temporary table, which increases its operating speed, because this algorithm does not involve processing records one by one.

We remind that this problem was solved in 1994 and since that time LeoBase algorithms have been seriously improved. Today the difference in operating speed between LeoBase and other DBMS will be considerably higher in spite of the fact that other DBMS are also being developed. In our opinion, though LeoBase-94 showed good results in comparison with Oracle, our DBMS was working too slowly (if we evaluate current capabilities of LeoBase). This fact is proved by the implementation of LeoBase-98 that worked 2-3 times quickly in comparison with LeoBase-94. In the same time it had an important disadvantage – only 16 bit version was impleemnted.

The version of LeoBase which technologies are described in this document takes account of all disadvantages of teh previous version and it is extended by new solutions. In our opinion, it will work about 5 times more quickly than LeoBase-98.

Conclusion

As was mentioned above, only a part of problem in the field of cartography was described. In fact, the solution of this problem required that line fragments included in or intersected a geometrical area were determined. Moreover, the algorithm of searching in the frame was used, though to solve this problem, it was necessary to create 2 frames and conduct a number of additional operations. The information about 10 millions of line segments were included into the database (which is not so big size for a cartographic project). The attempt to solve this problem on a rather up-to-date computer with the use of DBMS Oracle 6.0 failed, i.e. the operation of query processing took 3-4 hours. LeoBase processed the same query during 3-4 minutes. While it was not reasonable to use DBMS Oracle for more complex problems, for example searching more complex objects with the use of complex formulas.

This is lust an example related to cartography. However, LeoBase meets requirements of modern information technology and can be applied in other application fields, for example biotechnology where the problem of fast search and data processing is also critical.