Generalized Graph Pattern Matching

Generalized Graph Pattern Matching Pedro Almagro-Blanco and Fernando Sancho-Caparrini August 15, 2017 1 Introduction Graphs are high expressive models and especially suitable for modelling highly complex structures, the number of applications that use them for modelling both their data and the processes that manipulate has grown dramatically in recent years. The use of new conceptual structures in real-world applications requires the development of new systems to store and query such structures in order to allow users to access data effectively and efficiently. As with all new technologies, it is still in the development phase and in search of a set of standards ensuring a continued growth. The growing popularity of Graph Databases has led to the emergence of interesting problems related to storage and query in these systems. These databases have robust fundamentals in terms of basic information management (creation, access, deletion, and modification of individual elements of the structure), but they lack standards in some other tasks necessary for the storage and retrieval of information, like those related to more advanced query mechanisms. Among the problems related to these query processes, the detection of patterns is considered as one of the fundamental ones since it includes other subproblems necessary to obtain powerful query systems, such as the search of subgraphs or minimum paths, or the study of connectivity [18, 10]. In this paper we present Generalized Graph Query (GGQ), a proposal to carry out queries in property graphs. GGQ represents a robust logical framework, making it especially useful in graph discovery procedures and generalizing other more basic tools that have been proved very useful on related tasks. In addition, we will present a collection of operations that allow to obtain complex GGQs from simpler ones, something very useful when automating the construction of complex queries. 2 Graph Pattern Matching Graph Pattern Matching is an active research area since more than 30 years and its usefulness has been demonstrated in many areas, from artificial vision, to biology, through electronics, computer-aided design, and analysis of social networks, among others. Undoubtedly, its interest has grown even more as graph databases has become a tool for structuring and storing information in a transversal way in all areas of knowledge. For this reason, the problem of graph pattern matching expands, with slight variants, across different scientific 1 communities, showing that is not a single problem defined under a common formalization, but a set of related problems. The process by which we check the presence of a particular pattern in a particular set of data is called pattern detection, and computationally represents the set of mechanical processes that allow to return one (or all) the occurrences of the pattern. The definition of what is meant by an occurrence of a pattern in a graph varies according to how the pattern is defined. When it is given by a graph structure (although not necessarily using the same elementary sets of vertices and edges as the graph on which the query is made) it is usual to associate the occurrence with the existence of identifications (perhaps not as strong as isomorphisms) between the pattern and those subgraphs in the data that respect some imposed constraints [6]. Some classifications that we can present in terms of the different possible ways to carry out the detection of patterns in graphs are: (a) Structural vs. Semantic, (b) Exact vs. Inexact, and (c) Optimal vs. Aproximate [9]. One other classification takes into account the relation to be met by the pattern regarding to the subgraphs that are considered its occurrences. It allows to divide the different techniques of graph pattern matching in those based on Isomorphisms (an occurrence will be any subgraph that is isomorphic to the pattern), Graph Simulation [13] (an occurrence will be any subgraph for which there is a binary relation between the elements of the subgraph and the pattern which respects the types of the nodes and their adjacencies), Bounded Simulation [8, 18, 13] (based on Graph Simulation but allowing to associate pattern edges to paths) and Regular Pattern Matching [7, 15, 4, 13] (Bounded Simulation with regular expressions for pattern edges). Current tools that allow querying patterns in graphs use either a declarative language (such as Cypher, SPARQL, or SQL), or an imperative language (with Gremlin as the clearest representative). In the case of declarative languages, it is responsibility of the system (ideally) to perform queries optimization. In the case of imperative languages, the execution plan is responsibility of the user, so they usually provide lower level approximations. Next, we briefly present some query languages that have been used for graph pattern matching. SQL (Structured Query Language) is a declarative language for accessing Relational Database Management Systems (RDBMS). These types of databases were designed for tabular data with a fixed schema, and work best in contexts that are well defined from the beginning and where the records themselves are more important than the relationships between them. For this reason, trying to answer questions involving many relationships between data (as is usual in graph pattern queries) with a relational database involves numerous and costly operations between tables, that may become this option intractable. In spite of this, SQL has the expressive capacity necessary to be able to express most of graph pattern queries, and because relational databases have been the storage option chosen by most projects for decades, the first graph pattern query systems used SQL queries, such as Selection Graphs that we will see later. SPARQL is a declarative query language for data stored in RDF format [16] and is recognized as a key technology of the Semantic Web, its expressive ability to perform graph pattern matching is superior to that provided by SQL, but is still not intuitive for a human user. SPARQL allows structural, semantic, 2 optimal, and exact queries based on subgraph isomorphism. Although SPARQL does not allow for any type of Graph Simulation or Regular Pattern Matching, language extensions such as PSPARQL [3] have been developed to query RDF databases using patterns that make use of regular expressions. Thanks to the structure of the language, it is relatively easy to generate automatic queries in SPARQL and there are tools that use it as a final query language. Gremlin is, at the same time, a query language for databases and a graph oriented computation system. As a language, Gremlin is independent of the underlying database. Its syntax allows for declarative and imperative queries, and easily express complex queries on graphs. Each query consists of a sequence of steps that perform atomic operations on the data stream. Gremlin allows semantic, exact, optimal queries and is based on subgraph isomorphism. It is possible to design other query languages to compile to Gremlin language (eg, SPARQL can be compiled to run on Gremlin 1). Selection Graphs are multi-relational patterns to express SQL based queries. They represent the foundation of the multi-relational decision tree induction algorithm MRDTL [12] as well as other multi-relational automatic learning algorithms [14]. The purpose of selection graphs is to be used in top-down discovery procedures [11], thus operators to modify them through small changes are provided that allow the construction of complex queries in successive steps. As a counterpart, they have the disadvantage that these constructions can not contain cycles, limiting the expressiveness of queries. Selection graphs represent an exact, optimal type of graph pattern matching based on semantic graph isomorphism. In addition, being a graphical representation of SQL queries, they inherit the efficiency problems presented by the systems based on this technology. The new proposal we show in these pages can be considered as a generalization of some of the ideas that promoted this previous approach, avoiding some of their limitations. Cypher is a declarative query language specifically developed to work on Neo4j graph database 2. Cypher is designed to be a human-friendly query language, close to both developers and end users. Query patterns in graphs that are usually hard to express in other languages are very simple in Cypher [2], showing a high expressive capacity [1]. Neo4j database closely follows the property graph model, but forces the edges to be typed. Unlike Gremlin, Cypher is not Turing complete, so it has some limitations, and it is higher level. Simple Cypher queries have good performance, but when queries follow complex patterns they can lead to a worst performance since it does not allow to indicate the application order of the different conditions. Cypher allows structural and semantic, optimal, exact, and based on subgraph isomorphism queries. In addition, it allows a type of Regular Pattern Matching in which the edges in the pattern are projected onto paths of the graph, and where constraints can be imposed through expressions that make use of the disjunction operator and the closure of Kleene. One limitation from the academic point of view is that it lacks an associated formal model, and some of its operations have not yet been validated. Despite this, because of its excellent expressiveness and acceptable performance, and because it consumes the data from a graph database with a widespread use, Cypher has been the election to implement the tests of GGQ. 1https://github.com/dkuppitz/sparql-gremlin 2http://neo4j.org 3 Some other tools related to graph pattern matching are: GraphLog [5], that allows to structure the queries as graphs and evaluates the existence of patterns between a pair of nodes to generate a new edge between them; GraphQL 3, a declarative query language developed by Facebook to allow external applications to access its information; Graql 4, a declarative query language oriented to knowledge graphs; and GGQL [17], a SQL extension with additional graph pattern matching tools (analysis of accessibility between nodes, definition of paths, or construction of graphs). 3 Preliminaries Given a set V, we denote: V0=∅, V 1=V, V n+1 =Vn×V, V ∗=[ n≥0 Vn In general, we call sequences or lists the elements in V∗. If x∈Vnthen we say that xhas length n, and we write |x|=n. If x= (a1, . . . , an), y = (b1, . . . , bm)∈V∗, then the concatenation of xand yis the element of V∗given by xy = (a1, . . . , an, b1, . . . ,bm). For each x= (a1, . . . , an)∈Vn, we call support set of xto s(x) = {ai: 1 ≤ i≤n}. We write a∈xto indicate that a∈s(x). For each a∈V, we denote |a|x= #{i:xi=a}(where #(A) is the cardinal of the set A), and we call multi-support of xto the set of pairs ms(x) = {(a, |a|x) : a∈x}. We define the relation ∼, which can be easily proved to be equivalence in Vn, as: x∼yif and only if ms(x) = ms(y) And denote by Vn ∼=Vn/∼(set quotient of Vnunder ∼). Our interpretation of these sets will be that Vndenotes the set of ordered tuples of V,Vn ∼denotes the set of unordered tuples of the same set (ie tuples in which elements are important, considering the possible repetitions, but not the order in which they appear). Next, we present the Generalized Graph, that covers the different variants of graph that can be found in the literature and that we will need when presenting our proposal of property graph pattern matching tool. Definition 1. AGeneralized Graph is a tuple G= (V, E, µ)where: •Vand Eare sets, called, respectively, set of nodes and set of edges of G. •µis a relation (usually we will consider it functional, but not necessarily) that associates each node or edge in the graph with its set of properties, that is, µ: (V∪E)×R→S, where Rrepresents the set of possible keys for these properties, and Sthe set of possible values associated. Usually, for each α∈Rand x∈V∪E, we write α(x) = µ(x, α). In addition, we require the existence of a special key for the edges of the graph, which we call incidences and denote by γ, which associates to each edge of the graph a tuple, ordered or not, of vertices of the graph. 3http://graphql.org/ 4https://grakn.ai 4 Although the definition that we have presented here is more general than those that can be found in the related literature, we will also call them Property Graphs, since they suppose a natural extension of this type of graphs. It should be noted that in generalized graphs, unlike traditional definitions, the elements in Eare symbols representing the edges, and not pairs of elements from V, and γis the function that associates to each edge the set of vertices that it connects. Definition 2 (Notation and definitions).In the context of the above definitions, we use the following notation: •We usually identify ewith γ(e). Thus, we interpret the edge as the collection of nodes that connects, as classic definitions of graphs. •Symmetrically, for every u∈Vwe write γ(u) = {e∈E:u∈e}. In general, a generalized graph may have a combination of directed and nondirected edges. If γ:E→V∗we say Gto be Directed (Not Directed, otherwise). •For each e∈E, we define the arity of eas Pa∈e|a|e. •If γ:E→V2∪V2 ∼we say that the graph is Binary (and it matches the most usual graph structure). Otherwise, the graph is a Hypergraph. •An edge, e∈E, is said to be a loop if it connects a node to itself, that is, if it has arity other than 1 but s(e)is unitary. •An edge, e∈E, is said to be incident on a node, v∈V, if v∈e. •Two distinct nodes, u, v ∈Vare called adjacent, or neighbors, in G= (V, E, µ)if there exists e∈Esuch that {u, v} ⊆ e. •If there are different edges in Ewith the same incidence, that is, edges connecting the same nodes, we will say that the graph is a Multi-graph. •If eis a directed binary edge connecting uto v,e= (u, v), we write ue →v, and we also denote eo=u(output of e) y ei=v(input of e). In this case, for each u∈Vwe write: γo(u) = {e∈γ(u) : eo=u} γi(u) = {e∈γ(u) : ei=u} which respectively denote the sets of outgoing edges and incoming edges of u. •Given u∈V, we define the environment of uin Gas the set of nodes, including u, that are connected to it, i.e.: N(u) = Se∈γ(u)γ(e). When necessary, we will use the reduced environment of u,N∗(u) = N(u)\u. The notion of subgraph is obtained from the usual definition by imposing that the properties are also maintained in the common elements. Definition 3. A subgraph of a graph G= (V, E, µ)is a graph S= (VS, ES, µS) such that VS⊆Vand ES⊆Eand µS⊆µ|VS∪ES. We denote S⊆G. 5 A fundamental concept when working with graphs is the concept of path, which allows the study of distance relationships and connectivity conditions between different elements, extending the connectivity allowed by edges to more general situations. As generalized graphs are considerably more general than the usual ones we should give some notions about the position of a node in an edge: Definition 4. If e∈Eand γ(e)=(v1, . . . , vn)∈Vn, then for each vi∈s(e) we define its order in eas orde(vi) = i. If e∈Vn ∼, then for each v∈s(e)we define orde(v)=0. We denote u≤evto indicate that orde(u)≤orde(v). From this relation of order between the nodes that an edge connects, we can define what we mean by a path in a graph. Definition 5. Given a graph G= (V, E, µ), the set of paths in G, denoted by PG, is defined as the minimal set verifying: 1. If e∈E,u, v ∈ewith u≤ev, then ρ=ue →v∈ PG, and sopV(ρ) = (u, v),sopE(ρ)=(e). We will say that ρconnects the nodes uand vof G, and we will denote it by uρ v. 2. If ρ1, ρ2∈ PG, with uρ1v, v ρ2 w, then ρ1·ρ2∈ PG, with uρ1·ρ2 w, sopV(ρ1·ρ2) = sopV(ρ1)sopV(ρ2),sopE(ρ1·ρ2) = sopE(ρ1)sopE(ρ2). When u=vwe say that ρis a closed path, and if there are not repeated edges in ρwe say that it is a cycle. If ρ∈ PG, with sopV(ρ) = (u1, . . . , un+1) and sopE(ρ) = (e1. . . , en), then we write: ρ=u1 e1 →u2 e2 →. . . en →un+1 Generally we will write u∈ρto express that u∈sopV(ρ), and e∈ρto express that e∈sopE(ρ). Remark. •Following a similar notation to the case of directed binary edges, if ρ∈ P(G)and uρ v, then we write ρo=uand ρi=v. •When necessary, we denote the paths through u, starting in u, and ending in u, respectively, by: Pu(G) = {ρ∈ P(G) : u∈ρ} Po u(G) = {ρ∈ P(G) : ρo=u} Pi u(G) = {ρ∈ P(G) : ρi=u} 6 4 Generalized Graph Query Next, we present Generalized Graph Query (GGQ, for short), our proposal to perform graph pattern matching on generalized graphs. Taking into account the different classifications mentioned above, we can say that this proposal allows to carry out structural and semantic, exact, optimal, and based on a type of Regular Pattern Matching queries, allowing the edges of the pattern to be projected on paths (not necessarily edges). Also, GGQ allows to express more complex constraints on each element of the pattern and perform cyclic queries. One of the characteristics that we pursue for our tool is to provide a mechanism to obtain complementary patterns to a given one. This means that if a structure does not verify a pattern it must always verify one of its complementary patterns. As we have seen in previous section, many of the tools developed to perform queries of patterns in graphs require for a projection to be fulfilled between the pattern and the structure to be evaluated. This projection prevents us from evaluating the non existence of elements, something that we will need to generate these complementary patterns, for this reason our proposed matching system will not make use of projections, but is based on logical predicates, facilitating the generation of complementary patterns. We want to emphasize that one of our main goals is to provide a complete formalization of the model, but with the secondary objective of providing an implementation that is usable from a practical point of view 5(as a proof of concept more than as a professional tool in this first stage). In pursuit of our objectives, we will rely on Selection Graph model, extending it to add Regular Pattern Matching and some additional features that will allow us to obtain a greater expressiveness power in the patterns. As main differences with the query systems from the previous section we can indicate that: •GGQ may contain cycles. It will be a later problem to consider implementations of GGQs that handle cycles properly, considering additional constraints to ensure certain levels of efficiency in their actual execution, or being careful when designing the query to create a pattern that is efficient in the available implementation. •GGQ can evaluate subgraphs. In selection graphs it is only possible to evaluate a single node representing the target table. In the case of GGQ, fixed elements (elements that must belong to the subgraph under evaluation) will be represented through a predicate that forces them to be contained in the subgraph to be evaluated. •Individual edges of the GGQ can be projected onto paths in the graph where the pattern is being checked. For this reason, predicates will be used in a similar way as in Regular Pattern Matching. •The predicates associated with nodes or edges in the GGQ can evaluate structural and semantic characteristics beyond the properties stored through the µfunction (for example, using metrics on the graph or its elements). 5https://github.com/palmagro/ggq 7 We will briefly formalize what we understand concretely by a predicate defined on a graph. Consider Θ, a collection of function, predicate, and constant symbols, containing all the functions from µtogether with constants associated with each element of the graph and possibly some additional symbols (for example, metrics defined on the elements of the graph). From this set of symbols we can define a First Order Language with equality, L, making use of Θ as a set of non logical symbols, on which we construct, in the usual way, the set of terms of the language and the set of formulas, FORM(L), which we will call predicates. Although, generally, the definable formulas in Lcan be applied to all objects in the universe, which in our context will consist in elements of graphs (nodes, edges, and structures formed from them), when we want to make explicit the types of objects we are working with, we can write FORMV(L) for formulas on nodes, FORME(L) for formulas on edges, FORMP(L) for formulas on paths, etc. In order to simplify the notation, when there is no possibility of confusion we will use FORM to denote FORM(L). In addition, and taking advantage of the expressiveness capacity of generalized graphs, we define the query system using the same structure: Definition 6. AGeneralized Graph Query (GGQ) over Lis a binary generalized graph, Q= (VQ, EQ, µQ), where exist αand θ, properties in µQ, such that: •α:VQ∪EQ→ {+,−} total. •θ:VQ∪EQ→FORM(L)associates a binary predicate, θx, to each element xof VQ∪EQ. We will write Q∈GGQ(L) to denote that Qis a Generalized Graph Query over L(if the language is prefixed, we simply write Q∈GGQ). In the semantics associated with a GGQ we will use the second input of these binary predicates to impose requirements of membership on subgraphs of G(the general graph on which we are evaluating queries), whereas the first input must receive elements of the corresponding type to which it is associated: if Sis a subgraph and a∈VQthen θa(., S)∈FORMV, and if e∈EQthen θe(., S)∈F ORMP. For example: θa(v, S) = ∃z∈S(z v) θe(ρ, S) = ∃y, z(yρ z∧y /∈S∧z∈S) θa(v, S) will work for nodes, and it will be verified when there is a path in Gthat connects a node of S(the subgraph we are evaluating) with v, the input node on which it is evaluated. θe(ρ, S) will work for paths, and will be verified when the evaluated path, ρ, connects Swith its complementary (in G). Given a GGQ under the above conditions, x+, respectively x−, will indicate that α(x) = +, respectively α(x) = −, and V+ Q/V − Q(respectively, E+ Q/E− Q) the set of positive/negative nodes (respectively, edges). If for an element, θxis not explicitly defined, we assume it to be a tautology (generally denoted by T). As we will see below, positive elements of the pattern represent elements verifying the associated predicates that must be present in the graph, while negative ones represent elements that should not be present in the graph. 8 In order to be able to express more easily the necessary conditions that define the application of a GGQ on a graph, as well as the results that we will see later, we introduce the following notations: Definition 7. Given a GGQ, Q= (VQ, EQ, µQ), the set of Q-predicates associated to Qis: 1. For each edge, e∈EQ, we define: Qeo(v, S) = ∃ρ∈ Po v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) Qei(v, S) = ∃ρ∈ Pi v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) In general, we will write Qe∗(v, S), where ∗ ∈ {o, i}, and we will denote: Q+ e∗=Qe∗, Q− e∗=¬Qe∗ 2. For each node, n∈VQ, we define: Qn(S) = ∃v∈V ^ e∈γo(n) Qα(e) eo(v, S)∧^ e∈γi(n) Qα(e) ei(v, S)  =∃v∈V ^ e∈γ∗(n) Qα(e) e∗(v, S)  That can be written generally as: Qn(S) = ∃v∈V ^ e∈γ(n) Qα(e) e(v, S)  In addition, we denote: Q+ n=Qn, Q− n=¬Qn From these notations, we can formally define when a subgraph matches a given GGQ: Definition 8. Given a subgraph Sof a property graph, G= (V, E, µ), and a Generalized Graph Query, Q= (VQ, EQ, µQ), both over language L, we say that Smatches Q, and we will denote SQ, if the next formula is verified: Q(S) = ^ n∈VQ Qα(n) n(S) Otherwise, we will write: S2Q. Note that, in particular, using S=Gwe can define when a graph matches a GGQ. A generic GGQ example is shown in Figure 1. One of the objectives for GGQ is to provide power enough to express conditions that make use of elements that are outside the subgraph being evaluated, something that has been proven necessary to have a powerful query language 9 Definition 11. Given Q1, Q2∈GGQ, we say that Q1is a Q−-conservative extension of Q2, and we will denote it by Q2⊆−Q1, if: 1. Q2⊆Q1(as generalized graphs, so in the Q2elements the values of αand θshould coincide for both GGQ). 2. For each negative node in Q2,n∈V− Q2, and every edge incident to it in Q1,e∈γQ1(n), exists an edge incident to it in Q2,e0∈γQ2(n), imposing the same restriction, that is: Qe≡Qe0. Figure 11: Q−-conservative extension. Figure 11 shows an example of a conservative Q−-extension. The extension made in the GGQ on the left to get the GGQ on the right imposes new restrictions on the positive node but does not add any further restrictions to the negative node. Since negative nodes add non-existence constraints to subgraph verification, conservative Q−-extensions ensure that new constraints are not being added to them. Hence, we can give the next result: Theorem 2. Given Q1, Q2∈GGQ, if Q2⊆−Q1then Q1Q2. Proof. Since Q-predicates associated to edges depend only on the information in the edge itself (which considers the value of θat its incident nodes, regardless of the value of αin them), we can state: ∀e∈EQ2(Q1α(e) e=Q2α(e) e) Considering this fact, we analyse how the Q-predicates associated with the nodes for both GGQ behave: •If n∈V− Q2, since Q2⊆−Q1, is trivial that Q1− n=Q2− n. •If n∈V+ Q2, then Q1+ n→Q2+ n, because (we will note γ1,γ2the incidence 16 functions of Q1and Q2, respectively): Q1+ n=∃v∈V ^ e∈γ1(n) Q1α(e) e  =∃v∈V ^ e∈γ1(n)∩EQ2 Q1α(e) e∧^ e∈γ1(n)rEQ2 Q1α(e) e  =∃v∈V ^ e∈γ2(n)∩EQ2 Q2α(e) e∧^ e∈γ1(n)rEQ2 Q1α(e) e  →Q2+ n Hence: Q1=^ n∈VQ1 Q1α(n) n=^ n∈VQ2 Q1α(n) n∧^ n∈VQ1rVQ2 Q1α(n) n =^ n∈V+ Q2 Q1α(n) n∧^ n∈V− Q2 Q1α(n) n∧^ n∈VQ1rVQ2 Q1α(n) n →^ n∈V+ Q2 Q2α(n) n∧^ n∈V− Q2 Q2α(n) n∧^ n∈VQ1rVQ2 Q1α(n) n =^ n∈VQ2 Q2α(n) n∧^ n∈VQ1rVQ2 Q1α(n) n →Q2 Previous result suggests that a GGQ can be refined by adding nodes (of any sign) and edges to the existing positive nodes, but because of the (negated) interpretation of Q-predicates associated with negative nodes, care must be taken to maintain their environment to be sure that adding more edges does not weaken the imposed conditions (and, therefore, we would not get refined predicates). In order to obtain controlled methods of query generation, in the following we will give a constructive method to refine GGQ by unit steps. To do this, we will start by looking at how GGQ behaves when cloning nodes. A clone consists of making copies of existing nodes, and cloning all the edges incident on them (and between them, in case we clone several nodes that are connected in the original GGQ). Of course, the cloning operation can be done on any generalized graph, not only on GGQ. Definition 12. Given a generalized graph G= (V, E, µ), and W⊆V, we define the clone of Gby duplication of W, denoted by ClW G, as: ClW G= (V∪W0, E ∪E0, µ ∪ {(n0, µ(n))}n∈W∪ {(e0, µ(e))}e0∈E0) where: 17 •for each n∈W,n0is a new node, and W0={n0:n∈W}, •E0is a set of new edges obtained from incident edges on nodes of Wwhere nodes of Ware replaced by copies of W0(edges connecting original nodes with cloned nodes, and edges connecting cloned nodes, are cloned). Figure 12: Clone of a graph Figure 12 shows an example of a cloned graph by duplicating two of its nodes. In the original graph, on the left, the set of nodes to be cloned are highlighted. The result of the cloning is presented in the graph to the right. The following result shows that cloning positive nodes does not alter the meaning of the queries. Theorem 3. If Q∈GGQ and W⊆V+ Q, then ClW Q≡Q. Proof. To facilitate the notation, let Q1=ClW Q. Then, following a similar reasoning to that of the previous proof: Q1=^ n∈VQ1 Q1α(n) n =^ n∈VQ Q1α(n) n∧^ n∈W Q1α(n0) n0 =^ n∈VQrγQ(W) Q1α(n) n∧^ n∈γQ(W) Q1α(n) n∧^ n∈W Q1α(n0) n0 =^ n∈VQrγQ(W) Qα(n) n∧^ n∈γQ(W) Qα(n) n∧^ n∈W Qα(n) n =Q Continuing with the idea of obtaining tools to build GGQ automatically, the following concept of refinement completes the operations that we need to refine a GGQ. A refinement set forms a kind of partition of a given GGQ. 18 Definition 13. Given Q∈GGQ,R⊆GGQ is a refinement set of Qin Gif: 1. ∀Q0∈R(Q0GQ) 2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0)) We are now ready to present some refinement sets that will allow to automate the processes of creation and modification of Generalized Graph Query. Let’s start with the simplest operation, which allows to add new nodes to an existing GGQ: Theorem 4 (Add new node to Q).Given Q∈GGQ and m /∈VQ, the set Q+{m}, formed by: Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T)) Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T)) is a refinement set of Qin G(Fig. 13). Proof. We must verify that the two necessary conditions for refinement sets are verified: 1. It is trivial that Q⊆−Q1and Q⊆−Q2, thus Q1Qand Q2Q. 2. Given S⊆Gsuch that SQ. Then: Q1=Q∧Qm Q2=Q∧ ¬Qm where Qm=∃v∈V(T). If G6=∅, then SQ1and S2Q2. If G=∅, then S2Q1and SQ2. Usually, G6=∅, hence this operation does not really refine, in the sense that Q1≡Qand Q2≡ ¬T. However, although we obtain an equivalent GGQ, this operation is very useful to add new nodes to a GGQ in order to add new restrictions to them later. Figure 13: Refinement Add node We proceed now to give a second refinement set that allows to create edges between existing nodes. In order to get a refinement of the original GGQ we must restrict the addition of edges to positive nodes. 19 Theorem 5 (Add new edge between postive nodes of Q).Given Q∈GGQ and n, m ∈V+ Q, the set Q+{n+e∗ −→ m+}(∗ ∈ {+,−}), formed by (where Q0=Cl{n,m} Q): Q1= (VQ0, EQ0∪ {n+e∗ −→ m+}, θQ0∪(e, T)) Q2= (VQ0, EQ0∪ {n+e∗ −→ m−}, θQ0∪(e, T)) Q3= (VQ0, EQ0∪ {n−e∗ −→ m+}, θQ0∪(e, T)) Q4= (VQ0, EQ0∪ {n−e∗ −→ m−}, θQ0∪(e, T)) is a refinement of Qin G(Fig. 14). Proof. 1. Since Q0is a clone of Q, and {n, m} ⊆ V+ Q, then Q≡Q0. In addition, Q0⊆−Q1, Q2, Q3, Q4, thus Q1, Q2, Q3, Q4Q0≡Q. 2. Let us consider the predicates: Pn=∃v∈V ^ a∈γ(n) Qα(a) a∧Qα(e) eo  Pm=∃v∈V ^ a∈γ(m) Qα(a) a∧Qα(e) ei   If SQnand SQm, then we have four mutually complementary options: •SPn∧SPm⇒SQ1 •SPn∧S2Pm⇒SQ2 •S2Pn∧SPm⇒SQ3 •S2Pn∧S2Pm⇒SQ4 If n=m(eis a loop) then the previous refinement set is {Q1, Q4}. Next operation adds an additional predicate to an existing edge. To keep the necessary structural conditions, this operation is restricted to positive edges connecting positive nodes. Theorem 6 (Add predicate to positive edge between positive nodes of Q). Given Q∈GGQ and n, m ∈V+ Q, with n+e+ −→ m+, and ϕ∈FORM, the set denoted by Q+{n+e∧ϕ −→ m+}, formed by (where Q0=Cl{n,m} Q): Q1=(VQ0, EQ0∪ {n+e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q2=(VQ0, EQ0∪ {n+e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) Q3=(VQ0, EQ0∪ {n−e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q4=(VQ0, EQ0∪ {n−e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) is a refinement set of Qin G(Fig. 15). 20 Figure 14: Refinement Add edge Proof. The proof is similar to those shown in previous results. Figure 15: Refinement Add predicate to edge Finally, the last operation adds predicates to existing nodes. Again, we restrict this operation to cases when the affected nodes are positive (the node where the predicate is added, and those connected to it). Theorem 7 (Add predicate to positive node with positive environment in Q). Given Q∈GGQ,n∈V+ Q, with NQ(n)⊆V+ Q, and ϕ∈FORM. We define the set Q+{n∧ϕ}formed by: {Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)} where Q0=ClNQ(n) Q, and {+,−}NQ(n)is the set of all possible assignations of signs to elements in NQ(n). Then Q+{n∧ϕ}is a refinement set of Qin G(Fig. 16). Proof. The proof is similar to the previous cases. It is only necessary to take into account that, when modifying the node n, not only the Q-predicate associated with it is modified but also those from all its adjacent nodes, and the set of functions {+,−}NQ(n)cover all possible sign assignment for the nodes in the environment. 21 Figure 16: Refinement Add predicate to node It should be noted that these refinements generate structures that can be simplified. Next we provide some operations to simplify a GGQ and to obtain another equivalent and simpler one. Definition 14. Given Q∈GGQ,Q0⊆Qis redundant in Qif Q≡Q−Q0. Where Q−Q0is the subgraph of Qgiven by: (VQrVQ0, EQr(EQ0∪ {γ(n) : n∈VQ0}), µQ) Let us see a first result that allows to obtain simplified versions of a GGQ by removing positive redundant nodes: Theorem 8. Given Q∈GGQ, and n∈V+ Qsuch that exists m∈VQverifying: •α(n) = α(m),θn≡θm. •For each e∈γ(n), exists e0∈γ(m), verifying α(e) = α(e0),θe=θe0and γ(e)r{n}=γ(e0)r{m}. Then, nis redundant in Q. Essentially, mis a clone of n, but possibly with more edges connected. We can obtain a similar result for edges: Theorem 9. Given Q∈GGQ, and two edges, e, e0∈EQ, such that n+e −→ m+ and n+e0 −→ m+. If θe→θe0then e0is redundant in Q. From these two results we can give simplified versions of the previous refinement sets, grouping positive nodes and positive edges when, after initial cloning, the sign of the duplicate element has been maintained with the original, as well as in the cases where the sign has been maintained and an additional predicate 22 Figure 17: Refinement Add edge (simplified) Figure 18: Refinement Add predicate to edge (simplified) has been added. Figures 17 to 19 shows representations of the refinement sets Q+{n∧ϕ},Q+{n+e∧ϕ −→ m+}and Q+{n∧ϕ}applying these simplifications. For example, the following sequence of refinements constructs the pattern P5(Fig. 20): Q1=Q∅+{n1} Q2=Q1+{n1∧(v∈S∧τ(v)6=institution ∧τ(v)6=clan} Q3=Q2+{n2} Q4=Q3+{n2 e1 −→ n1} P5=Q4+{n2 e1∧(τ(ρ)=DEVOTED TO) −→ n1} From the structure of a GGQ it is not easy to obtain a complementary GGQ with it. However, there are many analysis on property graphs (or generalized graphs) where we need to work with sequences of queries verifying some properties of containment and complementarity as predicates. The refinements presented in this section come to cover this gap and to allow, for example, the construction of an embedded partition tree with the nodes labelled as follows (Fig. 21): •The root node is labelled with Q0(some initial GGQ). 23 Figure 19: Refinement Add predicate to node (simplified) Figure 20: Sequences of refinements for P5 •If a tree node is labelled with Q, and R= (Q1, . . . , Qn) is a refinement set of Q, then its child nodes are labelled with the elements of R. Note that the construction of this tree completely depends on the refinement chosen in each branch, and the initial GGQ. The refinements presented here are only one option, but not the only one. For example, we could consider refinements that, instead of adding constraints to positive elements, lighten the conditions over negative elements, and using disjunction of predicates instead of conjunction of them. 7 Conclusions and Future Work In this work we have presented a framework to evaluate subgraphs immersed in property graphs (more generally, in generalized graphs) that can be used in discovery procedures over relational data. We want this framework to verify several requirements: •To use the same grammar for the queries and for the structures to evaluate. 24 Figure 21: Refinements tree Thanks to the expressive power of generalized graphs we have presented a query tool that can be expressed by using generalized graphs. •To provide well-founded basis that would assure the queries behave consistently and robustly. These results have been obtained by studying the relationships between the topological structure of the query and the logical meaning of the query. •In addition, we have provided a controlled way to construct GGQ by means of atomic operators that translates the topological control of the construction into a logical control of the meaning. In this sense, we have introduced a first family of refinements to achieve this goal. Because relational data can be viewed as graphs, and queries can be viewed as pattern searchs, most query languages in databases can be viewed as (perhaps primitive) graph pattern matching tools. In this paper we have analysed some of the existing query tools as well as the feasibility to be used in automatic procedures. One of these tools, Selection Graphs, allows to evaluate records in relational databases through acyclic patterns that can be refined by using basic operations, and allowing to obtain complementary patterns in each case. They do not require an exact projection of the pattern representing the selection graph onto the subgraph to be evaluated, but rather the fulfillment of a series of predicates expressed in the pattern. We must remember that if a projection is required when carrying out the verification of a pattern, the task of evaluating the non-existence of certain elements becomes hard. Specifically, selection graphs evaluate the existence / non-existence of paths incidents into the record under evaluation (they are only capable of evaluating individual records) by verifying a conjunction of predicates associated to those paths, and it can be seen as the evaluation of existence of a tree rooted in the node that represents the record under evaluation. Generalized Graph Query extends the concept of selection graphs allowing the evaluation of general subgraphs, beyond a single node, the use of more powerful predicates and allowing cyclical patterns. As it becomes a requirement not to use a projection for the verification of a pattern, these objectives have been achieved by extending the form of evaluation, which can be seen as the evaluation of a tree rooted in every node from the pattern (allowing the edges to be identified with paths in the graph). Consequently, it manages more complex 25 flujo de datos que permite a los usuarios expresar de manera sencilla consultas complejas en grafos. De esta forma, cada consulta est´a compuesta por una secuencia de pasos que realizan operaciones at´omicas en el flujo de datos. Gremlin permite realizar consultas sem´anticas, exactas, ´optimas, y basadas en isomorfismos de subgrafos de manera natural. Dado que Gremlin es un lenguaje, un juego de instrucciones y una m´aquina virtual, es posible dise˜nar otros lenguajes de consulta en grafos que compilen al lenguaje Gremlin (por ejemplo, SPARQL puede ser compilado para ejecutarse en una m´aquina Gremlin1). Los Grafos de Selecci´on son un tipo de patrones multi-relacionales para consultar bases de datos basadas en la tecnolog´ıa SQL. Representan los cimientos sobre los que est´a construido el algoritmo de inducci´on de ´arboles de decisi´on multi-relacionales MRDTL [13] as´ı como otros algoritmos de aprendizaje autom´atico multi-relacionales [15]. El objetivo final de los grafos de selecci´on es su uso en procedimientos de b´usqueda de patrones de tipo top-down [12], y para ello se necesitan operadores que permitan modificar, a trav´es de peque˜nos cambios, un grafo de selecci´on dado. Adem´as, permiten una representaci´on gr´afica muy expresiva y pueden ser construidos en pasos sucesivos, ofreciendo buenas condiciones para ser utilizados en procedimientos de descubrimiento. Es por estas razones por las que nuestra propuesta se puede considerar una generalizaci´on de algunas de las ideas que promovieron esta aproximaci´on. Como contraparte, presentan el inconveniente de que los patrones que representan no pueden contener ciclos, limitando as´ı la potencia expresiva de las consultas. Los grafos de selecci´on representan un tipo de Graph Pattern Matching exacto, ´optimo y basado en el isomorfismo sem´antico de grafos. Adem´as, al ser una representaci´on gr´afica de las consultas SQL, hereda los problemas de eficiencia que presentan los sistemas basados en esta tecnolog´ıa. Cypher es un lenguaje de consulta declarativo desarrollado espec´ıficamente para trabajar sobre la base de datos en grafo Neo4j2. Cypher est´a dise˜nado para ser un lenguaje de consulta humano, cercano tanto para desarrolladores como para usuarios finales, y las consultas de patrones en grafos que habitualmente son complicadas en otros lenguajes resultan muy sencillas en ´el [2], mostrando una alta capacidad expresiva [1]. La base de datos Neo4j sigue con mucha fidelidad el modelo de grafo con propiedades, pero obliga que las aristas tengan un tipo asociado. A diferencia con Gremlin, Cypher no es Turing completo, por lo que presenta algunas limitaciones (por ejemplo, no es capaz de llevar a cabo algunos algoritmos de an´alisis en grafos), y es de m´as alto nivel (por ejemplo, no es capaz de expresar la forma en la que se quiere paralelizar una consulta). Las consultas sencillas en Cypher poseen un buen rendimiento, sin embargo no siempre es as´ı cuando las consultas siguen patrones complejos, ya que cuando hay condiciones m´ultiples Cypher no permite indicar en qu´e orden aplicar dichas condiciones. Cypher permite consultas de patrones en grafos estructurales y sem´anticas, ´optimas, exactas, y basadas en el isomorfismo de subgrafos. Adem´as, permite un tipo de Regular Pattern Matching en el que las aristas en el patr´on se proyecten sobre caminos del grafo, y se pueden imponer restricciones a esos caminos a trav´es de expresiones que hacen uso del operador disyunci´on y del cierre de Kleene. Una limitaci´on desde el punto de vista acad´emico es que carece de un modelo formal asociado, y se ha construido con un car´acter 1https://github.com/dkuppitz/sparql-gremlin 2http://neo4j.org 4 completamente aplicado, por lo que algunas de sus operaciones no han sido validadas. A pesar de ello, por su excelente expresividad y aceptable rendimiento, y porque consume los datos de una base de datos en grafo muy extendida en su uso, Cypher es el lenguaje base que se ha elegido para implementar Generalized Graph Query, nuestra propuesta para llevar a cabo consultas de patrones en grafos con propiedades. Algunas otras herramientas relacionadas con la consulta de patrones en grafos son: GraphLog [6], que permite estructurar las consultas en forma de grafo y eval´ua la existencia de un patr´on determinado entre un par de nodos para generar una nueva arista entre ´estos; GraphQL3, lenguaje de consulta declarativo desarrollado por la compa˜n´ıa Facebook para permitir el acceso a su informaci´on por parte de aplicaciones externas; Graql4, lenguaje de consulta declarativo orientado a grafos de conocimiento; y PGQL [19], que representa una extensi´on SQL con caracter´ısticas propias de las consultas en grafos: an´alisis de accesibilidad entre nodos, localizaci´on de caminos, y construcci´on de grafos. 3. Definiciones Previas Dado Vun conjunto cualquiera, denotaremos por: V0=∅, V 1=V, V n+1 =Vn×V, V ∗=[ n≥0 Vn En general, a los elementos de V∗los llamaremos secuencias,sucesiones o listas. Si x∈Vnentonces diremos que xtiene longitud n, y escribiremos |x|=n. Si x= (a1, . . . , an), y = (b1, . . . , bm)∈V∗, entonces la concatenaci´on de x eyes el elemento de V∗dado por xy = (a1, . . . , an, b1, . . . , bm). Para cada x= (a1, . . . , an)∈Vn, llamaremos conjunto soporte de xal conjunto s(x) = {ai: 1 ≤i≤n},. y, por un abuso del lenguaje, escribiremos a∈xpara indicar que a∈s(x). Para cada a∈V, denotamos |a|x= #{i:xi=a}(donde #(A) denota el cardinal del conjunto A), y llamaremos multiconjunto soporte de xal conjunto de pares ms(x) = {(a, |a|x) : a∈x}. A partir de los multiconjuntos soporte podemos definir la relaci´on ∼, que se puede probar f´acilmente que es de equivalencia en Vn, como: x∼ysi y solo si ms(x) = ms(y), y denotaremos por Vn ∼=Vn/∼(conjunto cociente de Vn bajo la relaci´on ∼). Nuestra interpretaci´on de estos conjuntos ser´a que, as´ı como Vndenota el conjunto de tuplas ordenadas de elementos de V,Vn ∼denota el conjunto de tuplas no ordenadas del mismo conjunto (es decir, tuplas en las que importan los elementos que aparecen, considerando las posibles repeticiones, pero no el orden en el que aparecen). A continuaci´on presentamos la definici´on de Grafo Generalizado, que abarca las diferentes variantes de grafo que se pueden encontrar en la literatura y que necesitaremos a la hora de presentar nuestra propuesta de consulta de patrones en grafos. Definici´on 1. Un Grafo Generalizado es una tupla G= (V, E, µ)donde: 3http://graphql.org/ 4https://grakn.ai 5 VyEson conjuntos, que llamaremos, respectivamente, conjunto de nodos yconjunto de aristas de G. µes una relaci´on (habitualmente la consideraremos funcional, pero no es necesario) que asocia a cada nodo o arista en el grafo su conjunto de propiedades, es decir, µ: (V∪E)×R→S, donde Rrepresenta el conjunto de posibles claves para dichas propiedades, y Sel conjunto de posibles valores asociados a las mismas. Habitualmente, para cada α∈Ryx∈V∪E, escribiremos α(x) = µ(x, α). Adem´as, exigiremos la existencia de una clave destacada para las aristas del grafo, que llamaremos incidencias y denotaremos por γ, que asocia a cada arista del grafo una tupla, ordenada o no, de v´ertices del grafo. Aunque la definici´on que hemos presentado aqu´ı es m´as general que las que se pueden encontrar en la literatura relacionada, tambi´en los denominaremos Grafos con Propiedades, ya que suponen una extensi´on natural de este tipo de grafos. Cabe indicar que en los grafos generalizados que acabamos de mostrar, y a diferencia de las definiciones tradicionales, los elementos en Eson s´ımbolos que representan a las aristas y no pares de elementos de V, y es γla funci´on que asocia a cada arista el conjunto de v´ertices que relaciona. Definici´on 2 (Notaci´on y definiciones).En el contexto de las definiciones anteriores, usaremos la siguiente notaci´on: Habitualmente identificaremos econ γ(e), de forma que si v∈Vescribiremos v∈epara denotar que v∈γ(e). As´ı, interpretamos la arista como la colecci´on de nodos que conecta, tal y como siguen las definiciones m´as cl´asicas de grafos. De forma sim´etrica, para cada u∈Vescribiremos γ(u) = {e∈E:u∈ e}. En general, un grafo generalizado puede tener combinaci´on de aristas dirigidas y no dirigidas. Si γ:E→V∗diremos que el grafo es Dirigido. Si γ:E→V∗ ∼diremos que el grafo es No Dirigido. Para cada e∈E, se define la aridad de ecomo Pa∈e|a|e. Si γ:E→V2∪V2 ∼diremos que el grafo es Binario (y coincide con la estructura de grafo m´as habitual). En caso contrario, diremos que el grafo es un Hipergrafo. Una arista, e∈E, se dice que es un lazo si conecta un nodo con ´el mismo, es decir, si tiene aridad distinta a 1 pero s(e)es unitario. Una arista, e∈E, se dice incidente en un nodo, v∈V, si v∈e. Dos nodos distintos, u, v ∈Vse dicen adyacentes, o vecinos, en Gsi existe e∈Etal que {u, v} ⊆ e. Si existen aristas distintas en Econ la misma incidencia, es decir, aristas que conectan los mismos nodos, diremos que el grafo es un Multi-grafo. 6 Si ees una arista binaria dirigida que conecta ucon v,e= (u, v), escribiremos ue →v, y tambi´en notaremos eo=u(output de e) y ei=v(input de e). En este caso, para cada u∈Vescribiremos: γo(u) = {e∈γ(u) : eo=u} γi(u) = {e∈γ(u) : ei=u} que denotan, respectivamente, el conjunto de aristas salientes de uy el conjunto de aristas entrantes en u. Dado u∈V, definimos el entorno de uen Gcomo el conjunto de nodos, incluyendo a u, que est´an conectados con ´el, es decir: N(u) = Se∈γ(u)γ(e). Cuando sea necesario hablaremos del entorno reducido de ucomo N∗(u) = N(u)\ {u}. La noci´on de subgrafo se obtiene de la definici´on habitual a˜nadiendo a las condiciones habituales de contenci´on de nodos y aristas la condici´on de que las propiedades tambi´en se mantengan en los elementos comunes. Definici´on 3. Un subgrafo de un grafo G= (V, E, µ)es un grafo S= (VS, ES, µS) tal que VS⊆VyES⊆EyµS⊆µ|VS∪ES. Notaremos S⊆G. Un concepto fundamental al trabajar con grafos es el de camino, que permite estudiar relaciones de distancia y condiciones de conectividad entre diferentes elementos, extendiendo la conectividad de las aristas a situaciones m´as generales. Debido a que nuestros grafos son considerablemente m´as generales que los habituales (hasta el punto de contener el concepto de hipergrafo, que generalmente no se cubre en la Teor´ıa de Grafos cl´asica) hemos de dar previamente algunas nociones que permitan hablar de la posici´on de orden que ocupa un nodo en una arista: Definici´on 4. Si e∈Eyγ(e) = (v1, . . . , vn)∈Vn, entonces para cada vi∈s(e) definimos su orden en ecomo orde(vi) = i. Si e∈Vn ∼, entonces para cada v∈s(e)definimos orde(v)=0. Este orden define de forma natural un orden entre los nodos incidentes en una arista, y escribiremos u≤evpara indicar que orde(u)≤orde(v). A partir de esta relaci´on de orden entre los nodos que conecta una arista, podemos definir de manera general qu´e entendemos por un camino dentro de un grafo. Definici´on 5. Dado un grafo G= (V, E, µ), el conjunto de caminos en G, que denotaremos por PG, se define como el menor conjunto verificando las siguientes condiciones: 1. Si e∈E,u, v ∈econ u≤ev, entonces ρ=ue →v∈ PG, y sopV(ρ) = (u, v),sopE(ρ)=(e). Diremos que ρune (o conecta) los v´ertices uyvde G, o que ves accesible desde upor medio de ρ, y lo notaremos por uρ v. 2. Si ρ1, ρ2∈ PG, con uρ1v, v ρ2 w, entonces ρ1·ρ2∈ PG, con uρ1·ρ2 w, sopV(ρ1·ρ2) = sopV(ρ1)sopV(ρ2),sopE(ρ1·ρ2) = sopE(ρ1)sopE(ρ2). En caso de que u=vdiremos que ρes un camino cerrado, y si adem´as no se repiten aristas en ρdiremos que es un ciclo. 7 Si ρ∈ PG, con sopV(ρ) = (u1, . . . , un+1) y sopE(ρ) = (e1...,en), entonces escribiremos: ρ=u1 e1 →u2 e2 →. . . en →un+1 En general, y como no hay confusi´on, escribiremos u∈ρpara expresar que u∈sopV(ρ), y e∈ρpara expresar que e∈sopE(ρ). Nota. Siguiendo una notaci´on similar al caso de las aristas binarias dirigidas, si ρ∈ P(G)yuρ v, entonces escribiremos ρo=uyρi=v. Cuando sea necesario, notaremos los caminos que pasan por u, que comienzan en u, y que acaban en u, respectivamente, por: Pu(G) = {ρ∈ P(G) : u∈ρ} Po u(G) = {ρ∈ P(G) : ρo=u} Pi u(G) = {ρ∈ P(G) : ρi=u} 4. Generalized Graph Query A continuaci´on presentamos Generalized Graph Query (GGQ, para abreviar, a partir de ahora), nuestra propuesta para llevar a cabo consultas de patrones en grafos. Teniendo en cuenta las diversas clasificaciones apuntadas anteriormente, podemos decir que esta propuesta permite llevar a cabo consultas estructurales y sem´anticas, exactas, ´optimas, y basadas en un tipo de Regular Pattern Matching que permite, adem´as de proyectar aristas del patr´on en caminos (no necesariamente aristas) que cumplan las restricciones impuestas, expresar restricciones m´as complejas sobre cada elemento del patr´on y realizar consultas que posean ciclos. Una de las caracter´ısticas que buscamos en nuestra herramienta es que permita obtener (de alguna manera) patrones complementarios a un patr´on dado. Esto significa que si una estructura no verifica un patr´on debe verificar siempre uno de sus patrones complementarios. Como hemos visto en la secci´on anterior, muchas de las herramientas desarrolladas para llevar a cabo consultas de patrones en grafos exigen que se cumpla una proyecci´on entre el patr´on y la estructura a evaluar. Dicha proyecci´on impide evaluar la no existencia de elementos, algo que vamos a necesitar para generar estos patrones complementarios, por lo que nuestra propuesta no se basa en una proyecci´on a la hora de verificar si una estructura cumple con un patr´on determinado, sino que ser´a construida en base a predicados l´ogicos, que facilitar´an la generaci´on de patrones complementarios. Hemos de indicar que nuestro objetivo principal es el de proporcionar una formalizaci´on completa del modelo (frente a implementaciones incompletas desde el punto de vista formal, pero operativas), pero con el objetivo secundario de proporcionar una implementaci´on que sea utilizable desde un punto de vista pr´actico5(aunque m´as como una prueba de concepto que como una herramienta profesional en esta primera etapa). 5https://github.com/palmagro/ggq 8 En busca de nuestros objetivos, nos apoyaremos en el concepto de Grafo de Selecci´on visto anteriormente, ampli´andolo para a˜nadirle Regular Pattern Matching y algunas caracter´ısticas adicionales que nos permitir´an obtener una mayor potencia expresiva en los patrones que se pueden construir. Como principales caracter´ısticas diferenciadoras respecto de los sistemas de consulta vistas en el apartado anterior, podemos indicar que: Los GGQ pueden contener ciclos. Ser´a un problema posterior considerar implementaciones de los GGQ que manipulen los ciclos adecuadamente, considerar restricciones adicionales para asegurar ciertos niveles de eficiencia en su ejecuci´on real, o preocuparse en la etapa de dise˜no de la consulta de crear un patr´on que sea eficiente en la implementaci´on disponible. Los GGQ pueden evaluar subgrafos. Recordemos que en los Grafos de Selecci´on cl´asicos s´olo es posible evaluar un ´unico nodo que representa a la tabla target. En el caso de los GGQ, los elementos fijos (elementos que deben pertenecer al subgrafo bajo evaluaci´on) ser´an representados a trav´es de un predicado que obliga a que dichos elementos est´en contenidos en el subgrafo a evaluar. Las aristas individuales del GGQ pueden ser proyectadas sobre caminos en el grafo en el que se comprueba el patr´on. Para ello se har´a uso de predicados de forma similar a como se hace en Regular Pattern Matching. Los predicados asociados a nodos o aristas en el GGQ pueden evaluar caracter´ısticas estructurales y sem´anticas m´as all´a de las propiedades almacenadas a trav´es de la funci´on µ(por ejemplo, a trav´es de m´etricas sobre el grafo o sus elementos). Aunque ya hemos mencionado que podemos disponer de un conjunto de predicados asociados a los elementos del patr´on, vamos a formalizar brevemente qu´e entendemos concretamente por un predicado definido sobre un grafo. Tal y como muestra su definici´on, asociado a un grafo con propiedades tenemos una funci´on µque representa un conjunto de funciones (en particular, pueden ser predicados) asociadas a nodos y aristas del grafo. Consideremos Θ, una colecci´on de s´ımbolos de funci´on, predicados y constantes, que contiene todas las funciones de µjunto con constantes asociadas a cada elemento del grafo y, posiblemente, algunos s´ımbolos adicionales, tanto de funciones como de predicados y constantes (por ejemplo, m´etricas definidas sobre los elementos del grafo). A partir de este conjunto de s´ımbolos podemos definir un Lenguaje de Primer Orden con igualdad, L, haciendo uso de Θ como conjunto de s´ımbolos no l´ogicos, sobre el que construimos, de la forma usual, el conjunto de t´erminos del lenguaje y el conjunto de f´ormulas, FORM(L), que llamaremos predicados. Aunque, en general, las f´ormulas definibles en Lse pueden aplicar a todos los objetos del universo, que en nuestro contexto estar´a compuesto por elementos de grafos (nodos, aristas, y estructuras formadas a partir de ´estos), cuando queramos explicitar sobre qu´e tipos de objetos estamos trabajando en cada momento, podremos escribir FORMV(L) para indicar que son f´ormulas aplicables sobre nodos, FORME(L) para indicar que son f´ormulas aplicables sobre aristas, FORMP(L) para indicar que son f´ormulas aplicables sobre caminos, etc. En lo que sigue supondremos prefijado un Lenguaje sobre grafos, L, por lo que, con el objetivo de simplificar las expresiones que usemos, notaremos de 9 forma general FORM para denotar FORM(L) cuando no haya posibilidad de confusi´on. Adem´as, y aprovechando la capacidad expresiva de los grafos generalizados, definimos las consultas sobre ellos haciendo uso de las mismas estructuras: Definici´on 6. Un Generalized Graph Query (GGQ) sobre Les un grafo binario con propiedades sobre L,Q= (VQ, EQ, µQ), donde existen αyθ, propiedades destacadas en µQ, tales que: α:VQ∪EQ→ {+,−} total. θ:VQ∪EQ→FORM(L)asocia un predicado binario, θx, a cada elemento xde VQ∪EQ. Escribiremos Q∈GGQ(L) para denotar que Qes un Generalized Graph Query sobre L(si el lenguaje est´a prefijado y no hay posibilidad de confusi´on, escribiremos simplemente Q∈GGQ). El sentido de usar predicados binarios es que en la sem´antica asociada a un GGQ usaremos la segunda entrada de estos predicados para poder hablar de condiciones de pertenencia sobre subgrafos de G(el grafo general sobre el que estamos evaluando las consultas), mientras que la primera esperar´a recibir como entrada elementos adecuados al tipo de elemento al que est´a asociado. As´ı, si Ses un subgrafo y a∈VQentonces θa(., S)∈FORMV, y si e∈EQentonces θe(., S)∈F ORMP. Por ejemplo: θa(v, S) = ∃z∈S(z v) θe(ρ, S) = ∃y, z(yρ z∧y /∈S∧z∈S) El primer predicado tendr´a sentido para nodos, y se verificar´a cuando exista un camino en Gque conecta un nodo de S(el subgrafo que estamos evaluando) con v, el nodo de entrada sobre el que se eval´ua. El segundo predicado tendr´a sentido para caminos, y se verificar´a cuando el camino evaluado, ρ, conecta S con su complementario (en G). Dado un GGQ en las condiciones anteriores, notaremos x+, respectivamente x−, para indicar que α(x) = +, respectivamente α(x) = −, y V+ Q/V − Q(respectivamente, E+ Q/E− Q) el conjunto de nodos (respectivamente, aristas) positivos/negativos. Si para un elemento x,θxno est´a expl´ıcitamente definida, supondremos que θxes una tautolog´ıa, que podemos denotar en general por T. Tal y como veremos a continuaci´on, intuitivamente los elementos positivos del patr´on representan elementos que deben estar presentes en el grafo sobre el que se realiza la consulta y que verifican los predicados asociados, mientras que los elementos negativos en el patr´on representan elementos que no deben estar presentes en el grafo. Para poder expresar con m´as facilidad las condiciones necesarias que definen la aplicaci´on de un GGQ sobre un grafo, as´ı como los resultados que veremos m´as adelante, introducimos a continuaci´on una serie de notaciones que generan predicados aplicables sobre elementos del grafo: Definici´on 7. Dado Q= (VQ, EQ, µQ)un GGQ, el conjunto de Q-predicados asociados a Qes: 10 1. Para cada arista, e∈EQ, definimos los Q-predicados asociados como: Qeo(v, S) = ∃ρ∈ Po v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) Qei(v, S) = ∃ρ∈ Pi v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) En general, escribiremos Qe∗(v, S), donde ∗ ∈ {o, i}, y notaremos: Q+ e∗=Qe∗, Q− e∗=¬Qe∗ 2. Para cada nodo, n∈VQ, definimos el Q-predicado asociado como: Qn(S) = ∃v∈V ^ e∈γo(n) Qα(e) eo(v, S)∧^ e∈γi(n) Qα(e) ei(v, S)  =∃v∈V ^ e∈γ∗(n) Qα(e) e∗(v, S)  Y que podemos escribir en general como: Qn(S) = ∃v∈V ^ e∈γ(n) Qα(e) e(v, S)  ya que para cada nodo no hay posibilidad de confusi´on. Adem´as, notaremos: Q+ n=Qn, Q− n=¬Qn A partir de estas notaciones, podemos definir formalmente cu´ando un subgrafo verifica un GGQ determinado: Definici´on 8. Dado un subgrafo Sde un grafo con propiedades, G= (V, E, µ), y un Generalized Graph Query, Q= (VQ, EQ, µQ), ambos sobre el lenguaje L, diremos que Sverifica Q, y lo denotaremos SQ, si se verifica la f´ormula: Q(S) = ^ n∈VQ Qα(n) n(S) En caso contrario, escribiremos: S2Q. En la Figura 1 se muestra un GGQ gen´erico a modo de ejemplo. Uno de los objetivos que persiguen los GGQ es proporcionar la capacidad expresiva suficiente para expresar condiciones que hacen uso de elementos que est´an fuera del subgrafo que se est´a evaluando, algo que se ha demostrado necesario para disponer de un lenguaje de consultas potente y que, salvo en los grafos de selecci´on, y de forma muy limitada, no est´a presente en el resto de soluciones vistas anteriormente. Obs´ervese que, en particular, usando S=Gpodemos definir cu´ando un grafo verifica un GGQ. Aunque la definici´on de GGQ que hemos presentado hace uso de grafos binarios (no hipergrafos), ya que proyecta aristas sobre caminos que conectan pares 11 Figura 1: Ejemplo de Generalized Graph Query. de nodos, el concepto de grafo generalizado es suficientemente flexible como para permitir otras interpretaciones en las que se pueden considerar GGQs que hagan uso de estructuras m´as generales. Adem´as, y es importante resaltar este hecho, aunque un GGQ sea binario, puede aplicarse sobre grafos con propiedades que no lo sean (es decir, Gpodr´ıa ser un hipergrafo generalizado), ya que el concepto de camino que conecta pares de nodos se define independientemente de la aridad de las aristas que intervienen. En estos casos, se deber´ıa usar una notaci´on algo m´as compleja para poder definir los Q-predicados, pero es completamente factible. Por motivos de simplicidad, y por la falta de bases de datos de hipergrafos, hemos restringido las definiciones presentadas a estos casos particulares, pero quedan abiertas para ser extendidas a los casos m´as generales en el momento en el que el uso de hipergrafos se generalice como medio de modelado y almacenamiento, ya que en la mayor´ıa de las (escasas) ocasiones en que se han necesitado siempre se ha resuelto el problema por medio de la creaci´on de nuevos tipos de nodos y aristas binarias que simulan la presencia de hiperaristas. Antes de pasar a analizar algunas propiedades interesantes sobre los GGQ y la forma de construirlos, veamos algunos ejemplos que permitan entender c´omo se interpretan y qu´e capacidad expresiva permiten. 5. Ejemplos Representativos A lo largo de este par´agrafo, y a modo de ejemplo, presentaremos una colecci´on de peque˜nos GGQ sobre un grafo con propiedades concreto con el objeto de mostrar la forma en que funcionan y su capacidad expresiva. En la Figura 2 se presenta un grafo con propiedades que se corresponde con una secci´on de una base de datos basada en grafos que contiene informaci´on acerca de los personajes principales de la serie Starwars y que es utilizada frecuentemente como ejemplo sencillo para hacer demostraciones relacionadas con las capacidades de las bases de datos en grafo 6. En lo que sigue haremos uso de este grafo para presentar algunos patrones que hagan uso del lenguaje sobre el que est´a definido y para comprobar la verificaci´on de algunos subgrafos 6http://console.neo4j.org/?id=StarWars 12 concretos del mismo. Figura 2: Grafo Starwars para ilustrar ejemplos de Generalized Graph Query. Con el fin de simplificar la representaci´on de consultas y subgrafos, una de las propiedades en µ, a la que denominaremos τy que representa una clasificaci´on de tipos sobre nodos y aristas, ser´a expresada directamente sobre la aristas y, en el caso de los nodos, a trav´es de colores. Adem´as, la propiedad name de los nodos ser´a representada directamente sobre los mismos, y las aristas no dirigidas ser´an representadas como aristas bidireccionales. La representaci´on gr´afica de los GGQ de ejemplo se muestra en las figuras 3 a 8. Cuando analicemos la interpretaci´on de estas consultas tambi´en indicaremos algunos subgrafos de Gque los verifican. Cada elemento en estos GGQ tiene asociada la representaci´on de su propiedad αdirectamente por medio de un s´ımbolo +/−, y de su propiedad θdirectamente en el elemento (si el predicado asociado a un elemento del GGQ es una tautolog´ıa, dicho predicado no ser´a representado). En expresiones del tipo τ(ρ) = Xen el predicado de una arista, Xse interpreta como una expresi´on regular que debe verificarse por la secuencia de propiedades τde sopE(ρ). El GGQ P1(Figura 3) se puede interpretar en lenguaje natural a trav´es de la siguiente sentencia: Personajes y relaci´on alumno-maestro en la que ambos son devotos de los Jedi y el maestro tiene m´as de 500 a˜nos. En este caso se imponen restricciones estructurales a trav´es de la presencia de aristas y a trav´es de predicados que hacen uso de las propiedades τ,name, y age. Este GGQ se verificar´a en subgrafos en los que puedan ser proyectados dos nodos y una arista que los une (los tres elementos marcados como elementos positivos en el GGQ) que cumplan con las restricciones impuestas. En el caso de que existiera un personaje que se haya ense˜nado a s´ı mismo (lo que vendr´ıa dado por un lazo de tipo TEACHES) que tenga m´as de 500 a˜nos y sea devoto de los Jedi, un subgrafo que contenga este nodo tambi´en verificar´ıa este patr´on. El subgrafo marcado 13 Con el fin de obtener m´etodos controlados de generaci´on de consultas, en lo que sigue daremos un m´etodo constructivo para ir refinando un GGQ por pasos unitarios. Para ello, comenzaremos viendo c´omo se comportan los GGQ cuando se clonan nodos. Un clon consiste en hacer copias de nodos existentes, clonando todas las aristas incidentes en ellos (y entre ellos, en caso de que clonemos varios nodos que est´an conectados en el GGQ original). Por supuesto, la operaci´on de clonaci´on se puede hacer sobre grafos con propiedades cualesquiera, y as´ı la presentamos. Definici´on 12. Dado G= (V, E, µ)un grafo con propiedades, y W⊆V, definimos el clon de Gpor duplicaci´on de W, y lo notaremos por ClW G, como el grafo con propiedades siguiente: ClW G= (V∪W0, E ∪E0, µ ∪ {(n0, µ(n))}n∈W∪ {(e0, µ(e))}e0∈E0) donde: para cada n∈W,n0es un nodo nuevo, W0={n0:n∈W}, y E0es un conjunto de aristas nuevas que se consiguen a partir de las aristas incidentes en nodos de Wdonde se sustituyen de todas las formas posibles los nodos de Wpor copias de W0(de forma que aparecen aristas clonadas que conectan nodos originales con nodos copia, y tambi´en aristas clonadas que conectan nodos copia). Figura 12: Clon de un grafo. La Figura 12 muestra un ejemplo de un grafo clonado por dupliaci´on de dos de sus nodos. En el grafo original, a la izquierda, se resaltan los dos nodos a ser clonados. El resultado de la clonaci´on se presenta en el grafo de la derecha. El siguiente resultado nos indica que la clonaci´on de nodos positivos no altera la interpretaci´on de las consultas. Teorema 3. Si Q∈GGQ yW⊆V+ Q, entonces ClW Q≡Q. 20 Demostraci´on. Para facilitar la notaci´on, sea Q1=ClW Q. Entonces, siguiendo un razonamiento similar al de la demostraci´on anterior: Q1=^ n∈VQ1 Q1α(n) n =^ n∈VQ Q1α(n) n∧^ n∈W Q1α(n0) n0 =^ n∈VQrγQ(W) Q1α(n) n∧^ n∈γQ(W) Q1α(n) n∧^ n∈W Q1α(n0) n0 =^ n∈VQrγQ(W) Qα(n) n∧^ n∈γQ(W) Qα(n) n∧^ n∈W Qα(n) n =Q Siguiendo con la idea de obtener herramientas que nos permitan construir GGQ de manera autom´atica, el concepto de refinamiento que introducimos a continuaci´on completa las operaciones que podemos hacer para refinar un GGQ. En cierta forma, un conjunto de refinamiento forma una partici´on por refinamientos de un GGQ dado. Definici´on 13. Dado Q∈GGQ. Diremos que R⊆GGQ es un conjunto de refinamiento de Qen Gsi verifica: 1. ∀Q0∈R(Q0GQ) 2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0)) Estamos ya en condiciones de dar algunos conjuntos de refinamiento que nos permitir´an automatizar los procesos de creaci´on y modificaci´on de Generalized Graph Queries. Comenzaremos por la operaci´on m´as sencilla, que consiste en ver de qu´e formas se pueden a˜nadir nuevos nodos a un GGQ existente: Teorema 4 (A˜nadir nodo nuevo a Q).Dado Q∈GGQ ym /∈VQ, entonces el conjunto que notaremos como Q+{m}, formado por: Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T)) Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T)) es un conjunto de refinamiento de Qen G(Fig. 13). Demostraci´on. Hemos de comprobar que se verifican las dos condiciones necesarias para que sea un conjunto de refinamiento: 1. Es evidente que Q⊆−Q1yQ⊆−Q2, por lo que Q1QyQ2Q. 2. Sea S⊆Gtal que SQ. Tenemos que: Q1=Q∧Qm Q2=Q∧ ¬Qm donde Qm=∃v∈V(T). Si G6=∅, entonces SQ1yS2Q2. Si G=∅, entonces S2Q1ySQ2. 21 Como norma general, G6=∅, por lo que esta operaci´on realmente no refina, en el sentido de que Q1≡QyQ2≡ ¬T. Sin embargo, a pesar de que obtenemos un GGQ equivalente, esta operaci´on es muy ´util para a˜nadir nuevos nodos a un GGQ a los que posteriormente se le podr´an ir a˜nadiendo nuevas restricciones. Figura 13: Refinamiento a˜nadir nodo. Teniendo en cuenta los resultados anteriores que daban relaciones entre las propiedades estructurales del GGQ y su interpretaci´on sem´antica como consulta, pasamos a dar un segundo conjunto de refinamiento que nos indica c´omo interviene la creaci´on de aristas entre nodos existentes. Para mantener que todos refinen al GGQ original, hemos de restringir la adici´on de aristas a los nodos positivos. Teorema 5 (A˜nadir arista nueva entre nodos positivos de Q).Dado Q∈GGQ yn, m ∈V+ Q, entonces el conjunto que denotaremos como Q+{n+e∗ −→ m+} (∗ ∈ {+,−}), formado por (donde Q0=Cl{n,m} Q): Q1= (VQ0, EQ0∪ {n+e∗ −→ m+}, θQ0∪(e, T)) Q2= (VQ0, EQ0∪ {n+e∗ −→ m−}, θQ0∪(e, T)) Q3= (VQ0, EQ0∪ {n−e∗ −→ m+}, θQ0∪(e, T)) Q4= (VQ0, EQ0∪ {n−e∗ −→ m−}, θQ0∪(e, T)) es un conjunto de refinamiento de Qen G(Fig. 14). Demostraci´on. 1. Como Q0es un clon de Q, y {n, m} ⊆ V+ Q, tenemos que Q≡Q0. Adem´as, por construcci´on, Q0⊆−Q1, Q2, Q3, Q4, por lo que Q1, Q2, Q3, Q4Q0≡ Q. 2. Consideremos los predicados: Pn=∃v∈V ^ a∈γ(n) Qα(a) a∧Qα(e) eo  Pm=∃v∈V ^ a∈γ(m) Qα(a) a∧Qα(e) ei   22 Si SQnySQm, entonces tenemos 4 opciones mutuamente excluyentes, seg´un se verifique SPny/o SPm, que son: SPn∧SPm⇒SQ1 SPn∧S2Pm⇒SQ2 S2Pn∧SPm⇒SQ3 S2Pn∧S2Pm⇒SQ4 Si n=m(la arista a˜nadida es un lazo), entonces el conjunto de refinamiento anterior queda reducido a dos GGQ, los equivalentes a Q1yQ4. Figura 14: Refinamiento a˜nadir arista. La siguiente modificaci´on necesaria es la de a˜nadir un predicado adicional a una arista existente. Para mantener las condiciones estructurales necesarias, restringimos esta operaci´on a las aristas positivas que conectan nodos positivos. Teorema 6 (A˜nadir predicado a arista positiva entre nodos positivos de Q). Dado Q∈GGQ n, m ∈V+ Q, con n+e+ −→ m+, y ϕ∈FORM, el conjunto que notaremos como Q+{n+e∧ϕ −→ m+}, formado por (donde Q0=Cl{n,m} Q): Q1=(VQ0, EQ0∪ {n+e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q2=(VQ0, EQ0∪ {n+e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) Q3=(VQ0, EQ0∪ {n−e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q4=(VQ0, EQ0∪ {n−e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) es un conjunto de refinamiento de Qen G(Fig. 15). Demostraci´on. La demostraci´on es similar a la realizada en los casos anteriores. Por ´ultimo, la modificaci´on que nos queda es la de a˜nadir predicados a nodos existentes. De nuevo, hemos de restringir esta operaci´on a los casos que no plantean problemas, cuando los nodos afectados son positivos (el nodo al que se a˜nade el predicado, y los conectados a ´el). 23 Figura 15: Refinamiento a˜nadir predicado a arista. Teorema 7 (A˜nadir predicado a nodo positivo con entorno positivo en Q). Dado Q∈GGQ,n∈V+ Q, con NQ(n)⊆V+ Q, y ϕ∈FORM. Definimos el conjunto que denotaremos como Q+{n∧ϕ}formado por: {Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)} donde Q0=ClNQ(n) Q, y {+,−}NQ(n)es el conjunto todas las posibles asignaciones de signo a los elementos de NQ(n)(el entorno, en Q, del nodo n). Entonces Q+{n∧ϕ}es un conjunto de refinamiento de Qen G(Fig. 16). Demostraci´on. La demostraci´on es similar a la realizada en los casos anteriores. Solo hay que tener en cuenta que, cuando se modifica el nodo n, no solo queda modificado el Q-predicado asociado a ´el sino tambi´en el de todos sus nodos adyacentes. Por ello, el procedimiento que se ha seguido para cubrir todas las posibles opciones de asignaci´on de signos para los nodos involucrados es por medio del conjunto de funciones {+,−}NQ(n)(recordemos que en NQ(n) tambi´en se tiene en cuenta el centro, n). Se debe tener en cuenta que los refinamientos anteriores generan estructuras que pueden ser simplificadas. A continuaci´on vamos a definir la operaci´on principal que permite simplificar un GGQ determinado obteniendo otro equivalente con menor n´umero de elementos. Definici´on 14. Dado Q∈GGQ, diremos que Q0⊆Qes redundante en Qsi Q≡Q−Q0. Donde Q−Q0es el subgrafo de Qdado por: (VQrVQ0, EQr(EQ0∪ {γ(n) : n∈VQ0}), µQ) Veamos un primer resultado que, analizando nodos, nos permite obtener versiones simplificadas de un GGQ por medio de la eliminaci´on de nodos redundantes positivos: Teorema 8. Sea Q∈GGQ, y n∈V+ Qtal que existe m∈VQverificando: α(n) = α(m),θn≡θm. 24 Figura 16: Refinamiento a˜nadir predicado a nodo. Para cada e∈γ(n), existe e0∈γ(m), verificando α(e) = α(e0),θe=θe0y γ(e)r{n}=γ(e0)r{m}. Entonces, nes redundante en Q. Esencialmente, la condici´on que impone el resultado anterior es que msea un clon de npero, posiblemente, con m´as aristas conectadas. Teniendo en mente esta idea intuitiva, la prueba es directa a partir de las condiciones impuestas. Podemos obtener un resultado similar para aristas por medio del siguiente resultado: Teorema 9. Sea Q∈GGQ, y dos aristas, e, e0∈EQ, tales que n+e −→ m+y n+e0 −→ m+. Si θe→θe0entonces e0es redundante en Q. A partir de los resultados anteriores podemos dar versiones simplificadas de los conjuntos de refinamiento vistos, agrupando nodos positivos y aristas positivas en aquellos casos en los que, tras la clonaci´on inicial, el signo del elemento duplicado se ha mantenido con el original, as´ı como en los casos en los que el signo se ha mantenido y se ha a˜nadido un predicado adicional. En las Figuras 17 a 19 se muestran diagramas de los conjuntos de refinamiento Q+{n∧ϕ},Q+{n+e∧ϕ −→ m+}yQ+{n∧ϕ}, respectivamente, aplicando las simplificaciones presentadas. Por ejemplo, para construir el patr´on P5una posibilidad ser´ıa seguir la si25 Figura 17: Refinamiento a˜nadir arista (simplificado). Figura 18: Refinamiento a˜nadir predicado a arista (simplificado). guiente secuencia de refinamientos (Fig. 20): Q1=Q∅+{n1} Q2=Q1+{n1∧(v∈S∧τ(v)6=institution ∧τ(v)6=clan} Q3=Q2+{n2} Q4=Q3+{n2 e1 −→ n1} P5=Q4+{n2 e1∧(τ(ρ)=DEVOTED TO) −→ n1} A partir de la estructura de un GGQ no es f´acil obtener un GGQ complementario con ´el. Sin embargo, hay muchos procesos de an´alisis sobre grafos con propiedades en los que necesitamos trabajar con sucesiones de consultas que verifiquen algunas propiedades de contenci´on y complementariedad como predicados. Los refinamientos vistos en esta secci´on vienen a cubrir esta carencia y permiten, por ejemplo, construir un ´arbol de particiones encajadas con los nodos etiquetados de la siguiente forma (Fig. 21): El nodo ra´ız est´a etiquetado con Q0(un GGQ inicial cualquiera). Si un nodo del ´arbol est´a etiquetado con Q, y R= (Q1, . . . , Qn) es un conjunto de refinamiento de Q, entonces sus nodos hijo se etiquetan con los elementos de R. 26 Figura 19: Refinamiento a˜nadir predicado a nodo (simplificado). Figura 20: Sucesi´on de refinamientos para P5. Obs´ervese que la construcci´on del ´arbol anterior depende por completo de la elecci´on del conjunto de refinamiento que se elija en cada ramificaci´on. Los refinamientos que hemos presentado en los resultados anteriores son una opci´on, pero no es la ´unica posible. Por ejemplo, se pueden considerar refinamientos que, en vez de a˜nadir restricciones a elementos positivos, aligeren las condiciones impuestas por los elementos negativos, consiguiendo nuevos GGQ que refinan al anterior, y usando la adici´on de predicados por medio de la disyunci´on en vez de la conjunci´on. 7. Conclusiones y Trabajo Futuro En este trabajo hemos abordado el objetivo de obtener una herramienta para evaluar subgrafos inmersos en grafos con propiedades de manera que pueda ser utilizada en procedimientos de descubrimiento de informaci´on relacional. Para conseguir una herramienta de este tipo era deseable verificar varios requisitos: Por una parte, resultaba necesario disponer de una gram´atica que expresase las consultas a evaluar de una forma cercana a las propias estructuras 27 Figura 21: ´ Arbol de refinamientos. sobre las que iba a trabajar. Gracias a la capacidad expresiva de los grafos generalizados hemos presentado una herramienta de consulta que se puede expresar de forma natural por medio de un grafo con propiedades. Adem´as, era necesario dotar al sistema de consulta una base bien fundamentada de propiedades que nos asegurasen que, al ser usadas como predicados l´ogicos sobre grafos, se comportaban de manera coherente y robusta. Este resultado se ha obtenido presentando las relaciones existentes entre la estructura topol´ogica de la consulta y las relaciones de implicaci´on por medio del refinado. Adem´as, era necesario, ya que en tambi´en las usaremos para generar m´etodos autom´aticos de aprendizaje, que las consultas pudiesen ser modificadas de manera controlada por medio de operadores at´omicos que tradujesen el control topol´ogico en un control l´ogico. En este sentido, se ha introducido una primera familia de refinamientos que permiten construir a partir de una consulta inicial una colecci´on ordenada de consultas que recorren las diversas opciones de verificaci´on, formando un ret´ıculo completo de consultas. Debido a que cualquier estructura de datos relacional puede ser vista como un grafo, y cualquier consulta puede ser vista como la b´usqueda de un patr´on, la mayor´ıa de lenguajes de consulta en bases de datos pueden ser vistos como herramientas (quiz´as primitivas) de consulta de patrones en grafos con propiedades. En este trabajo tambi´en se han analizado algunas de las herramientas de consulta existentes, as´ı como la viabilidad para ser utilizadas en procedimientos autom´aticos. Una de las herramientas analizadas, los grafos de selecci´on, permite evaluar registros en bases de datos relacionales a trav´es de patrones ac´ıclicos que pueden ser refinados a partir de operaciones b´asicas, permitiendo obtener patrones complementarios en cada caso. Para ello, no requiere una proyecci´on exacta del patr´on que representa el grafo de selecci´on sobre el subgrafo a evaluar, sino el cumplimiento de una serie de predicados expresados a trav´es de dicho patr´on. Debemos recordar que si se exige una proyecci´on a la hora de realizar la verificaci´on de un patr´on se complica la tarea de evaluar la no existencia de determinados elementos. Concretamente, los grafos de selecci´on, eval´uan la existencia / no existencia de caminos incidentes al registro bajo evaluaci´on (solo son capaces de evaluar registros individuales), para ello se verifica si se cumple 28 una conjunci´on de predicados sobre caminos que parten del registro analizado, lo cual puede ser visto como la evaluaci´on de existencia de un ´arbol enraizado en el nodo que representa el registro bajo evaluaci´on. Los Generalized Graph Queries que hemos presentado aqu´ı extienden el concepto de grafo de selecci´on permitiendo la evaluaci´on de subgrafos generales, m´as all´a de un ´unico nodo, y el uso de predicados abiertos a trav´es de la definici´on de un lenguaje sobre los elementos del grafo y patrones c´ıclicos. Como se convierte en un requisito no usar una proyecci´on para la verificaci´on de un patr´on, estos objetivos los hemos conseguido extendiendo la forma de evaluaci´on, que puede ser vista como la evaluaci´on de un ´arbol enraizado por cada nodo presente en el patr´on. A pesar de que por cada nodo de un GGQ se eval´ua la existencia de un nodo que cumpla con las condiciones impuestas por su predicado y las aristas en las que participa, al permitir que las aristas se identifiquen con caminos en el grafo (Regular Pattern Matching) se produce la evaluaci´on de un ´arbol por cada nodo, y no de un simple ´arbol. Las intersecciones que se producen entre los diversos ´arboles y las restricciones impuestas en los nodos permiten la evaluaci´on de patrones c´ıclicos en los GGQ, algo que no se hab´ıa conseguido en otras propuestas anteriores. Como hemos comentado, al igual que los grafos de selecci´on, los GGQ se pueden modificar y construir a partir de refinamientos, pero a diferencia del caso simple de los grafos de selecci´on, normalmente los refinamientos no son binarios, ya que su aplicaci´on puede modificar m´as de un predicado en el patr´on, dando lugar a conjuntos de tama˜no 2k(siendo kel n´umero de predicados modificados). A trav´es de la definici´on de determinadas operaciones de simplificaci´on y equivalencia, los refinamientos mostrados pueden ser simplificados dando lugar a herramientas sencillas que permiten construir consultas complejas en grafos. En general, los refinamientos dan lugar a particiones encajadas de las estructuras que eval´uan, lo que los convierte en herramientas ideales para procedimientos de caja blanca. Tras haber llevado a cabo una primera implementaci´on como prueba de concepto (pero totalmente funcional), se ha demostrado experimentalmente que los GGQ son viables bajo condiciones suaves y que cumplen con los objetivos planteados de extensi´on de las herramientas existentes. Un uso expl´ıcito de estas capacidades ya ha sido llevado a cabo en procedimientos de descubrimiento de informaci´on, en concreto en el algoritmo GGQID3, que hace uso de los Generalized Graph Queries como herramientas de test para la construcci´on de un ´arbol de decisi´on siguiendo los fundamentos del famoso algoritmo ID3. La relaci´on que guardan los GGQ con GGQ-ID3 es equivalente a la relaci´on que guardan los grafos de selecci´on con el algoritmo MRDTL [13]. En los resultados de los experimentos llevados a cabo, se muestra que GGQ-ID3 es capaz de extraer patrones interesantes que pueden ser utilizados en tareas de aprendizaje complejas. Por otro lado, se pueden crear familias de refinamientos m´as complejos (por ejemplo, combinar el refinamiento a˜nadir arista con a˜nadir propiedad a una arista en un solo paso) para de esta manera reducir el n´umero de pasos para obtener GGQ complejos y ampliar la potencia con respecto a los pasos at´omicos que son menos informativos. Si se lleva a cabo esta opci´on de manera adecuada (unificando los refinamientos en funci´on de la frecuencia de aparici´on de estructuras en un grafo, por ejemplo) se puede conseguir que los algoritmos de descubrimiento que hacen uso de GGQ se acerquen de manera m´as r´apida a una buena soluci´on. En este caso se consigue una mejora en la eficiencia sacrificando 29