SPARQL queries on RDF with fuzzy constraints and preferences

2.1 RDF and SPARQL

RDF is a directed, labeled graph data format for representing Web resources [15]. The RDF abstract syntax is a set of triples, called the RDF graph. A RDF triple is defined as (s ;  p ;  o) ∈ (I ∪ B) × I × (I ∪ B ∪ L). Here I, B and L are infinite sets of IRIs, blank nodes and RDF literals, respectively. In a triple, s is called the subject, p the predicate (or property), and o the object.

For RDF data sets, SPARQL [19] provides tools to obtain information from URIs, blank nodes, text of no format and RDF sub-graph, and construct a new RDF graph according to the information from the query graph. A SPARQL query can be defined as a quadruple Q = (V,  P,  DS,  SM), where V declares a result form, P represents a graph pattern, DS is a data set and SM a set of solution modifiers [6].

A SPARQL query has the basic format of SELECT-FROM-WHERE. Among these components, the SELECT component is applied to represent the set of variables being shown in the result, the FROM component is employed to represent the dataset constituted by a set of IRIs of RDF documents, and the WHERE component is used to represent the graph pattern constituted by a set of RDF triples. In addition to these major components above, there is an additional solution modifier SPARQL FILTERs. SPARQL FILTERs restrict solutions to those for which the FILTER expression evaluates to TRUE. One can refer to [19] for the syntax of SPARQL.

2.2 Fuzzy sets and orderly linguistic values

In the classical sets theory, two-valued logic {0, 1} is applied. As a result, an element either belongs to a set or does not belong to a set for certain. But in the fuzzy sets theory [25, 29], an element belongs to a set with a membership degree of [0, 1] instead of {0, 1} was introduced, which is described by a membership function.

Definition 1. Let U be a universe of discourse and A be a fuzzy set in U. A membership function μ _A  : U → [0, 1] is defined for A, in which μ _A  (x) for each x ∈ U denotes the membership degree of x in the fuzzy set A.

Let A be a fuzzy set in the universe of discourse U with the membership function μ _A  :  U → [0, 1]. Then we have the following notions.

Support: the support of A is a set of the elements that have non-zero degrees of membership in A, denoted by supp (A) = {x|x ∈ U and μ _A  (x) >0}.

With α-Cut, a fuzzy set (say F) is converted to a classical one (say F _α or F _α +).

Let A be a fuzzy set in the universe of discourse U with the membership function μ _A  : U → [0, 1]. We say A is convex if and only if for all μ₁,  μ₂ in U, μ _A  (λu₁ + (1 - λ)  u₂) ⩾ min   (μ _A  (u₁) ,  μ _A  (u₂)), where λ ∈ [0, 1]. In addition, we say A is a normal fuzzy set if ∃ u ∈ U, μ _A  (u) =1. A fuzzy number is a convex and a normal fuzzy set. Let A and B be two fuzzy numbers in U and let A _α and B _α be the α-Cuts of A and B, respectively. Then we have (A ∪ B)  _α  = A _α  ∪ B _α and (A ∩ B)  _α  = A _α  ∩ B _α .

A fuzzy set is applied to represent a fuzzy notation, which generally corresponds to a linguistic value [26–28]. With some linguistic values, we may get orderly linguistic values.

Definition 2. (orderly linguistic values). Let S be a finite and totally ordered label (term) set and formally defined as S = {s _i |i = 0, …,  τ}, where τ is a positive integer which means the cardinality of S, s _i is a linguistic value and s _i  <  s _j  if 0 ⩽ i < j ⩽ τ.

In the orderly linguistic values, the middle linguistic value (i.e., s_τ/2) means “approximately 0.5”, and it is assumed that the other values are placed symmetrically around it. In particular, s₀ and s _τ denote the lower and upper limits of linguistic values. Actually orderly linguistic values generally represent adverbs in the natural language.

Let s _i and s _j be two linguistic values. Then we have the following operations on linguistic values.

neg  (s _i ) = s _j ,  j = τ - i

Here neg  () represents a negation operator, and max   () and min   () represents the maximazation operator and the minimazation operator, respectively.

The cardinality of S (i.e., τ) are odd such as 7 and 9. The limit of cardinality is 11. Generally it must be small enough so as not to impose useless precision on decision making, but it must also be rich enough in order to allow a discrimination of the performances of each object in a limited number of grades. According to Miller decision theory, generally 5 up to 7 linguistic values on an ordered scale are used [16]. In this paper, we adopt 7 linguistic values to make up the orderly linguistic values. Then we have S = {s₀ = none,  s₁ = very low,  s₂ = low,  s₃ = medium,  s₄ = high,  s₅ = very high,  s₆ = perfect}.

Viewed from the processing of orderly linguistic values, it is required that each linguistic value (say s _i ) is associated with a fuzzy set defined with a membership function. In principle, membership functions can be of different shape, but in practice, trapezoidal and triangular membership functions are most frequently used. Trapezoid membership function is generally described with (a _i ,  b _i ,  c _i ,  d _i ), where a _i and d _i represent minimal and maximal value in membership interval of an element of an order i, b _i and c _i form an interval to show the membership degree equals to 1.

The notations and semantics of the orderly linguistic values S = {s₀ = none,  s₁ = very low,  s₂ = low,  s₃ = medium,  s₄ = high,  s₅ = very high,  s₆ = perfect} are presented in Table 1. The trapezoid membership functions of the orderly linguistic values in S are given in Fig. 1.

2.3 Related work

In recent years with expansion of data Web applications, problems of RDF queries come to forefront. In [6], SPARQL is extended with an easy-to-grasp yet powerful way for querying the RDF data sets. In the extended SPARQL, the occurrence of fuzzy terms and fuzzy operators is allowed. Also, in order to express users’ weight preferences on fuzzy constraints, user-defined weights in the form of ∑ω _i  = 1 are provided in [6]. Finally it is shown in [6] how to translate fuzzy terms and fuzzy operators into crisp ones and how to efficiently calculate the top-k answers of fuzzy queries with regard to membership degrees as well as user-defined weights. In [12], for fuzzy queries over RDF data, a proof-of-concept framework is presented for enabling relaxation of structured entity-lookup queries, evaluating different distance measures for performing relaxations. To query the fuzzy DL-Lite ontologies, in [18], an extended SPARQL is proposed, which allows threshold and user-defined weights in the query.

In addition to the efforts of fuzzy constraints mentioned above, there are some efforts in the expression constructed with users’ preferences in the context of the Semantic Web. In [22], a method to querying the Semantic Web with multi-dimensional preferences is proposed. In their method, the preferences are divided into two types, which are the Boolean preferences and the scoring preferences. By using the Preferring clause which defines some independent preferences separated by the AND construct, users can specify the preferences. In addition, the atomic preferences can be nested using the CASCADE construct. It should be noted that the ranking method in the Preferring modifier may meet the situation that the queries cannot be handled in [22]. Assume that, for example, we just need one more result in the current result set of a four-dimension preference. Also we assume that there is a best solution in each dimension, but there are not any domination relations between any two of them. For this case, it is difficult for the ranking to be finished (see [22] for more details about ranking). In [13], the preference problem of fuzzy and multiple conditions are considered in practical query, and the relevancy computational formula is provided, which can realize preference query through sequencing.

This paper differs from the efforts above in three aspects: first, the orderly linguistic values are applied instead of the crisp thresholds in [0, 1]; second, the fuzzy relations between two variables are also introduced into the fuzzy constrains in addition to fuzzy terms and fuzzy operators; finally, the dimensional preferences for users are explicitly introduced and applied in ranking the returned results.

3.1 Fuzzy terms and fuzzy operators

The fuzzy extension of SPARQL mainly takes place in the FILTER constraint component. In [6], the basic form of FILTER constraint allowing fuzzy terms is as follows.

FILTER (?X θ FT [WITH α])

Among them, FT denotes a fuzzy term (e.g., “tall” or “young”), which corresponds to a fuzzy set using a trapezoidal membership function, and θ is an operator of >,   < , = ,   ⩾ ,   ⩽ ,   ! = ,  between and not between . If the operator θ is between or notbetween, the syntax of FILTER constraint is a little different, i.e.,

FILTER (?X between/notbetween FT₁ and FT₂) [WITH α],

where FT₁ and FT₂ are two fuzzy numbers, respectively.

The optional parameter [WITH α] indicates the condition that must be satisfied as the minimum membership degree in [0, 1]. It is required in [6] that users need to choose an appropriate value of α to express their requirements. If not specified, 1 is used as default. However, it is not easy for users to understand the semantics of a crisp α and to make an appropriate choice. For this reason, we apply orderly linguistic values in FILTER constraint, which has the form as follows.

FILTER (?X θ FT [WITH s _i ]) or

FILTER (?X between/notbetween FT₁ and FT₂) [WITH s _i ]

The fuzzy terms applied in SPARQLf can be classified into three types, which are simple (atomic) fuzzy term, modified (composite) fuzzy term and compound fuzzy term. A simple fuzzy term such as “young” or “tall” is defined in terms of a fuzzy number with a membership function. A modified fuzzy term, e.g. “very young” or “more or less tall”, is described by a simple fuzzy term and a fuzzy modifier together. A compound fuzzy term is represented by simple fuzzy terms or modified fuzzy terms connected by or (union), and (intersection), or not (complement) connectors, such as “young or very young”.

Now we consider fuzzy operators within the FILTER constraint, which is formalized as follows.

FILTER (?X θ ˜ Y) [WITH s _i ]

Here θ ˜ denotes a fuzzy operator, and Y denotes a string, an integer or any other data types allowed in RDF. Then the fuzzy operator θ ˜ and the crisp value Y constitute a fuzzy number represented by θ ˜ Y. We, in this paper, mainly discuss three types of fuzzy relations, which are “close to (around)”, “at least”, and “at most”.

3.2 Fuzzy relation

It is worth noting that the fuzzy terms and fuzzy operators discussed above are applied in single variables of the fuzzy constraints. In “Age = old” and “Age is around 50”, for example, fuzzy term “old” and fuzzy operator “around 50” are related to a single variable “Age”. In practice, there exist many fuzzy semantics constraints within two variables. Let us look at an example. Suppose that we have two variables, say “supplier” and “customer”, and there is a fuzzy constraint relation between them, say “customer likes supplier”. In order to handle this kind of fuzzy constraints, we further introduce fuzzy relations into SPARQLf.

Definition 3. (fuzzy relation). Let U and V be two universes of discourse, and R be a fuzzy relation on U × V. A membership function θμ _R  : U × V → [0, 1] is defined for R, in which μ _R   (u,  v) for each u ∈ U and v ∈ V denotes the membership degree of (u,  v) in the fuzzy relation R.

Basically we can identify two major kinds of fuzzy relations, which are simple fuzzy relation and compound fuzzy relation. A simple fuzzy relation between elements from two universes of discourse and its membership function are generally defined directly by the domain experts. Compound fuzzy relations can be obtained with simple fuzzy relations.

Definition 4. (compound fuzzy relation). Let Q be a fuzzy relation on U × V and R be a fuzzy relation on V × W. Then a compound fuzzy relation on Q and R, noted as Q © R, is defined as Q © R (u,  w) = ∨ (Q  (u,  v) ∧ R (v,  w)) (u ∈ U ∧ v ∈ V ∧ w ∈ W).

Example 1. Let R be a fuzzy relation, which represents that variable x is much greater than variable y. Here x and y are two variables taking real values. The membership function of this simple fuzzy relation may be defined, for example, as follows.

R ( x , y ) = { 0 , x ⩽ y [ 1 + 100 × ( x - y ) - 2 ] - 1 , x > y

Suppose that there is a compound fuzzy relation R © R, meaning that x is far greater than y. Then we have R © R (x,  y) = ∨  _z  (R  (x,  z) ∧ R  (z,  y)) and would get

∨ z ( R ( x , z ) ∧ R ( z , y ) ) = ∨ z R ( x , z ) = R ( z 0 , y ) whenR ( x , z ) ⩽ R ( z , y ) ;

∨ z ( R ( x , z ) ∧ R ( z , y ) ) = ∨ z R ( z , y ) = R ( x , z 0 ) whenR ( z , y ) ⩽ R ( x , z ) . In other words, we can get z₀ that makes R  (x,  z) equal to R  (z,  y). That is, [1 +100 × (x - z) ^-2] ^-1 = [1 + 100 × (z - y) ^-2] ^-1. Then we further get the following membership function for R © R. R ( x , y ) = { 0 , x ⩽ y [ 1 + ( 100 × ( x + y ) / 2 ) - 2 ] - 1 , x > y

In order to accommodate the fuzzy relations into SPARQL, we apply FILTER (Fuzzy Relation (?X, ?Y) [WITH s _i ]) to express the fuzzy constraints between two variables in the FILTER expression.

Example 2. Suppose that a user would like to find the name, height and weight of some male individuals who are of middle height and physical health. This query can be formalized in SPARQLf as follows.

#FQ#

SELECT ?name, ?height,? weight WHERE {

?x foaf:name ?name.

?x ex:hasHeight ?height.

?x ex:hasWeight ?weight.

FILTER (?height=medium tall WITH s₃ &&

        Health (?height, ?weight) WITH s₅)

}

In the query above, #FQ# is placed before the SELECT clause, indicating that the SPARQL query is a fuzzy one. In addition, Health (?height, ?weight) WITH s₅ is used to indicate a fuzzy relation between height and weight, and s₅ is used to indicate the threshold of constraints in the query condition.

3.3 Preferences

It is very common to use preferences in human natural language. Thus to support users’ demands well, it is very necessary to accommodate preferences in queries. In this section, we apply the orderly linguistic values for dimensional preferences.

In order to construct users’ preferences in SPARQL, we introduce two keywords AND and SUPERIOR.

The keyword AND is used to express independent preferences and SUPERIOR is used to signify prioritized preferences. We define AND and SUPERIOR as binary relation connection identifiers. Let P _i , P _j and P _k be three atomic preferences. For AND, we have the followings.

Law 1 (commutative law): P _i AND P _j  = P _j AND P _i ;

Law 2 (associative law): P _i AND (P _j AND P _k ) = (P _i       AND P _j ) AND P _k ;

Law 3 (idempotent law): P _i AND P _i  = P _i ;

For SUPERIOR, we have:

P _i SUPERIOR (P _j SUPERIOR P _k ) = (P _i       SUPERIOR P _j ) SUPERIOR P _k .

Note that SUPERIOR does not satisfy the commutative law because of the strict partial order relationship between the two atomic preferences. So P _i SUPERIOR P _j is not equal to P _j SUPERIOR P _i . When AND as well as SUPERIOR appears together, we have the followings.

Law 4: P _i SUPERIOR (P _j AND P _k ) = (P _i       SUPERIOR P _j ) AND (P _i SUPERIOR P _k )

Law 5: P _i AND (P _j SUPERIOR P _k ) ≠ (P _i AND P _j )       SUPERIOR (P _i AND P _k )

Now we investigate how to quantitatively convert a dimensional preference to a weight vector in a semantic perspective. For this purpose, we first define two relational operators: ⊕ for AND and ⊗ for SUPERIOR. Also we use S _Δi to indicate the orderly linguistic value of P _i . We have the following rules to convert an original preference to a weight vector.

Rule 1: P _i AND P _j  ≅ S _Δi  ⊕ S _Δj ;

Rule 2: P _i SUPERIOR P _j  ≅ S _Δi  ⊗ S _Δj ;

In order to obtain the relatively independent weight of atomic preference after SUPERIOR, we define a notion of conditional probability.

Definition 5. (conditional probability). Let A and B be two atomic preferences, and S _ΔA and S _ΔB be their orderly linguistic values, respectively. Suppose that A and B has a relationship of A SUPERIOR B. Then B has a conditional probability with respect to A, denoted CP (B|A).

With CP (B|A), we have the independent weight of B, denoted CP (B|A) * S_vartriangleB. Here CP (B|A) can be calculated by counting N (AB) and N (A). The former represents the number of results satisfying both A and B, and the later represents the number of resultsmeeting A.

The relational operators ⊕ and × and the conditional probabilities satisfy the following rules.

Rule 3: S_vartrianglei ⊕ S_vartrianglei = S_vartrianglei;

Rule 4: S_vartrianglei ⊗ S_vartrianglej = S_vartrianglei ⊕ CP  (P _j |P _i ) * S_vartrianglej;

Rule 5: CP  (P _k |P _i ) * S_vartrianglek ⊗ CP  (P _k |P _i P _j ) * S_vartrianglek = indent   CP  (P _k |P _i P _j ) * S_vartrianglek;

Rule 6: CP  (P _k |P _i ) * S_vartrianglek ⊗ S_vartrianglej =  CP  (P _k |P _i ) * indent   S_vartrianglek ⊗  CP  (P _j |P _i P _k ) * S_vartrianglej;

Rule 4 means that the conditional probability must be considered while calculating the weight of the right operand with respect to ⊗. Rule 5 describes a preference which must satisfy the most restrictedconditions.

Using the rules presented above, we can obtain a preference with the form of r₁ * S_vartriangle1 ⊕ r₂ * S_vartriangle2 ⊕ … ⊕ r _n  * S_vartrianglen. Here n indicates the number of atomic preferences, and r_i indicates a weight coefficient, either a conditional probability or a product of probabilities. Then we use the vector of (r₁ * S_vartriangle1,  r₂ * S_vartriangle2,   … ,  r _n  * S_vartrianglen) to represent this preference.

3.4 Syntax of SPARQLf-p

The SPARQLf with preferences is denoted as SPARQLf-p. In this section, we summarize the syntax of SPARQLf-p. The SPARQLf-p consists of three parts, which are “Query”, “Constraint” and “PREFER”.

Part 1: Query

In SPARQLf-p, element QueryType is introduced into SELECT query [6] to indicate the query type, either the fuzzy type or the top-k fuzzy type. We use keywords #FQ# to declare that the query is fuzzy, and use #top-k FQ# to declare that the query is top-k fuzzy.

Part 2: Constraint

In addition to the three original elements (i.e., BracketedExpression, BuiltInCall and FunctionCall) in the classical SPARQL, the “Constraint” element is extended with a “FlexibleExpression” element, which contains fuzzy terms elements and fuzzy relation element. Element FuzzyTermExpression is a representation of fuzzy terms that is consisted of symbols =, ≠, >, ≥, <and ≤. The FuzzyOperatorExpression is an expression with simple fuzzy operator or modified fuzzy one. The structure of FuzzyRelationExpression is SimpleFuzzyTerm (Var, Var) [WITH s _i ], which describes the fuzzy relation between twovariables.

Part 3: PREFER

The PREFER is an additional part to construct preference expression, which is added to the SolutionModifier part. At this point, the keyword AND constructs the independent preferences and SUPERIOR constructs the prioritized preferences. And its syntax form is SuperiorPreference (‘AND’ SuperiorPreference)*, where the SuperiorPreference is AtomicPreference (‘Superior’ AtomicPreference)*, and the AtomicPreference element is an atomic preference with weight of orderly linguistic value.

Table 2 presents the syntax of SPARQLf-p.

Example 3. Now we use an example to illustrate the SPARQL query containing three parts discussed above. Suppose that a user would “find all persons who are less than 40 years old and with height close to 175 cm and physical health, with preferences of age constraint in a medium degree and height constraint in a high degree with priority to weight constraint in a somewhat high degree”. With the SPARQLf-p, the query can be formalized as follows.

#FQ#

SELECT ?X WHERE {?X ex:has Age ?age.

FILTER (?age <40) WITH s₃.

  ?X ex:hasHeight ?height.

  FILTER (?height close to 175 WITH s₅).

  ?X ex:hasWeight ?weight.

  FILTER (HEALTH (?height,?weight) WITH s₃)

  }

PREFER

  (?age <40) WITH s₃

  AND

  (?height = medium) WITH s₅

  SUPERIOR (?weight) WITH s₄.

4.1 Translation of fuzzy terms and fuzzy operators

First we concentrate on the translation of simple fuzzy terms and modified fuzzy term. For FILTER (?X θ FT [WITH s _i ]), s _i is converted into a fuzzy number with membership function according to Table 1. Then FT with s _i an interval, written as FT  (s _i ) = [x,  y], and fuzzy queries can be translated into crisp ones according to the rules given in Table 3.

Let FT₁ and FT₂ be two fuzzy terms and s _i be an orderly linguistic value. Also let FT₁ (s _i ) = [x₁,  y₁] and FT₁ (s _i ) = [x₂,  y₂]. For FILTER (?X between FT₁ and FT₁ WITH s _i ) in the constraints, it is converted into ?X ≥ FT₁ WITH s _i && ?X ≤ FT₂ WITH s _i and then into ?X ≥ y₁ && ?X ≤ x₂ according to Table 4. Table 4 gives the translation rules for the compound fuzzy terms.

For the translations of “FT₁ or FT₂” and “not FT”, ones can refer to [6].

Second we focus on the translation of fuzzy operators. Here we mainly discuss three kinds of fuzzy operators, which are “closeto”, “atleast” and “atmost”.

Case 1: close to

For FILTER (?X θ ˜ Y)[WITH s _i ], the operator θ ˜ represents “closeto”. This fuzzy operator along with the crisp value Y actually forms a fuzzy term, which corresponds to a membership function. The membership function of “closeto” is defined as μ _closetoY   (Y) (u) = (1 + ((u - Y)/b) ^-2) ^-1. According to the membership interval [λ₁, λ₂] of s _i , we choose λ₁ as a threshold and then get α-cut sets [x,  y]. With the interval [x,  y], we can translate fuzzy queries into crisp ones.

Example 4. Assume that we have a query “find the jobs with salary very close to 10000”. The query is formatted with f-SPARQL as follows.

#FQ#

SELECT ?X WHERE {

  ?X rdf:type WorkPos.

?X ex:monthSalary ?salary.

  FILTER (?salary close to 10000 WITH s₅).

}

Here we choose 1000 as the value of b in the above membership function. That is μ _closetoY  (Y) (u) = (1 + ((u - Y)/1000) ^-2) ^-1. According to the mapping rules between orderly linguistic values and trapezoidal member degree in Table 1, we get λ = 0.71 based on s₅. Then the interval of λ-cut set can be computed and we have Y _λ  = [936,  10639]. Furthermore, ?salary close to 10000 WITH S₉ is converted into ?salary ≥ 9361 and ?salary ≤ 10639.

Case 2: at most and at least

We can directly make translations from “at most Y” to “≤ Y” and from “at least Y” to “≥ Y”, respectively.

4.2 Translation of fuzzy relationships

Let R  (x,  y) be a fuzzy relationship between variables x and y. To translate the fuzzy relationship into a crisp one, we identify the following three cases for R  (x,  y).

Case 1: there are not any constraints on either x nor y.

For the given s _i , an interval [λ₁, λ₂] of the membership degree can be obtained. Then the reciprocal fuzzy relationship is converted into λ₁ ≤ R (?X, ?Y) ≤ λ₂.Such a expression containing arithmetical operations on variables is allowed in the traditional FILTER constraints and is written as R (?X, ?Y) ≥ λ₁ && R (?X, ?Y) ≤ λ₂.

Case 2: there is a fuzzy constraint either x or y.

First we make a preliminary translation and get λ₁ ⩽ R  (x,  y) ⩽ λ₂. Suppose that the fuzzy constraint is only on variable x, where x has a crisp range. Then using the inequalities on x and y with the range of x, we can get the expressions of y represented by x. The expressions about y can be translated as y ∈ [f₁ (x) ,  f₂ (x)], y ∈ [min(U) ,  f₁ (x)] or y ∈ [f₂ (x) ,   max(U)]. Among them, min   (U) and max   (U) mean the minimum value and maximum values of y in its domain, respectively. Finally we can combine these two expressions together and get yθf (x) to represent the constraints on x and y.

Example 5. Assume that the constraint in a query contains “u is very close to 5 and v is fairly bigger than u”. The filter representation is “u close to 5 WITH s₅ and R  (v,  u) WITH s₄”. With the membership function of “u is much greater than v” (in Section 3.2) and the function of “u close to Y” (in Section 4.1), in which 4 is selected as the value of b, we can get the translation results as follows.

the translation result of the single variable u is u∈ [4.08, 5.92];

Case 3: there are fuzzy constraints on both variables in the fuzzy relationship.

Two variables in this case need to be translated, respectively. The translation result of x is x θ f (y) and the translation result of y is y θ g (x). The final constraints are translated to x θ f (y) && y θ g (x).

For the case that there is not a direct simple fuzzy relationship between two variables given in the query, additional fuzzy compositional operations are needed before translating. The basic idea is to first convert the indirect fuzzy relationship to a simple fuzzy relationship and then the translation results can be obtained according to the different cases discussed above.