CN101093501A - Method for querying high performance, transparent distributed spatial database - Google Patents

Abstract

The invention discloses an efficient and transparent query method for a distributed spatial database. Based on the spatial topological relation and spatial analysis operation defined by the Open GIS standard, the spatial topological relation operation and the spatial analysis operation are divided into two categories: Disjoint operation and Non-Disjoint operation; Buffer operation and non-Buffer operation, and according to the spatial topological relationship operation and spatial analysis operation, the connection methods of space segments are divided into four types, and three rules are proposed for the cross-boundary connection operation of four types of space segments, and in these three On the basis of the regularity, 7 rules of cross-boundary spatial segment connection optimization method are further proposed, including 3 removal rules and 4 connection transformation rules. Through the optimization of spatial segment connection, efficient and transparent query of distributed spatial database is realized. .

Description

An Efficient and Transparent Query Method for Distributed Spatial Database

technical field

The invention relates to an efficient and transparent query method for a distributed spatial database, which belongs to the field of information.

Background technique

At present, there are two main methods to achieve cross-boundary seamless query of distributed spatial databases: one is to convert the global query connection operation into the connection operation of each segment according to the distribution rules of traditional distributed database connections, but the efficiency of query processing is low; Another method is for the user to determine the relevance between the sites, that is, the user determines which relevant local sites to send the query to, this method does not meet the requirements of the transparency of the distributed database, and it is determined by the user himself The data correlation between venues is complicated to apply, and it is actually not realistic.

Contents of the invention

The object of the present invention is to provide a kind of highly efficient, transparent distributed spatial database query method, by using the proposed cross-boundary connection optimization rule for the query decomposition of distributed spatial data, automatically generate the spatial sub-query that can be executed by the local spatial database, Achieve efficient, transparent and seamless query.

The technical solution adopted for realizing the purpose of the present invention is: a highly efficient and transparent distributed spatial database query method, which is realized through four levels of query decomposition, data localization, global query optimization, and local query optimization. For the problem of cross-boundary seamless query of distributed spatial databases, first classify the connection operations of spatial segments, based on the spatial topological relational operations and spatial analysis operations defined by the Open GIS standard, divide the spatial topological relational operations into separation operations (Disjoint operations ) and non-disjoint operation (non-Disjoint operation), divide the spatial analysis operation into buffer operation (Buffer operation) and non-buffer operation (non-Buffer operation), and divide the connection mode of the spatial segment according to the spatial topology relation operation and the spatial analysis operation into four categories: the first type of spatial segment join is non-disjoint join with non-buffered query; the second type of spatial segment join is non-disjoint join with non-buffered query; the third type of spatial segment join is non-disjoint join with buffered query; The four types of spatial segment connections are separated connections with buffered queries. This classification preliminarily straightens out the relationship between spatial topology operations, spatial analysis operations, and spatial segment connections, and lays the foundation for the optimization of spatial segment connections.

The cross-boundary seamless query problem of partitioned shards is essentially a cross-boundary spatial segment connection problem, so it can be realized by optimizing the spatial segment connection. The basic idea of cross-boundary segment connection optimization: first, reduce the number of spatial segment connections; second, reduce the number of objects participating in the spatial segment connection, so as to reduce the connection operation time and reduce the amount of spatial data transmission between sites. According to the two basic ideas described, the cross-boundary connection operations of different types of space segments meet the following rules: ) intersection rectangle intersects; II. the minimum enclosing rectangle of the d buffer extension of a space segment relation does not exceed the d expansion of the minimum enclosing rectangle of this space segment division boundary, the so-called d expansion of the minimum enclosing rectangle is defined as follows: set a space object The coordinates of the lower left corner and upper right corner of the minimum enclosing rectangle of the object are (x _min , y _min ), (x _max , y _max ), then the d extension of the minimum enclosing rectangle of this object is that the coordinates of the lower left corner and upper right corner are (x The rectangle of _min -d, y _min -d), (x _max +d, y _max +d), where d is a positive real number; III. The third type of spatial connection between two spatial segments, if the main segment object and the auxiliary segment Objects satisfy the third type of connection mode of spatial segments, then the objects satisfying the third type of spatial topological relationship in the main segment intersect with the d extension of the smallest enclosing rectangle of the auxiliary segment or the double d extension of the smallest enclosing rectangle, where the main segment and the auxiliary segment The definition of the double-d extension is as follows: among the two fragments participating in the connection, the fragment containing the buffer operation is called the main fragment, and the other fragment is called the secondary fragment. If there are buffer operations on the two fragments participating in the connection, set the buffer are d1 and d2 respectively, then choose one as the main segment and the other as the auxiliary segment, at this time, carry out the d1+d2 extension of the smallest enclosing rectangle to any segment, which is called the double-d extension of the segment;

Based on the above three rules, a method for optimizing the cross-boundary connection of space segments is proposed, including three removal rules: (1) If the smallest enclosing rectangles of the segmentation boundaries of the two space segments involved in the connection do not intersect, then the two The first type of connection between space segments is removed; (2) The first type of connection between non-adjacent space segments is removed; (3) If the generalized d extensions of the two space segments of the split slice are disjoint, then the two space segments The third type of connection removal, the so-called generalized d extension of the connection fragment is defined as follows: a fragment X participating in the buffer connection, its generalized d extension is expressed as MBR(X)_d _E , if the object in X is buffered first and then performed Fragment connection, then d is equal to the buffer distance, that is, MBR(X)_d _E = MBR(X)_d, if the object in X directly performs fragment connection, it is regarded as d=0, at this time MBR(X)_d _E = MBR(X); and the following four connection conversion rules: (4) Perform the first type of cross-boundary θ _sp-1 ^ed connection on two space segments X and Y, and convert to X and Y based on X, The intersection of the smallest enclosing rectangle and the rectangle of the Y division boundary is calculated and filtered, and then the first type of space connection operation θ _sp-1 is performed, namely: $x{\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^{\mathrm{ed}}}Y={\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^f}\left(x\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-1}}{\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^f}\left(Y\right);$ (5) If the minimum enclosing rectangles of the segmentation boundaries of the two space segments participating in the connection do not intersect, the second type of connection between the two space segments is transformed into the Cartesian product of the two segments; (6) in the two space segments The third type of cross-boundary connection θ _sp-3 ^ed is performed on the space segment X and Y, and it is converted into the third type of spatial topological filtering θ _{MBR(Y)_d} ^f (X) on X, and the filtering result is d-buffered, Then perform the third type of spatial join operation θ _sp-3 , namely ${\mathrm{\η}}_d\left(x\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-3}^{\mathrm{ed}}}Y={\mathrm{\η}}_d\left({\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{MBR}\left(Y\right)\_d}^f}\left(x\right)\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-3}}Y;$ (7) The generalized d extensions of the two space segments participating in the connection are disjoint, and the connection between the two space segments is transformed into the Cartesian product of the two space segments.

An efficient and transparent distributed spatial database query method provided by the present invention is realized through four levels of query decomposition, data localization, global query optimization, and local query optimization. The steps are as follows:

Query decomposition: convert the query problem into a relational algebra expression defined on the global relationship. The query decomposition is divided into four steps: the first step is to write the query into a normalized form, the second step is to analyze the correctness of the normalized query statement, and the second step is to The third step is to simplify the query, and the fourth step is to rewrite the query statement into an algebraic query. The query rewriting is divided into two sub-steps: one is to convert the query into relational algebra, and the other is to reconstruct the relational algebraic query;

Data localization: use data distribution information to locate the query data, determine the segments involved in the query, specify a query on a global relationship, and perform a query on a localized or evolutionary spatial segment, and integrate the global relationship The relational algebra expression is transformed into the relational expression on the corresponding segment, and the spatial query is optimized by using the 7 rules of the cross-boundary connection optimization of the space segment, according to the removal rules (1) and (2) in the space segment cross-boundary connection optimization method Remove redundant non-adjacent space segments of the first type of connection, according to the space segment connection optimization rule (3), remove the third type of connection between segments, and obtain whether the segments are adjacent to each other, the minimum enclosing rectangle of the segment, etc. from the spatial global data dictionary The information judges which optimization rule to use among the four connection transformation rules to optimize the connection of space segments;

Global query optimization: By looking for a near-optimized execution strategy, that is, to find the best operation order of fragmented queries, including the minimum cost function, the cost function is generally the sum of I/O, CPU and communication costs, and output an optimized relational algebra queries on fragments;

Local query optimization: Each site with query fragments executes subqueries on each site, and uses a centralized system algorithm to optimize through the DBMS on the site.

The beneficial effects of the invention are: on the basis of traditional transparent query processing, the connection optimization between space segments is realized through the proposed cross-boundary segment connection optimization rule, and efficient and transparent query of distributed spatial databases is realized.

Detailed ways

The specific steps of the four levels of query decomposition, data localization, global query optimization, and local query optimization are as follows:

Query Decomposition: Converts a query problem into a relational algebra expression defined on global relations. The query decomposition is divided into four steps: the first step is to write the query into a standardized form for subsequent processing; the second step is to analyze the correctness of the normalized query statement; the third step is to simplify the query and eliminate redundant predicates; the fourth step The first step is to rewrite the query statement into an algebraic query. The query rewriting is divided into two sub-steps: one is to convert the query into a relational algebra, and the other is to reconstruct the relational algebra query and express it with a query tree. In the reconstruction of relational algebra query, some optimizations are realized through the conversion rules of traditional databases, including elimination of redundancy, etc. The information needed for this level of transformation is obtained in the global conceptual schema.

Data localization: The input of this layer is an algebraic query on a distributed global relationship. The query data is located through the data distribution information to determine which segment is involved in the query, and the query on a global relationship is concretized and implemented on the appropriate segment. Inquire. Transforms a relational algebra expression on a global relation into a relational expression on the corresponding fragment.

Optimizing Spatial Queries Using 7 Rules for Spatial Fragment Join Optimization. In a traditional distributed database, there are many redundant connections between horizontally sharded fragments, and there are also redundant connections among the partitioned fragments obtained by splitting the same partition set. According to the removal rules (1) and (2) in the space segment connection optimization method, the redundant first-type connection of non-adjacent space segments is removed, and the third-type connection between segments is removed according to the removal rule (3), and the spatial global data Whether the fragments are adjacent, the MBR of the fragments and other information is obtained in the dictionary to determine which of the four connection transformation rules to use to optimize the spatial fragment connection.

Global query optimization: the input of global optimization is fragment query, that is, algebraic query on fragments. Functions are generally the sum of I/O, CPU, and communication costs. The output of a global query is an optimized, relational algebra query on fragments. The information required for this layer comes from the statistical information of the database, including the statistical information of each field segment, resource information and communication information.

Local query optimization: Sub-queries are executed on each site by each site that owns the query fragment. It uses a centralized system algorithm to optimize through the DBMS on the site, and the required information is taken from the local schema.

The present invention will be further described below in conjunction with embodiment.

Example 1

The specific execution steps of an experimental system are:

(1) System call: After the user enters the SQL statement on the query interface, the global SQL statement is passed to the distributed spatial data access engine.

(2) Global query decomposition: Distributed query decomposition is divided into two steps. The first step is to realize the parsing of SQL query statements to obtain the syntax tree; the second step is to transform the syntax tree to obtain the merge connection tree.

(3) Data localization and query optimization: localize and optimize the merged join tree according to site fragmentation and other information, and call the global data dictionary service to obtain the necessary global information in the process of data localization and query optimization, such as fragments Site, statistical information, selectivity factors of connection operations, etc., use the removal rules and connection conversion rules to realize the optimization of spatial segment connections. According to the removal rules (1) and (2), remove the redundant first-type connection of non-adjacent space segments; according to the removal rule (3), remove the third type of connection between segments, and obtain whether the segments are adjacent to each other from the spatial global data dictionary , fragment MBR and other information to determine which of the four connection transformation rules to use for space fragment connection optimization.

(4) Query scheduling; after the distributed spatial data access engine obtains the query execution plan tree, it sends the query execution plan tree and the corresponding scheduling script to the scheduling server, and the scheduling server executes the scheduling script through the distributed script engine, The query execution tree is traversed, and each execution node is sent to the proxy server on the relevant execution site for execution. After all are completed, the final query result set is returned to the distributed spatial data access engine.

(5) Execution of the execution node: After obtaining the execution node, the proxy server performs segment query conversion according to the characteristics of its own data source, and invokes the relevant local spatial database engine and basic data access driver to query. After obtaining the data set , serialize according to the same format specified by this system, and finally send the result to the specified location.

Claims (2)

1. One kind efficient, transparent distributed spatial database querying method, pass through query decomposition, the data localization, global query optimization, four levels of local query optimization are realized, it is characterized in that: at the cross-border seamless inquiry problem of the distributed spatial database of cutting apart burst, earlier the attended operation of space fragment is classified, spatial topotaxy operation and spatial analysis operation based on the OpenGIS standard definition, the spatial topotaxy operation is divided into from operating with non-from operation, spatial analysis operation is divided into buffer operation and non-buffer operation, and the connected mode of space fragment is divided into four classes according to spatial topotaxy operation and spatial analysis operation: first kind space fragment be connected be non-buffering inquire about non-from connection; The second space-like fragment connect be non-buffering inquiry from connection; It is the non-from connection of band buffering inquiry that the 3rd space-like fragment connects; The 4th space-like fragment connect be the inquiry of band buffering from connection, this classification has been set up spatial topotaxy operation, spatial analysis operation and the incidence relation between the space fragment is connected, on this basis, following rule is satisfied in the cross-border attended operation of dissimilar space fragment:

   I. satisfy two space fragments of first kind connected mode and must hand over rectangle intersection with the minimum outsourcing rectangle of these two space fragment partitioning boundaries;

   II. the minimum outsourcing rectangle of the d buffer zone expansion of a space fragment relation does not exceed the d expansion of the minimum outsourcing rectangle of this space fragment partitioning boundary, and the d expanded definition of so-called minimum outsourcing rectangle is as follows: the lower left corner and the upper right corner coordinate of establishing the minimum outsourcing rectangle of a spatial object are respectively (x _Min, y _Min), (x _Max, y _Max), then the d of the minimum outsourcing rectangle of this object expansion is that the lower left corner and upper right corner coordinate are respectively (x _Min-d, y _Min-d), (x _Max+ d, y _Max+ d) rectangle, wherein d is an arithmetic number;

   III. two intersegmental the 3rd space-likes of spatial pieces connect, if satisfy the 3rd class connected mode of space fragment between main leaf section object and auxilliary fragment objects, the object that then satisfies the 3rd space-like topological relation in the main leaf section intersects with the d expansion of the minimum outsourcing rectangle of auxilliary fragment or two d expansions of minimum outsourcing rectangle, main leaf section wherein, auxilliary fragment, the definition of two d expansions is as follows respectively: the fragment that comprises buffer operation in two fragments that participate in connecting is called the main leaf section, then another fragment claims auxilliary fragment, if on two fragments that participate in connecting buffer operation is arranged all, if buffer zone is respectively d1, d2, then choose one wantonly as the main leaf section, another is as auxilliary fragment, carry out the d1+d2 expansion of minimum outsourcing rectangle to any one fragment this moment, is called two d expansions of fragment;

   Based on these three rules, 7 rules that fragment cross-border connection in space is optimized are proposed, remove rule comprising following 3:

   (1) if the minimum outsourcing rectangle of the partitioning boundary of two space fragments that participation connects is non-intersect, then the intersegmental first kind of these two spatial pieces connects removal;

   (2) non-conterminous space fragment first kind connection is removed;

   (3) expand non-intersect if cut apart the broad sense d of two space fragments of burst, then intersegmental the 3rd class of these two spatial pieces connects removal, the broad sense d expanded definition of so-called junction fragment is as follows: participate in the fragment X that buffering connects, its broad sense d expansion table is shown MBR (X) _ d _EIf, do fragment again after the advanced row buffering operation of the object among the X and connect, then d equals the buffer zone distance, i.e. MBR (X) _ d _E=MBR (X) _ d connects if the object among the X directly carries out fragment, then regards d=0 as, at this moment MBR (X) _ d _E=MBR (X);

   And following 4 connection transformation rules:

   (4) on two space fragment X, Y, carry out the cross-border θ of the first kind _Sp-1 ^EdConnect, be converted to earlier and hand over rectangle to ask friendship to filter, and then carry out first kind spatial join operation θ based on X, the minimum outsourcing rectangle of Y partitioning boundary carrying out on X, the Y _Sp-1, that is: ${X\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^{\mathrm{ed}}}Y={\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^f}\left(X\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-1}}{\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{sp}-1}^f}\left(Y\right);$

   (5) if the minimum outsourcing rectangle of the partitioning boundary of two space fragments that participation connects is non-intersect, then the second intersegmental class of these two spatial pieces connects the cartesian product that is converted into these two fragments;

   (6) on two space fragment X, Y, carry out the cross-border connection of the 3rd class θ _Sp-3 ^Ed, be converted to and on X, carry out earlier the 3rd space-like topology filtration θ _{MBR (Y) _ d} ^f(X), filter result is carried out the d buffering, and then carry out the 3rd space-like attended operation θ _Sp-3, promptly ${\mathrm{\η}}_d\left(X\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-3}^{\mathrm{ed}}}Y={\mathrm{\η}}_d\left({\mathrm{\σ}}_{{\mathrm{\θ}}_{\mathrm{MBR}\left(Y\right)\_d}^f}\left(X\right)\right){\∞}_{{\mathrm{\θ}}_{\mathrm{sp}-3}}Y;$

   (7) the broad sense d expansion of two space fragments of participation connection is non-intersect, and then these two intersegmental connections of spatial pieces are converted into the cartesian product of these two space fragments.
2. 2. a kind of efficient, transparent distributed spatial database querying method according to claim 1 is characterized in that: the concrete steps that query decomposition, data localization, global query optimization, four levels of local query optimization are realized are as follows:

   Query decomposition: the inquiry problem is converted to a relational algebra expression formula that is defined on the holotopy, query decomposition was four steps: the first step is write inquiry as normalized form, second step was that the standardization query statement is carried out the correctness analysis, the 3rd step was to inquire about abbreviation, the 4th step was that query statement is rewritten as an algebraically inquiry, query rewrite is divided into two sub-steps: the one, query conversion is become relational algebra, and the 2nd, relational algebra inquiry reconstruct;

   Data localization: by DATA DISTRIBUTION information locating query data, the fragment that relates in determining to inquire about, inquiry on the holotopy is specialized, inquire about specific to localization or on the space fragment on changing with advancing, relational algebra expression formula on the holotopy is transformed to relational expression on respective segments, utilize 7 rules of the cross-border connection optimization of space fragment to optimize space querying, removing the unnecessary non-conterminous space fragment first kind according to the cross-border connection principle of optimality of space fragment (1) and (2) is connected, connect the principle of optimality (3) according to the space fragment and remove intersegmental the 3rd class connection of sheet, and whether adjacent by from the global catalog of space, obtaining fragment, information such as the minimum outsourcing rectangle of fragment are judged the optimization of using four kinds of which kind of principles of optimality that connects in the transformation rule to carry out space fragment connection;

   Global query optimization: be bordering on optimized implementation strategy by seeking one, promptly find out the optimum operation order of burst inquiry, a relational algebra inquiry optimization of output, on the fragment;

   Local query optimization: on each website, carry out subquery by each website that has query fragment, adopt the integrated system algorithm to be optimized by the DBMS on this website.