Functional querying in graph databases

Here we will use a (labelled) property graph model whose basic constructs include:Entities and relationships can have any number of properties, nodes and edges can be tagged with labels. More edges connecting two nodes are allowed. Both nodes and edges are defined by a unique identifier. Properties are expressed in the key:value style. In graph-theoretic notions we also talk about labelled and directed attributed multigraphs in this case. These graphs are used both for GDB and its database schema (if any). An example of a GDB is in Fig. 1.

In a little restricted version, also XML documents can be represented by labelled, finite trees. More generally, XML documents can have a more general graph structure, due to ID references, but we will not consider this case. Nodes of these data structures are objects, labels on edges are XML tags (element names or attribute names). We will not even consider XML attributes here. Leaves contain atomic values—texts. Figure 2 presents an example of XML document based on the GDB sample in Fig. 1.

XML data can be represented as trees in more ways. One possibility is used in Fig. 3 for XML document in Fig. 2. Comparing to property graphs, these XML trees use only nodes of two types and labelled edges.

XML data can contain more occurrences of one element. To include them into a database, we introduce a set E of abstract elements. An empty abstract element \(\upvarepsilon \) is also in E. Any function is undefined on \(\upvarepsilon \). The set E serves as a reservoir for construction of XML elements and to their unique identification. Abstract elements can be implemented as inner OIDs in an XML database. The content of an abstract element will be either a string from PCDATA, in the easiest example, or a sequence of abstract subelements, or empty. Neglecting ordering of subelements, the sequence can be replaced by a set. For example, \(<\mathtt{town\_name}>\hbox {Berlin}<\mathtt{/town\_name}>\) is an instance of the town_name element object. The town_name element object is a (partial) function from E to PCDATA. A more complex town element type can be conceived as a set of functions from E to the Cartesian product of E \(\times \) E (abstract town names and populations). The second component of a town couple can be \(\upvarepsilon \). Due to the tree representation, for example the town Berlin will represented twice in such XML tree. Similarly, if more teachers learn German, representation of German language would be repeated in the XML document. This observation reflects the fact that XML data is textual, even for numeric data. Moreover, no conceptual view is supposed for this data.

In [8] we considered only partially ordered XML documents. In paper [9], we proposed an ordered model of XML data, i.e., a modification of its typing apparatus, which preserves ordering of subelements.

In [12] we proposed a binary E-R model as a variant for graph conceptual modelling considering strong entity types, weak entity types, relationship types, attributes, identification keys, partial identification keys, ISA-hierarchies, and min-max ICs. The notation is based on the Oracle Designer CASE [3]. The graph conceptual schema in Fig. 4 uses for min-max ICs well-known notation with dotted lines and crow’s foots used for the start node and the end node of some edges. The perpendicular line denotes the identification and existence dependency of weak entity types. Subtyping (ISA-hierarchies) is simply expressed by arrow to the entity supertype. Relationship types are expressed by couples of mutually “inverse” labels, e.g., (Is_thought_by, Teaches).

Figures  4 and 5 give examples of graph conceptual schema and graph database schema (without attributes/properties), respectively. Graphical min-max ICs (see, Fig. 2) can be expressed equivalently by expressions (\(\hbox {E}_{1}\):(a, b), \(\hbox {E}_{2}\):(c, d)), where a, \(c \, \upepsilon \{0, 1\}, b\), \(d\, \upepsilon \{1, n\)}, and n means “any number greater than 1”. For example, (Teacher:(1, 1), Town:(0, n)) can be associated with the relationship type (Is_born_in, Is_birthplace_of). Expressions (\(\hbox {E}_{1}\):(a, n), \(\hbox {E}_{2}\):(c, n)) correspond to cardinalities m : n in an alternative notation.

A correct graph conceptual schema may be mapped into an equivalent (or nearly equivalent) graph database schema with the straightforward mapping algorithm [12] but with a weaker notion of a database schema, i.e., some inherent ICs from the conceptual level have to be neglected to satisfy usual notation of labelled property graphs. Consequently, we can propose several different graph database schemas from a graph conceptual schema. For example, the edges Teaches and Is_born_in provide only a partial information w.r.t. the associated source conceptual schema. The inverted arrow Is_taught_by could be used as well. Due to the loss of the inherent ICs occurring at the conceptual level, we should put some explicit ICs into the GDB schema, e.g., that “A teacher can teach more languages” and “A teacher is born in exactly one town”.

As usual, only single-valued attributes of form key:domain are considered here, where domains include elementary descriptive types like String, Number, Date, etc. Then, the identification key of Teacher could be #Person_ID. On the database schema level, the identification key of Street would be {Town_name, Street_name}. Details of mapping of graph conceptual schemas to graph database schemas can be found in [12].

Figure 6 presents the graph database schema associated to the GDB in Fig. 1. Obviously, the schema is again a labelled and directed attributed multigraph.

The values of some properties can be unknown or undefined in a GDB. This reminds NULL values in SQL databases. For example, Textbook:NULL could be considered. In GDB as well is in NoSQL databases generally, such properties are not explicitly represented. In Fig. 1, the Language node for English is the case.

The simplest way how to model XML data on the database schema level is given by the language DTD. A more rich collection of modelling tools is offered by XML Schema language⁷. The DTD subset considered in our examples uses only element declarations. Figure 7 contains a DTD describing the XML data in Fig. 2.

Due to the graph structure of data in GDB, associated explicit ICs can have also a graph form. Very simple IC is a functional dependency (FD) or conditional functional dependency (CFD) introduced in [12]. For example, “Each teacher is born in one town” and “Teachers born later than in 1994 teach at most one language” are examples of FD and CFD, respectively. A usable approach is also offered by above mentioned GRAD database model. It enables to express some semantic restrictions over the graph data with using graph patterns. A graph pattern P is a predicate on the graph topology (specifying conditions on the structural properties of the graph) and properties (specifying conditions on their values) of the graph elements.

At least inherent ICs coming from a graph conceptual schema should be considered as explicit ICs on the graph databases level, i.e., using a DDL for their formulation. In [13], we have focused on graph database Neo4j and its possibilities to express a database schema and/or ICs. We have extended these possibilities through new constructs in Neo4j DDL including their prototype implementation and experiments.

On the other hand, NoSQL databases often does not require the notion of a graph database schema at all. Strict application of schemas is sometimes considered disadvantageous by those who develop applications for dynamic domains, e.g., domains working with user-generated content, where the data structures are changing very often [1]. Consequently, many GDBMSs are schema-less, including Neo4j. OrientDB⁸ even distinguishes three roles of graph database schema: schema-full, schema-less, and schema-hybrid. Even schema-less, some GDBMSs support to specify some types of ICs. Neo4j uses for this purpose the language Cypher.

In this section, we focus on basics of graph querying (for more details see [11]). Its simplest type uses the index-free adjacency. In practice, the basic queries like k-hop queries are the most frequent. Looking for a node, looking for its neighbours (1-hop query), scan edges in several hops, retrieval of property values, etc., belong into the category.

More complex queries are subgraph and supergraph queries. They belong to traditional queries based on exact matching. Other typical queries include breadth-first/depth-first search, path and shortest path finding, least-cost path finding, finding cliques or dense subgraphs, finding strong connected components, etc.

Very useful are regular path queries (RPQ). RPQs have the form:where R is a regular expression over the vocabulary S of edge labels. Construction of regular expressions is as follows:where s is a label from S. RPQs provide couples of nodes connected by a path conforming to R. With the closure of RPQs under conjunction and existential quantification we obtain conjunctive RPQs.

For example, the Cypher working with Neo4j databases lacks some fundamental graph querying functionalities, namely, RPQs and graph construction. In [2] an interesting newer approach is offered by the language G-Path. G-Path is an RPQ language working on graphs, which supports mostly all useful regular expression operators. PGQL [19] is based on the paradigm of graph pattern matching, closely follows syntactic structures of SQL, and provides RPQs with conditions on labels and properties.

A hierarchy of types is constructed as follows. We assume the existence of some (elementary) types \(\mathtt{S}_{1}\),...,\(\mathtt{S}_{k}\) (\(k\ge 1\)). They constitute a base B. More complex types are constructed in the following way.

If \(\mathtt{S, R}_{1},\ldots , \mathtt{R}_{\mathrm{n}}\) (\(n\ge 1\)) are types, thenThe set of types T over B is the least set containing types from B and those given by (i)-(ii). When \(\mathtt{S}_{\mathrm{i}}\) in B are interpreted as non-empty sets, then \((\mathtt{S:R}_{1},\ldots ,\mathtt{R}_{\mathrm{n}})\) denotes the set of all (total or partial) functions from \(\mathtt{R}_{1}\times \cdots \times \mathtt{R}_{\mathrm{n}}\) into S, \(\mathtt{(R}_{1},\ldots ,\mathtt{R}_{\mathrm{n}})\) denotes the Cartesian product \(\mathtt{R}_{1}\times \cdots \times \mathtt{R}_{\mathrm{n}}\).

In the conceptual modelling, each base B consists of descriptive and entity types. Descriptive types (String, Number, etc.) serve for domains of properties. Their elements are constants like ‘Prague‘, ‘John‘, ‘201400‘, etc. The elementary type Bool = {TRUE, FALSE} is also in B. The type Bool allows to type some objects as sets and relations. They are modelled as unary and n-ary characteristic functions, respectively. The concept of the set then becomes redundant.

The fact that X is an object of type R \(\in \) T can be written as \(X\mathtt{R}\), or “X is the R-object”. For each typed object o the function type returns type(\(o) \quad \in \) T of o. Logical connectives, quantifiers and predicates are also typed functions: e.g., and/(Bool:Bool,Bool), R-identity \(=_{\mathrm{R}}\) is (Bool:R,R)-object, universal R-quantifier \(\Pi _{\mathrm{R}}\), and existential R-quantifiers \(\Sigma _{\mathrm{R}}\) are (Bool:(Bool:R))-objects. R-singularizer \(I_{\mathrm{R}}\)/(R:(Bool:R)) denotes the function whose value is the only member of an R-singleton and in all other cases the application of \(I_{\mathrm{R}}\) is undefined. Arithmetic operations +, -, *, / are examples of (Number:Number,Number)-objects. We can also type functions of functions etc.

Object structures usable in building a database can be described by some expressions of a natural language. For example, “the language thought by a teacher at a school” (abbr. LTS) is a (Language:Teacher, School)-object, i.e., a (partial) function f :Teacher \(\times \) School \(\rightarrow \) Language, where Teacher, School, and Language are appropriate elementary types. Such functions are called attributes in [7].

More formally, attributes are functions of type ((S:T):W), where W is the logical space (possible worlds), T contains time moments, and S \(\upepsilon \) T. \(M_{\mathrm{w}}\) denotes the application of the attribute M to \(w.\mathtt{W}\), \(M_{\mathrm{wt}}\) denotes the application of \(M_{\mathrm{w}}\) to the time moment t. In our approach to conceptual modelling, we can omit parameters w and t in type(M). In the case of LTS attribute, we suppose only possible worlds, where teachers teach at most on language in each school. However, this may not be true for other possible worlds. For GDBs we can elementary entity types conceive as sets of node IDs. For a better readability, John, Prague, Frank can be simply such IDs.

Attributes can be constructed according to their type in a more complicated way. For example, “the classes in a school” could be considered as an attribute CS of type ((Bool:(Bool:Student)):School), i.e., the classes contain sets of students and the CS returns a set of classes (of students) for a given school. Obviously, Student is an elementary type.

We can also consider other functions that need no possible world. For example, aggregate functions like \(\hbox {COUNT}_{\mathrm{S}}\)/((Number:(Bool:S)), SUM/(Number:(Bool:Number)) ⁹ and arithmetic operations provide such functions. These functions have the same behaviour in all possible worlds and time moments. Consequently, we can distinguish between two categories of functions: empirical (e.g. attributes) and analytical. The former are conceived as partial functions from the logical space. Range of these functions are again functions. Analytical functions are of type S, where S does not depend on W and T.

The notion of attribute applied in GDBs could be restricted on attributes of types(R:S), ((Bool:R):S), or (Bool:R,S), where R and S are entity types. This strategy simply covers binary functional types, binary multivalued functional types, and binary relationships described as binary characteristic functions. The last option corresponds to m : n relationship types. For modelling directed graphs the first two types are sufficient, because m : n relationships types can be expressed by two ,,inverse“ binary multivalued functional types. Here we will consider always one of them (see, e.g., Teaches below). Thus, a graph database schema can reflect a reality only partially, similarly to non-functional graph data modelling.

Now we add properties. Properties describing entity types can be of types (\(\mathtt{S}_{1}\),...,\(\mathtt{S}_{\mathrm{m}}\):R), where \(\hbox {S}_{\mathrm{i} }\) are descriptive elementary types and R is an entity type. So we deal with functional properties. Similarly, we can express properties of edges. They are of types (\(\mathtt{S}_{1}\),...,\(\mathtt{S}_{\mathrm{m}},\mathtt{R}_{1}:\mathtt{R}_{2})\) and \(((\mathtt{Bool:S}_{1}\),...,\(\mathtt{S}_{\mathrm{m}},\mathtt{R}_{1}):\mathtt{R}_{2})\) for binary functional and binary multivalued functional types, respectively.

Then a functional database schema describing GDB in Fig. 1 can look as:

La/((Name, Textbook):Language)

Te/((T_ID, T_Name, Birth_year):Teacher)

Tw/((Town_name, Population):Town)

Teaches/((Bool:Day, Hour, Room,

Is_Born_in/((Date, Town):Teacher)

Lives_in/ ((From,Town):Teacher)

where La, Te, Tw, Teaches, Is_Born_in and Lives_in are typed variables. The use of variables correspond to a “database view” of the modelled world. Since we do not consider temporal functional databases here, it is not necessary to use time explicitly.

Thus, a functional graph database schema is a set of variables of types from T restricted to attribute types. A functional graph database is any evaluation of these variables. Thus, certain variables serve for referencing the associated database. For convenience, we denote the variables from the functional graph database schema by names remaining entity and relationship types in the associated traditional GDB schema or at least their abbreviations.

Instead of the position notation we can use more readable dot notation for components. Consider the Prague object (entity, node). Then instead of Tw (Prague) [2], where Prague/Town, we can write Tw (Prague).Population. The real effect of this convention is that we approach Population property independently on its position in the tuple described by the associated functional database schema. In the case that the population is not present between properties of the town Prague, the function will be undefined.

Terms are interpreted in a standard way by means of an interpretation assigning to each function symbol from Func an object of the same type, and by a semantic mapping [ ] from LT into all functions given by T. Func influences the expressive power of LT. It can contain usual arithmetic and aggregation functions, etc. Of a special importance is R-identity \(=_\mathtt{{(Bool:(Bool:S),(Bool:S))}}\) usable for a comparison of two sets of S-objects. We will denote the (Bool:(Bool:S),(Bool:S))type as 2sets for better readability. Consider Teacher-objects John and Frank. Then withwe can test whether John and Frank teach the same set of languages. Similarly to domain relational calculus, we can simplify this expression by omitting some existential quantifiers and associated variables. Then the resulted expression can look asA further simplification could be made by omitting lambda abstraction supposing that information about objects considered is in the Bool(Language)-identity. Then we can writeIn other words, an application is evaluated as the application of an associated function to given arguments, a lambda abstraction “constructs” a new function. In the conventional approach a valuation \(\updelta \) is used. Supposing this mapping we can assign objects to every variable occurring in a term.

For example, CS(Oxford_House)(’AM_training’) is TRUE, if there is the class AM_training in the Oxford_house school (’AM_training’ is a constant of type (Bool:Student)). It is true while ’AM_training’ contains all students of the class AM_training.

In accordance with the semantics of the quantifiers and the singularizer, we can write simply \(\forall x(M)\) instead of \(\Pi (\lambda \quad x(M))\). Similarly, \(\exists x(M)\) replaces \(\Sigma (\lambda \quad x(M))\). Finally, we write \(I(\lambda \quad x(M))\) shortly as onlyone x(M) and read “the only x such as M”. Certainly, M /Bool.

From the database point of view, we have at disposal a powerful declarative language for formulating schema transformation, ICs, etc., even querying GDBs, as we shall see in Sect. 5.1. Section  5.2 shows that a similar technique can be used in context of XML trees.

The LT language can be used as a theoretical tool for building a functional database language. A query in such language is expressed by a term of LT, e.g.,with d, h, r, and l of types Teacher, Day, Hour, Room, Language, respectively.

Using the syntactic abbreviation similar to that one used in Section 4.3, the resulted lambda expressiondenotes the query “Give a set of couples associating with each teacher the number of languages teaching by him/her”. Obviously, the query could be also reformulated as \(\lambda \quad t\) (\(\lambda \quad n\) (...)), or more conventionally \(\lambda \quad t\) onlyone n (...).

To consider only teachers born in Prague the lambda expression might look like

In querying GDBs, RPQs are of user importance. We will consider expressionswhere Reg is an expression simulating concatenation and closure. There are two styles how to construct Reg. First, consider the attributeabbreviated as FOF. FOF(\(p_{\mathrm{i}})(p_{\mathrm{j}})\) = TRUE expresses the fact that there is an edge between \(p_{\mathrm{i}}\) and \(p_{\mathrm{j}}\) in the associated GDB. Thenwill denote the expression FOF(\(p_{1})(p_{2})\) and ... and FOF(\(p_{k-1}\),)(\(p_{k})\), for a k (\(k>\)1), andprovides a set of couples (\(p_{1}\), \(p_{\mathrm{k}})\), where there is a directed path from \(p_{1}\) to \(p_{\mathrm{k}}\) along edges of FOF.

Now we will consider a single-valued function, e.g.,abbreviated as MO. MO \(^{*}(p)\), where p /Person, will denote the expression MO(...(MO(p)...)) with l applications of MO, for a \(l\ge \)1, andprovides a set of couples (\(p_{1}\), \(p_{k})\), where there is a directed path from \(p_{1}\) to \(p_{k}\) along edges MO.

A composition of different functions representing relationships and properties looks, e.g., as follows. The following term expresses a YES/NO query “Is John born in Berlin?”One of the most fundamental problems in graph processing is pattern matching. Specifically, a pattern match query searches over a GDB to look for the existence of a pattern graph in a GDB. For example, triangle counting is used heavily in social network analysis. It is easy to formulate terms providing sets of triples (\(p_{1}\), \(p_{2}\),\( p_{3})\) and there is a path \(p_{1} \quad \rightarrow \quad p_{2} \quad \rightarrow \quad p_{3 }\rightarrow \quad p_{1}\) in GDB. Clearly, we have to suppose oriented labelled edges, i.e., attribute names, e.g., FOF. Finding only structural triangles, regardless of edge names, would require to expand the typing of variables and to move to the second-order typed lambda calculus.

First, we extend the type system defined in Sect. 4.1 by the union type (\(\mathtt{T}_{1}+\mathtt{T}_{2})\) denoting union of sets \(\mathtt{T}_{1}\) and \(\mathtt{T}_{2}\). Now we introduce the type system T \(_{\mathrm{reg}}\). Let B = {PCDATA, BOOL, NAME}. The type system T \(_{\mathrm{reg}}\) over B is recursively defined as follows.

The type system T \(_{\mathrm{reg}}\) describes regular expressions over character data, similarly as it is allowed in DTDs. Suppose that PCDATA is interpreted as a set of character data (strings). Then tag:PCDATA denotes the set of character data labelled by tag. The type tag: denotes the empty labelled character object. (\(\mathtt{T}_{1} \cup \mathtt{T}_{2})\) denotes the set of objects of type \(\mathtt{T}_{1}\cup \mathtt{T}_{2}\). T* is an abbreviation for (BOOL:T). In this case, (BOOL:T)-objects include \(\varnothing \) which simulates the empty set. Similarly, T+ denotes the set of (BOOL:T)-objects except \(\varnothing \), and T? the set of objects of type T \(\cup \) NIL.

Now we will define (XML) element types, following the established type system T \(_{\mathrm{reg}}\) over B. In order to distinguish tags used in T \(_{\mathrm{reg}}\) from element tags we will suppose for each tag used in the elementary types tag:T or tag: the existence of the TAG name denoting an associate element type¹⁰. The same holds for any tag \(\in \) NAME. Thus, NAME contains both tags and TAGs.

Let T \(_{\mathrm{reg}}\) over B be the type system and E be a set of abstract elements. Then the type system T \(_{\mathbf{E}}\) induced by T \(_{reg}\) (or T \(_{\mathbf{E}}\) ifT \(_{\mathrm{reg}}\) is understood) containing the regular element expressions is given by the following grammar:

Elementary element types and regular element expressions TAG:(\(E_{1},\ldots ,E_{\mathrm{n}})\) are called element types.

The functional semantics of the element types associate with TAG:PCDATA the set of all functions from E to tag:PCDATA. For a non-elementary element type T, the semantics of TAG:T are also functional, but the functions are more complex.

Then an XML-database schema, S \(_{\mathrm{XML}},\) is a set of variables of types from T \(_{\mathbf{E}}\). Given an XML-database schema S \(_{\mathrm{XML}}\), an XML-database is any valuation of these variables. Thus, certain variables serve for referencing the associated database. For convenience, we denote the variables from S \(_{\mathrm{XML}}\) by the same names as TAGs from T \(_{\mathbf{E}}\), e.g. BOOK, AUTHOR, etc. For example, a number of types associated with DTD in Fig. 7 can look as follows:To manipulate XML data from XML-database based on T \(_{\mathbf{E}}\), it is necessary only to extend the original LT language by tagged terms K:M, where K/NAME. If M /T, then K:M/(T:E). The resulted language version called XML-\(\lambda \) in [8] enables to simulate much of the XPath¹¹ language as well as the 1st order logic, aggregation functions, arithmetic, and user defined functions. Obviously, a more user-friendly notation can be used. For example,can be rewritten asWhen we use a path in more logical conditions, it is possible to write the common prefix only once in XML-\(\lambda \) and to put conditions in parentheses. For example,denotes the query “Give a set of teachers names who live in the same town where they were born”.