We study the properties of optimal patterns, our novel extension of Sparql, that allows for a ne-grained control over incompleteness of query answers in knowledge graphs. Optimal patterns encode preferences over the completeness of query answers. In this paper, we add language constructs for expressing dependencies between con icting preferences. Furthermore, we provide discussions and proofs of fundamental results concerning Sparql with optimal patterns.
One of the major di culties in working with knowledge graphs is that entities
may vastly di er in their structural representation, even if they are of the same
kind. Indeed, due to limitations of the underlying sources and knowledge
extraction processes it is quite common that in practical instances two entities
(represented as nodes or resources) share a type, but may be characterized in totally
di erent ways regarding their properties. The consequences are unexpectedly
small or even empty result sets when querying basic graph patterns (conjunctive
queries), usually followed by a lot of manual query re nements in the retrieval
process. Thus, operators for handling such heterogeneity are mandatory when
designing a robust query language for knowledge graphs. Sparql [
A OPTIONAL B OPTIONAL C.
Then we may get results satisfying A alone, results that additionally satisfy B
or C, and results that satisfy all three patterns. In fact, the number of result
schemas can be exponential in the number of OPTIONAL operators in a query.
We recently proposed optimal patterns [
The new OPTIMAL operator for Sparql enables the expression of structural as well as some value preferences. These preferences can be used to satisfy a user's information need if no perfect results can be found. For instance, a user may ask for a car with sunroof and air conditioner that costs less than 10,000e. If such con gurations are not available in the data, cars with fewer features or higher prices are still relevant. Evaluating queries that use our OPTIMAL operator automatically retrieves the best possible answers. Thus, a user can receive useful information instead of having to manually tweak her search settings until a result can be found.
OPTIMAL positions itself between the rather restrictive query conjunction
and the loose optional patterns of Sparql. In our previous work [
Optimal patterns alone lack the ability to describe complex dependencies between preference patterns. As we will argue with concrete query examples in Sect. 4.1, we cannot express what we call positive and negative dependencies. For instance, the preferred color of a car may only be relevant for a certain type of car but irrelevant for others. Similarly, optimal patterns do not allow for modeling the next-best preference if one preference cannot be satis ed. Therefore, we extend our earlier work introducing structural preferences into Sparql with a focus on retrieving reasonably sized result sets over incomplete data sets. We analyze how multiple preferences can a ect each other leading to a characterization of di erent types of dependencies (Sect. 4). In order to cope with these di erent types, we then introduce a suitable set of operators to be used in conjunction with OPTIMAL.
Modeling preferences with Sparql has been the goal of several language
extensions [
Since Sparql is the recommended query language for the Resource Description
Framework (RDF) [
Sparql o ers expressions for querying information from RDF graphs. We
restrict our presentation to pattern matching capabilities, e. g., leaving out path
queries. Abstract syntax and semantics of Sparql follow the standard
notation [
Let t = (u; a; v) be a triple pattern and G an RDF graph. A partial function : VIL ! IL is called a match of t in G i (a) (c) = c for all c 2 IL, (b) fu; a; vg dom( )4, and (c) ( (u); (a); (v)) 2 G. By ;IL we denote the empty match, being the partial function that respects (a) but is otherwise undened. The notion of a match naturally extends to BGPs G by requiring that is a match of all triple patterns t 2 G. We denote the set of all matches of t (G, resp.) in G by JtKG (JGKG, resp.).
Sparql further supports complex queries in terms of unions, query
conjunctions, optional patterns, and lter conditions. The semantics of such queries Q
(w. r. t. RDF graphs G) can be found in [
Throughout this section, we present our extension of Sparql by optimal
patterns. Additional examples, an encoding by standard Sparql, as well as an
initial evaluation may be found in [
As with the other Sparql structures, OPTIMAL combines queries Q1 and Q2 to an optimal pattern Q1 OPTIMAL Q2. The intuition of optimal patterns is that we state a preference for matches that are complete w. r. t. Q1 and Q2, i. e., in the optimal case, we get the matches of Q1 AND Q2. Only if this goal is impossible to reach, i. e., there could be matches of Q1 but no compatible ones of Q2, we expect the matches of Q1. The semantics of optimal patterns will adhere to the following property:
JQ1 AND Q2KG
(1) More concretely, if there are matches of Q1 AND Q2 in G, then JQ1 OPTIMAL Q2KG = JQ1ANDQ2KG. Unlike the respective optional pattern Q1OPTIONALQ2, we do not include a single match of only Q1 in this case. This matching behavior allows us to express preferences over the completeness of the matches w. r. t. a given RDF graph. Only if JQ1ANDQ2KG = ;, the respective semantics of optimal patterns and optional patterns align.
As long as Q1 and Q2 are free of optimal patterns, the previous paragraph tells us the whole story of the new operator. The combination of (several) optimal patterns with lter constraints allows for formulating meaningful preference patterns on data values and structure.
Example 1. OPTIMAL can be used to model preferences over attribute values. A simple price preference could be: I prefer cheap cars under 15,000e over other cars under 20,000e over more expensive cars. It can be adequately modeled in the form of: ?car rdf:typeof Car OPTIMAL f ?car ex:price ?price FILTER( ?price < 15000 ) g OPTIMAL f ?car ex:price ?price FILTER( ?price < 20000 ) g The query will return all cars that are cheaper than 15,000e if any exist. If not, then it will return all cars that are cheaper than 20,000e instead. If no such car exists either, then the query will return all cars in the data set that are more expensive or have no available price information.
Example 2. A user can pose structural preferences as well. Such a query could be I prefer to see cars with available price and brand information. Such a query could be adequately modeled as: ?car rdf:typeof Car OPTIMAL f ?car ex:price ?price g OPTIMAL f ?car ex:brand ?brand g The query will return all cars with information for price and brand. If no such cars can be retrieved, it will instead return all cars with price information. If that also results in an empty set, then the query will return all cars with brand information instead. Only if all of these attempts yield empty results, then the query will return all cars instead.
The last example shows how optimal patterns may be used to impose an ordering on the preferred structure. To allow for the formulation of preferences of equal importance, we extended the syntax of optimal patterns Q1 OPTIMAL Q2, allowing Q2 to be a nite list of queries Q12; Q22; : : : ; Q2n, i. e., the syntax of these optimal patterns is
Q1 OPTIMAL (Q12; Q22; : : : ; Q2n).
The intuition is still that Q1 is necessary to be matched. However, a simple correspondence as in Equation (1) cannot be derived. In the optimal case, we nd matches of all of the queries in the optional pattern, i. e., JQ1 AND Q21 AND Q22 AND : : : AND Q2nKG JQ1 OPTIMAL (Q12; Q22; : : : ; Q2n)KG.
Whenever we cannot reach the optimal case, we will obtain dominant matches as answers.
Example 3. Given the query from Example 2, a possible answer could be a car for a price of 17,000e but of no known brand. This result contains more information than one with completely unknown attributes. Thus, the rst match dominates the second one. A match concerning a third car with a price of 18,000e and a known brand contains even more information on the other hand. Thus, the rst match is dominated by the third one. If we consider price and brand to be of equal importance, then the rst match would not dominate a fourth one that only has brand information. The two matches would be incomparable. If we consider the price to be more important instead, then the fourth match does not appear in the result set. The just sketched process is like asking for a skyline over the price (which does not include the fourth match) and then construct a skyline over the brand for the previous results.
Hence, the new construct requires a Pareto-style semantic, which entails a skyline of matches. Subsequently, we order candidate matches by Pareto dominance. Only the maximal candidates (w. r. t. Pareto dominance) are considered matches of optimal patterns.
JQiKG [ f;ILg (0 < i 0 [ 1 [ 2 [ : : : [ k.
Q = Q0 OPTIMAL (Q1; Q2; : : : ; Qk) for some integer k > 0. A partial function : VIL ! IL is called a candidate match of Q in G i there are 0; 1; 2; : : : ; k, such that 1. 0 2 JQ0KG, 2. i 2 k), 3. i j for all i; j 2 f0; 1; 2; : : : ; kg, and 4. = The rst requirement accounts for the fact that Q0 is the necessary pattern to be matched. Note, every other part of may be the empty match ;IL. Using the separation of candidate matches of Q (in G) into 0; 1; 2; : : : ; k, we say that covers Qi (0 i k) i i 6= ;IL. Note, Q0 must be covered by all candidate matches. We denote by coverQ ( ) the set of all sub-queries Qj 2 fQ0; Q1; Q2; : : : ; Qkg covered by . Then the semantics of optimal patterns boils down to the maximal matches w. r. t. inclusion of the sets of covered subqueries.
tern, G an RDF graph, and ; 0 two candidate matches of Q in G. 0 dominates w. r. t. Q, denoted by Q 0, i coverQ ( ) ( coverQ ( 0).
Candidate match of Q in G is called a match of Q in G i there is no candidate match 0 of Q in G with Q 0. The set of all matches of Q in G is denoted by JQKG.
This formalization allows us to derive correctness of (1) for the special case of optimal patterns with a single query as the right-hand side.
Proposition 1. For all Sparql queries Q1 and Q2, (1) holds.
Proof. Let be a match of Q1 AND Q2. Then there are matches i 2 JQiKG (i = 1; 2) with = 1 [ 2 and 1 2. Thus, is a candidate match of Q0 = Q1 OPTIMAL Q2. Furthermore, every match of Q1 AND Q2 covers Q1 and Q2 in Q0. Hence, cannot be dominated by any other match of Q0 in G.
Let 0 be a match of Q0 = Q1 OPTIMAL Q2. We need to show that 0 is a match of Q1 OPTIONAL Q2. Towards a contradiction assume, 0 is not a match of Q1 OPTIONAL Q2. Then 0 2 JQ1KG but there is a match 00 2 JQ2KG, such that 0 00. But then 0 [ 00 is a candidate match of Q0 and
coverQ0 ( 0 [ 00) = fQ1; Q2g ) fQ1g = coverQ0 ( 0), which contradicts the assumption that 0 is a match of Q0, i. e., 0 is not dominated by any other candidate match. tu Subsequently, we justify the syntax style of query lists in optional patterns and we consider RDF's open world assumption in the context of optimal patterns. 3.1
Justifying Optimal Patterns Our divergence from the standard binary operator structure of Sparql may seem peculiar at rst. However, this was a necessary step to allow for expressing preferences of equal importance. Suppose, we want to express a preference of query Q over Q1 and Q2, but Q1 and Q2 are equally important. Without the query list notation, we have several candidates using optimal patterns and standard Sparql operators: { Q OPTIMAL (Q1 UNIONQ2): This query returns all the matches of Q, preferably joined with matches of Q1 or Q2. However, as soon as Q1 and Q2 have a shared variable, we will hardly see any matches ful lling all three sub-queries. { Q OPTIMAL (Q1 AND Q2): From this query we may expect only matches that ful ll all three sub-queries or only Q. Hence, if Q1 cannot be matched, we will also not see matches that ful ll Q and Q2. { (Q OPTIMAL Q1) AND (Q OPTIMAL Q2): This query is quite close to the desired Pareto query. Here, Q1 and Q2 are seen as independent through the use of query conjunction. For queries of that shape we may actually observe matches ful lling all three sub-queries or only a subset of these. However, this query also accommodates some weird matching behavior. Suppose, Q1 and Q2 share a variable x, that does not occur in Q, but Q1 and Q2 cannot simultaneously be matched in some RDF graph G. Then the query above may easily yield no results at all, although Q may be matched together with Q1 or Q2 separately.
Besides the possibilities above, it is always possible to unfold the Pareto query exponentially. However, such queries are hardly readable and maintainable. Therefore, we decided to expand Sparql's operator set in this respect. 3.2
Optimal Patterns and Certain Answers
How well do optimal patterns cope with RDF's open world assumption (OWA).
The OWA in uences the way the query semantics is actually executed. We often
see query semantics following the certain answers perspective [
CertainAnswers(Q; G) := TH GJQKH.
Iterating over all in nitely many extensions H of G is infeasible in practice. Therefore, handy characterizations can be proven. One such characterization is concerned with the monotonicity of the given query Q. A query Q is monotone i for all RDF graph G H, JQKG JQKH, i. e., adding more information may only lead to more query results. Since more information may lead to di erent matches that cover more sub-queries, Arenas and Perez introduced the notion of weak monotonicity. A query Q is weakly monotone i for all RDF graphs G H. 2 JQKG implies the existence of a 0 2 JQKH with 0. It can easily be shown that in the case of (weakly) monotone queries Q, CertainAnswers(Q; G) coincides with JQKG.
Unfortunately, not all queries containing optimal patterns are weakly monotone. For instance, the third query shape in Sect. 3.1 is not monotone. Consider Q1 and Q2 to share a variable x, that is not shared with Q. Now construct G in such a way that it ful lls Q and Q1 but not Q2. Disjointly add a minimal structure to G that ful lls Q and Q2 but not Q1. Then we simultaneously match Q and Q1 as well as Q and Q2, but the respective matches are necessarily in con ict in x. Therefore, the result set will easily be empty, where it used to be non-empty when Q2 was violated.
Hence, optimal patterns are neither better nor worse than optional patterns, at least w. r. t. certain answers. It is simply two di erent styles of querying and we have to let the user decide which style is appropriate in which scenarios.
In this section we propose a solution for modeling dependencies by introducing an additional set of operators that complement OPTIMAL. Preferences may exist in various di erent types and combinations. Being able to model such dependencies is necessary to adequately model complex user requests.
Sometimes a subquery preference simply cannot return useful results for a given preference unless another part of the query also returns valid matches. This is the case when a query asks for a possibly missing node that is only indirectly related to an enforced match. For example, a query may ask for a person's car as well as their car's model. The person's car can be trivially retrieved. However, if that person does not own a car, it is impossible to give an adequate answer regarding the car's model. We call this kind of dependency a structural dependency because these directly depend on the (in-)completeness in the knowledge graph structure. In contrast, we call all dependencies that relate to data values within the modeled preference as non-structural dependencies, e. g., a user may prefer the color red for sports cars but not necessarily for other cars as well.
If one preference cannot be answered unless the found answers satisfy a speci ed condition, i. e., also cover a more relevant preference, we speak of a positive dependency. The previously given examples fall into this category. We speak of negative dependencies if one preference should only be answered if a speci ed condition remains unsatis ed, i. e., a speci c and more relevant preference is not covered. For example, a user may prefer the color blue for any car that is not a sports car with either no color preference, or a di erent one for sports cars. Negative dependencies also model di erent alternatives of unequal importance, e. g., a user interested in buying a car needs to know about the price of the object. Most likely, that user will prefer o ers made in his own currency. If no suitable matches can be found, o ers in foreign currencies may still be relevant.
Dependencies are not guaranteed to be 1:1 relations. Especially structurally dependent preferences often rely on the same condition, implying a 1:m relation. For example, asking for a person's car and its properties will result in a structural dependency of all properties towards the retrieval of a matching car. When modeling multiple alternatives of unequal importance, the opposite behavior is true. For example, a car manual should only be displayed in an unknown language if it is not available in any language the user is uent in. This yields an n:1 relationship between preferences. Mixed types of questions can also lead to general n:m relations between preferences which need to be accounted for. 4.1
Limitations of OPTIMAL Expressing interdependent preferences is already possible using existing Sparql operators which requires signi cant e ort, even more so than individual preferences. By the new OPTIMAL operator we have developed a tool to ease this process. We have also shown how it can be used for individual preferences. However, it is still not ideal for modeling dependencies.
Let us assume a user is looking for a car, preferably a sports car. If it happens to be a sports car, then the user prefers it to be red { otherwise any color is acceptable. Simultaneously, the user also prefers cars with available price information. Using multiple optimal patterns in a naive way (as shown in Example 4) does not represent these requirements.
Example 4. The following query will look for all cars, preferably sports cars. Among those, it will look for red ones. This works well if the database contains any sports car. ?car rdf:typeof Car OPTIMAL f ?car rdf:typeof SportsCar, ?car ex:hasPrice ?price g OPTIMAL f ?car ex:hasColor "red" g Additionally, the query also describes a dominance of red cars over non-red cars. A more accurate model can be achieved by nesting one optimal pattern into another one, being a technique also commonly used when modeling interdependent optional patterns.
Example 5. The following query looks for sports cars with red color rst and then combines it with other preferences. As a result, red sports cars will be preferred over other sports cars, and sports cars in general will be preferred over other cars. ?car rdf:typeof Car OPTIMAL f ?car rdf:typeof SportsCar OPTIMAL f ?car ex:hasColor "red" g, ?car ex:hasPrice ?price g This time, red cars that are no sports cars will no longer be preferred over other cars. So we managed to x the underlying problem in our model. However, the model is still not correct. Because the color preference is evaluated rst, red sports cars will always be ranked better than non-red sports cars. This also means that a red sports car without price will be ranked higher than a non-red sports car with a price. In our use case, these two preferences are meant to be incomparable.
Modeling preferences with optimal patterns alone causes side e ects by
introducing unwanted ranking of actually incomparable query answers. For sure, it is
always possible to model them correctly using complex lter conditions (cf.
encodings in [
Syntax and Semantics of THEN and OTHERWISE In order to enable an easy way of modeling dependencies, we introduce two new operators called THEN and OTHERWISE. Both operators can be used on the right-hand side of an OPTIMAL operator in order to ne-tune requirements of a preference's matching behavior. A THEN B de nes a positive dependency of B towards A, meaning that preference B should only be answered if preference A also yields a non-empty set of answers. A OTHERWISE B, on the other hand, de nes a negative dependency of B towards A, meaning that preference B is only answered if preference A does return an empty set of answers.
For our OPTIMAL operator we have already introduced lists of preferences for simultaneous evaluation (cf. Sect. 3). We apply the same concept to both sides of the new operators. For a preference A and a set of dependent preferences B towards A, A THEN (b1; b2; :::; bm) applies a matching restriction for all dependent preferences bj 2 B. They will only be answered if preference A is covered as well. Similarly, A OTHERWISE (b1; b2; :::; bm) applies a negative dependency restriction to all bj 2 B. For a set of independent preferences A and dependent preference B towards A, (a1; a2; :::; an) THEN B applies a matching restriction on B. It will only be answered if at least one ai 2 A is covered. When modeling a restriction towards all preferences in A (instead of any member) a simple conjunction can be used in order to turn the conditions into a single one. This method is best suited for handling alternative routes that lead to similar objects. Likewise,(a1; a2; :::; an) OTHERWISE B applies a matching restriction on B. It will only be answered if none of the preferences ai 2 A are covered. If both A and B are a set of preferences then both the respective restrictions apply for all bj 2 B towards all ai 2 A.
Just like the OPTIMAL operator, we de ne THEN and OTHERWISE as leftassociative. That way, the syntax for all following preferences Bi 2 fB1; :::; Bng of the form A 1 B1 2 ::: n Bn (with i 2 fTHEN; OTHERWISEg) will always imply a relation towards A, making the query easier to read. Query groups and preference list separators can be used to model the order of execution explicitly. Example 6. The following query adequately models the query we were looking for in Sect. 4.1 and thereby resolves our issues with optimal patterns. ?car rdf:typeof Car OPTIMAL (f ?car rdf:typeof SportsCar g THEN f ?car ex:color "red" g, ?car ex:price ?price ) Example 7. In the following query (with negative dependencies), we consider the price in US-Dollar as a fallback if no o ers in Euros can be found. Finding both currencies is not better than only Euros, though. ?car rdf:typeof Car OPTIMAL (f ?car ex:price EUR ?p eur g OTHERWISE f ?car ex:price USD ?p usd g) 4.3
Encoding Dependencies
In our previous work [
The encoding using UNION has proven to be more stable regarding performance. For this style we rst construct a superset of desired results by combining all possible preference combinations. For every such combination we bind a fresh variable in the respective subquery to mark which combination an answer candidate is generated from. As a next step, we retrieve the results for every subquery a second time (but with changed variable names) inside an EXISTS-operator. That way, we can determine which combinations yield at least one candidate match. Lastly, we use FILTER-conditions to remove any answers that are dominated by at least one combination with a non-empty set of matches.
This method is easily changed to adapt for the new operators. When constructing the superset, we have to rede ne what a possible combination is. Every THEN or OTHERWISE operation results in additional constraints on this set. A preference A that is dependent on B is not supposed to be matched unless a mapping for B also appears in the answer. Thus, any combination including mappings for A but not B has to be removed from the superset. Likewise, a preference A that has a negative dependency on B is only supposed to match if no mapping for B appears in the answer. Thus, any combination including mappings for both A and B has to be removed from the superset. Our prototypical implementation5 can easily be extended.
In terms of performance, we leave out an extensive analysis here. Usage of the new operators only results in removal of answer candidates. Thus, any encoded query using THEN or OTHERWISE will be shorter and most likely slightly faster than an independent preference. 5
We have presented a new set of operators for expressing structural preferences
over the completeness of knowledge graph query results. The primary extension
consists of so-called optimal patterns, which we introduced in [
Although our discussion regarding certain answers (cf. Sect. 3.2) attests
optimal patterns to have a similar behavior as optional patterns, a detailed discussion
about the expressive power/complexity may still reveal important di erences.
For future work, we plan to overcome the limitations we observed in [