in which period of time the deduced BGP was processed.
At the bottom of Figures REF  and REF  there are deduced BGPs corresponding to queries appearing at the top of these Figures. Information about which endpoints collaborate with which triple pattern, the federated query engine that issued the query, and the time period where the queries were processed appear too.
FETA: FEderated query TrAcking
Figure REF  describes how FETA processes a
federated log. A federated log is a sequence of subqueries with
answers as described in Table REF . The goal is to
link different subqueries participating in the same join, in order to
reconstruct federated BGPs. T\(_\bowtie \), Same queries and Common join condition, allow to join subqueries'
BGPs. NLFO, Same Concept/Same As and Not Null Join
verify joins and potentially unlink BGPs.
<FIGURE>T\(_\bowtie \) identifies subqueries of the same time interval
that will be analyzed together. For instance, all subqueries in Table
REF , are captured in the interval of few seconds. The
challenge is to choose the appropriate time interval. A small window
may separate subqueries pertaining to the same federated query. A
large window may join subqueries of different federated queries.
Same queries merges identical subqueries but also
subqueries differing only in their offset values. Same queries are
sent twice to the same endpoint to be sure obtaining an answer and to
different endpoints in order to have complete answers. For instance,
every query in Table REF  is sent twice consecutively
to each selected endpoint. Additionally in Figure REF , we observe that the first two triple patterns of CD6 are evaluated separately to different endpoints, with the aim of having complete answers. Similar queries with different offsets, on the other hand, are sent to avoid reaching the endpoint's limit response. For instance, the subqueries below which are sent to Geonames for evaluating query CD7, are merged by FETA and considered as a unique subquery without the part limit/offset:
draw, text width=9.5cm] at(0,1.7) SELECT ?location ?news WHERE {
?y <http://data.nytimes.com/elements/topicPage> ?news
?y <http://www.w3.org/2002/07/owl#sameAs> ?location }
LIMIT 10000 OFFSET 0
;
draw, text width=9.5cm] at (0,-0.2)SELECT ?location ?news WHERE {
?y <http://data.nytimes.com/elements/topicPage> ?news
?y <http://www.w3.org/2002/07/owl#sameAs> ?location }
LIMIT 10000 OFFSET 10000 ;
Common join condition, joins BGPs of queries having common
projected variables or triple patterns with common IRI/literal on their subjects or objects. We are aware that, in general, subqueries are joined on their common projected variables. However, we consider also IRIs and literals, even if it can produce some noise on our deduction approach, because they are used in some cases as a common join condition. For instance, in Figure REF , the IRI dbpedia:Barack_Obama, is a join condition between triple patterns of CD2. We presume that subqueries with common join condition, closely in time, may be joined locally at the query engine using the symmetric hash operator. For instance, in Table
REF , all subqueries have variable ?pres in common and thus we
suppose they are joined at Anapsid.
Nested Loop with Filter Options (NLFO), verifies if BGPs, joined in
the previous heuristic, were executed with a nested loop operator. In
particular, we group queries varying only in their filter
values, if these values are contained in answers of a previously evaluated subquery, with which we confirm that they are joined. For instance, in Table REF  we identify that
filter values of subquery 3 correspond to answers of variable ?pres, e.g., <http://dbpedia.org/resource/Barack_Obama>, for subquery
2. This certifies a nlfo between subqueries 2 and 3, discarding a
global symhash join among the three subqueries.
Same Concept/Same As, verifies if answers of joined queries
correspond to same concepts or concepts related with a sameAs
property.Note that we do not consider generic concepts for this heuristic, e.g.,
<http://www.w3.org/2002/07/owl#Thing>.
 If this is not the case, concerned BGPs are unlinked. For instance, in Table REF , answers of the triple
pattern of subquery 1 have the same concept with the second triple
pattern of subquery 3, for variable ?pres, i.e.,
<http://dbpedia.org/ontology/President>.
Not Null Join, verifies if a join returns an empty set of
answers. If this is the case, concerned BGPs are unlinked. For
instance, in Table REF , triple patterns in subqueries
1 and 3 have a common value for projected variable ?pres, i.e.,
<http://dbpedia.org/resource/Barack_Obama> and therefore they remain linked in the same BGP.

Experiments
We analyzed the collection of 7 federated queries of Cross Domain (CD)
of the benchmark FedBench [1]}. Datasets
are those concerned by these queries: DBPedia, Jamendo, LMDB, NYTimes,
SWDF and Geonames. Virtuoso
OpenLinkhttp://virtuoso.openlinksw.com/ 6.1.7 is hosting
SPARQL endpoints. We used Anapsid 2.7 as federated query engine with
the cache disabled. Answers of endpoints to the subqueries they
received, are captured with tcpdump
4.5.1http://www.tcpdump.org/. FETA is implemented in Java
1.7 and the collected federated log is stored in a CouchDB
databasehttp://couchdb.apache.org/.
We evaluated FETA under two configurations. In the first
configuration, one Anapsid client processes all federated queries
sequentially with a delay between each query. In the second one, one
Anapsid client processes all queries concurrently, each one into an
individual thread. Executing queries concurrently from a single client
is clearly a worst case scenario for FETA because the IP address of the client
cannot be used to split subqueries of the federated log. For the scope of
this paper, we suppose that all endpoints concerned by federated
queries share their logs.
With the first configuration, FETA reconstructs correctly all
federated BGPs of the CD collection. Each deduced BGP corresponds to the federated query, once simplified and rewritten by the query engine at the query decomposition phase. We focus now on the
second experiment. In this case, Anapsid produces 529
subqueries.Note that we subsequently remove ASKs and consider only SELECT subqueries. Size of queries and answers logs are of 300KB and 14MB, respectively.
<TABLE>Table REF  shows the number of BGPs produced after each heuristic following the FETA execution workflow shown in Figure REF . FETA processes this federated log in approximately 90 seconds. \(T_\bowtie \)  is not significant here, we consider it big enough to cover the execution of all federated queries of CD. Initial log contains 238 SELECT subqueries as they are unlinked, there are 238 BGPs. Same queries heuristic removes or merges more than 60% of subqueries and their respective answers, producing 109 BGPs. Common join condition produces a single BGP because chaining among queries. NLFO confirms joins, by identifying the injection of answers from a subquery into subqueries which vary only in their filter values. Same Concept/Same As heuristic unlinks some joins and certifies others. Not Null Join certifies that a symmetric hash is certainly possible, because an intersection of answers on a common projected variable of every two subqueries.
<FIGURE><FIGURE><FIGURE><FIGURE>Figures REF -REF  present BGPs extracted by FETA for all concurrently executed CD queries. Note that query plans established by Anapsid for each query, may differ depending on endpoints availability and when operators are blocked. Ideally, FETA should reconstruct 8 BGPs. The CD collection consists of 7 queries but CD1 is a union query normally decomposed in 2 BGPs. FETA extracted 4 BGPs containing the 8 original BGPs. Even if this result is not precise, extracted BGPs with endpoints' information give valuable information to data providers bout how their data are processed and (potentially) joined with other endpoints. In the following paragraphs, we explain how FETA deduces each particular BGP.
Figure REF  describes how FETA processes federated queries CD1, CD2 and CD3. CD1 is composed of two BGPs separated by a union, which we expect to identify individually. In fact, these two BGPs were deduced as a single BGP because they have a common IRI, dbpedia:Barack_Obama and also share common answers for both variables ?predicate and ?object which concern Barack Obama. Next, we observe that CD1, CD2, and CD3 were grouped in one BGP. CD1 and CD2 were not separated because of the common IRI dbpedia:Barack_Obama, which is actually also a join condition between triple patterns of CD2. BGPs of CD2 and CD3 were not separated because results of CD2 are included in CD3 for their common triple pattern, \(?x \ nytimes:topicPage \ ?page\) , but also for the other triple patterns of CD2.
In Figures REF  and REF , we can see that BGPs of CD5 and CD6 were well reconstructed. CD4 and CD5 are linked in the same BGP with Same Concept/Same As, as both concern films. Subsequently, Not Null Join separated CD4 from CD5 on the content of the ?film variable, as CD4 concerns films related to Tarzan while CD4 concerns films of Italian directors. In a similar way, CD6 and CD7 are linked with Same Concept/Same As, as both concern localizations but they were separated because they have no common answer for variable ?location as the first concerns the Federal Republic of Germany and the second California, USA.
Figure REF  shows FETA's deduced BGP, grouping CD4 and CD7. On the other hand CD4 and CD7 share common concepts but also answers because, for the currently employed heuristics, we infer that these two queries share the same triple pattern \(?y \ nytimes:topicPage \ ?news\) .
From this experiments we conclude that (i) it is possible to reconstruct precise federated BGPs if federated queries are different enough, and (ii) reconstructed BGPs contain all original BGPs, i.e., false joins are not deduced.

Related Work
Federated query tracking is related to web
tracking [2]}. In web tracking, a first-party
website authorizes a third party to learn about its users. Analogously, FETA plays the role of the third party.
However, logs collected in federated query tracking is the result of
the execution of a physical plan in distributed query processing
compared to a more simple web navigation flow in web tracking.
Extracting information from raw logs is traditionally a data mining
process [3]} involving the following steps:
[(i)]
data selection identifies the
target dataset and relevant attributes that will be used to derive
new information;

data cleaning removes noise and
outliers, transforms field values to common units, generates new
fields and finally brings the data into the structured data schema
that is used for storage, e.g., relational databases, XML;

data mining applies data analysis and discovery algorithms
based on machine learning, pattern recognition, statistics and other
methods;

finally evaluation presents the new knowledge
in a form that will be also understandable from the end user, e.g.,
through visualization.
FETA can be located at the data mining step because it transforms raw logs
into a sequence of sets of BGPs. In experiments, we presented one
extraction for a period of time. Repeating extractions will generate a
sequence of extracted BGPs than can be used for association rules
mining of frequent pattern detection.
Conclusions and future work
Federated query tracking allows data providers to access secondary data in Linked Data federation. We proposed FETA, a federated
query tracking approach that extracts original federated Basic Graph Patterns
from a shared log maintained by data providers. FETA links and
unlinks variables present in different subqueries of the federated log
by applying a set of heuristics we presented in this paper.
Even in a worst case scenario with Anapsid, FETA extracts BGPs that contain
original BGPs of federated join queries. Extracted BGPs with endpoints'
information give valuable information to data providers about which triples are joined, when and by whom.
We think FETA opens several interesting perspectives. First,
heuristics can be improved in many ways by better using semantics of
predicates and answers. Second, we conducted experiments on one slice of federated
log. Repeating BGPs extractions on successive slices allows to apply
traditional data mining techniques such as extracting frequents
patterns. Third, we limited experiments to Anapsid. Extending to FedX
query engine [4]} will challenge proposed
heuristics because FedX physical operators produce slightly
different query traces.
