Databases Reference
In-Depth Information
have to define a domain where access paths are effective because we can get multiple
access paths.
In querying to a graph, regular expressions are usually used as specification of
an access path (for example, Lorel, UnQL, XML-QL) in
Abiteboul et al 99)
). Such
expressions are developed into a set of possible access paths and multiple queries
can be generated. It is important for users, however we omit it in this article,
because it is not essential.
4.3
Logical Operations and Reduction of Access Paths
We define logical operations between graphs obtained in Section 4.2. Let
a-path(g)
be a set of access paths, obtained by transformation of a graph
g
. Transformation
of results in
.
It requires to specify a domain where
reference relations are effective, as already mentioned.
Given a set of graphs or access paths, we have to normalized it, that is, eliminate
duplication and redundancy. As for graphs, we explain in Section 4.4.
As, when, ,
a
2
has more specific information than
a
1
, we define Smyth
ordering between sets of access paths
S
1
,
S
2
as follows:
Let the minimum set be the representative of corresponding equivalence classes. A
set of access paths as the result of retrieval is the representative in this meaning.
We consider only such sets.
When
, we define
. Further we
define logical operations between sets of access paths as follows:
As an access path specifies a subgraph, we can enlarge the graph by reducing the
access path as follows:
which is similar with projection as in relational algebra. When the specified label
appears in multiple times, we take the longest path: that is,
is not
necessarily the same as
. The result is normalized in the sense of Smyth
ordering.
4.4
Merge of Graphs
In distributed environments, the same object might be located in different locations
in different expressions. When we get such objects as a result of search operations,
graphs should be normalized according to the semantics and graphs with the same
identifier should be merged. Merging based on equality constraints is executed
