Graph databases underlie several modern applications such as social networks and the Semantic Web. In those scenarios, integrating and exchanging data is very common, which leads to proliferation of incomplete graph data. However, the well developed models of incompleteness of data do not apply to graph data. This is mainly due to the fact that standard graph query languages concentrate on graph topology; this requires functionalities beyond the abilities of standard relational systems. Besides, many graph languages ignore the actual data stored. However, recently languages combining data and topology aspects of querying have been proposed for graph databases. An example is a query Find pairs of people in a social network connected by professional links restricted to people of the same age). Formalisms developed to handle such queries include regular expressions with memory (REM), regular expressions with equalities (REE) [5], their extensions [1], as well as variants of XPath [4]. Handling incompleteness by languages dealing with pure graph topology has been studied in [2]. In this short note, we present preliminary results on dealing with incompleteness at the levels of both data and topology, using some of the recently proposed query languages. Let be a nite alphabet , let N be a countable set of node ids and let D be an in nite alphabet of data values. A data graph G (over , N and D) is a tuple (V; E; ), where V N is a nite set of nodes, E V V is a set of -labeled edges, and : V ! D assigns a data item to each node. A path in G is a sequence v0a0v1a1v2 vk 1ak 1vk such that (vi 1; ai 1; vi) 2 E, for each i k. The data path associated with is the word (v0)a0 (v1)a1 ak 1 (vk). The regular expressions with equality (REE) [5] are de ned by the grammar
e ::=
j a j e:e j e [ e j e+ j j e= j e6=;
. Given a REE e, L(e) is de ned by induction by the
where a ranges over
following rules
and the standard rules for L(e:e0), L(e [ e0) and L(e+). REE expressions without
6= are called positive. The evaluation e(G) of an REE e on a data graph G gives
pairs of nodes (u; v) such that there is a data path between them that belongs
to L(e). The combined complexity of REEs is Ptime, while the data complexity
is in Nlogspace. REEs are a subclass of a more expressive class REM whose
data complexity remains the same but combined complexity is in PSpace [
Let Vdata be an in nite set of label variables, let Vnode be an in nite set of nodes variables and let Vlabel be an in nite set of data variables. A data graph pattern (over , N and D) is a data graph over the alphabets [ Vlabel , N [ Vnode and D [ Vdata . That is, a data graph pattern is a data graph with constant nodes and node variables, whose edges can be labeled with variables and elements of , and in which the data values are taken from D [ Vdata .
Given a data graph pattern G = (V; E; ) and a data graph G0 = (V 0; E0; 0), a homomorphism is a triple (h1; h2; h3) of mappings h1 : V ! V 0, h2 that maps label variables in G to letters in , h3 that maps data variables in G to data values in D such that { h1(n) = n for all n 2 N , { for every edge (p; x; p0) 2 E, the edge (h1(p); h2(x); h1(p0)) belongs to E0, { for every pair (p; x) 2 , the pair (h1(p); h3(x)) belongs to 0. The data graph G0 is an homomorphic image of the data graph pattern G if V 0 = h1(V ).
Given a data graph pattern G and a REE e, the certain answers of e over G are de ned as 3
\fe(G0) : G0 is an homomorphic image of Gg: 3
Evaluation of REEs over incomplete graphs Theorem 1. The combined and data complexities of nding certain answers of REEs over incomplete graph databases are coNP-complete. This remains true for incomplete graphs without label variables.
Membership in coNP follows from tractability of REEs. Hardness is by reduction to Positive 1-in-3 SAT. The proof extends to show that data complexity of nding certain answers of REMs is coNP-complete, and their combined complexity is PSpace-complete.
Given a formula in CNF with 3 variables in each clause, we design an incomplete graph data such that an homomorphic images with data in f0; 1g corresponds to a valuation of the variables in . We de ne a REE e such that e is false in an homomorphic image G0 i the data of G0 belong to f0; 1g and the 3 The reader familiar with incompleteness may notice that we adopted the closed world semantics. Given the de nition of REE (and also of REM), it is easy to see that the open world semantics and the closed world semantics coincide. valuation associated with G0 makes exactly one variable true in each clause of .
For positive REE, we can obtain a tractable algorithm by using a so-called
naive evaluation, cf. [
Proposition 1. The combined complexity of nding the certain answers of positive REEs over incomplete graph databases is tractable.
We can also show, using naive evaluation, that data complexity of certain answers of positive REMs is tractable. The exact combined complexity though is open. 4
Many questions are left open. Instead of REM and REE, we could investigate
incompleteness for other languages designed to query graph databases.
Natural candidates would be versions of XPath for graph databases [