\section{\label{sec:level1}Introduction}
Radio-isotope production by different methods, chemical seperation, isotope delivery, molecular targets, radiolabeling protocols and identification of clinical applications are an active area of research. Several $\beta$-emitters, $^{90}$Y (t$_{1/2}$=2.67d) and $^{131}$I (t$_{1/2}$=8.07d) emit electrons with maximum kinetic energies of 0.3–2.3 MeV with a range of $\sim$0.5 - 12 mm in tissues. Single cell disease such as leukemia, micrometastases, post-surgical residual disease and some other types of cancer may not be curable with targeted $\beta$-particle therapy due to insufficient dose to each cell \cite{humm90}. Concomitantly, a significant portion of the dose would also be deposited in the surrounding normal tissues by virtue of long range. Therefore $\alpha$-particle targeted therapy provides superior option compared to $\beta$-particle therapy. Production of $^{225}$Ac has been studied for its possible generation using proton accelerator.

Heavy ions have larger linear energy transfer and smaller penetration depth which lead to targeted killing of the cancer cell. Carbon therapy is becoming popular after proton therapy due to larger linear energy transfer. Targeted Alpha Therapy (TAT) is one of the promising and effective methods for treatment of bladder cancer, brain tumors, neuroendocrine tumors and prostate cancer due to short range (47-85$\mu$m) \cite{sgouros1,essler12} of alpha particles. The linear energy transfer from alpha particles is two orders of magnitude higher than that by $\beta$-particle. Single $\alpha$-emitter such as $^{213}$Bi eluted from $^{225}$Ac or $^{225}$Ac with 4-$\alpha$ emitting isotopes along with radio-isotopes from its decay chain are currently under immense interest for treating several malignant diseases even acute myeloid leukemia. $^{225}$Ac and daughter isotopes with 4-$\alpha$'s give 1000 times more integrated dose compared to single alpha from $^{213}$Bi\cite{Brechbiel07}. Relative biological effectiveness is 3-8 times higher for alpha particles \cite{Azure94}. Although, $^{225}$Ac is superior $\alpha$-emitting source but the fate of the free daughter radioisotopes in circulation after decay is to be resolved thoroughly.

Alpha emitters such as $^{225}$Ac are favorable due to their very short range (few cell diameters) and targeted high doses to kill cancer cells which show resistance to treatment with beta- or gamma- irradiation or chemotherapeutic drugs. Some of the gamma emission ($^{221}$Fr, 218.2keV, 11.6$\%$; $^{213}$Bi, 440.5keV, 26.1$\%$; $^{209}$Tl, 117.2keV, 84.3$\%$, 465.1keV, 96.9$\%$, 1567.1keV, 99.8$\%$;) from the decay chain of the $^{225}$Ac along its path gives $\textit{in vivo}$ imaging and pharmaco-kinetic and dosimetric studies \cite{McDevitt01}.  Long half-life  of $^{225}$Ac and the multiple alpha particles generated in the decay chain render $^{225}$Ac a particularly cyto-toxic radio-nuclide. Reactor based production of $^{225}$Ac by decay of $^{229}$Th (T$_{1/2}$=7880y) is available from few places like ORNL, USA, IPPE, Obninsk, Russia and ITU, Germany with combined inventory of $\sim$1.8Ci/year\cite{iaea2013}. There are plan to develop advance reactor system with $^{232}$Th utilization \cite{shina06}. This reactor can generate $^{229}$Th which can give $^{225}$Ac through $\alpha$-decay.

Several studies have been conducted to investigate different means of increasing the available supply of either $^{229}$Th parent or $^{225}$Ac itself.  $^{225}$Ac can be produced by proton+$^{232}$Th reaction at high energy spallation reaction as a direct product as well as it can be milked from $^{229}$Pa at low energies. $^{229}$Pa decays via emitting $\alpha$-particle to $^{225}$Ac with only 0.48$\%$ branching ratio and rest decays to $^{229}$Th. Thus, producing required quantities of $^{225}$Ac activity using low energy proton accelerator from $^{229}$Th is challenging due to its extremely long half-life despite the $\sim$160 mb cross section for the $^{232}$Th(p, 4n)$^{229}$Pa reaction at $\sim$30 MeV. Dedicated accelerator production of $^{229}$Th may not be economically viable due to long irradiation times and high currents required to produce a substantial quantity of $^{229}$Th \cite{jost2013}.

Cross-section were measured at ITU, Germany for $^{226}$Ra(p, 2n)$^{225}$Ac to seek direct production of this isotope \cite{Apostolidis05}. The cross-section peaks ($\sim$ 700mb) around 17MeV proton energy. A feasibility study of the $^{226}$Ra($\gamma$, 2n)$^{225}$Ra reaction for producing the $^{225}$Ra, the parent to $^{225}$Ac, has revealed that $^{225}$Ra yields are insignificant for practical use \cite{Melville07}.

In this paper, activity of $^{225}$Ac is estimated for p+$^{232}$Th and p+$^{226}$Ra reactions at low proton energies. A comparative study for the production of $^{225}$Ac by Thorium-232 target at different energies is performed to search an optimum energy. Monte-carlo code MONC ($\textbf{\underline{MO}}$nte carlo $\textbf{\underline{N}}$ucleon transport $\textbf{\underline{C}}$ode) \cite{hkumawat05,hkumawat04,hkroot,hkvenkata13,baras1} is used for the present simulation. In Sec. II, we present small description of MONC. Section III contains simulation studies for production of $^{225}$Ac. Conclusions are given in Sec. IV.

\section{\label{sec:level2} Description of MONC}
Monte Carlo program MONC incorporates Intra-nuclear Cascade, Pre-equilibrium,
Evaporation and Fission models to simulate spallation reaction mechanism for
thin and thick targets. Modeling details of Intra-nuclear cascade, pre-equilibrium
particle emission are described in detail in Ref. \cite{baras1}. Treatment of cutoff energy
from Intra-nuclear to pre-equilibrium and next to evaporation stage was changed
later which is described in Ref. \cite{hkumawat05}. Generalized evaporation model was developed
as described in Ref. \cite{mashnik}. Fission barrier, level density parameter and
inverse cross sections for pre-equilibrium/evaporation/fission model are given in detail in Ref. \cite{hkumawat05, hkumawat04}. The following level density parameters are used in MONC.
\begin{equation}
 a =  (0.134-.000121A)(1+(1-e^{-0.061E})\Delta S/E)     \label{eqpa229}
\end{equation}
Where $\Delta$S is shell correction, E is excitation energy and A is Mass number of the compound nucleus.
Benchmark of spallation models for experimental values of neutron, charged particles,
and pions double differential production cross-sections, particle multiplicities,
spallation residues and excitation functions was organized by IAEA and is given in Ref. \cite{hkumawat10}.
We have used the predecessor of this code named CASCADE.04 to calculate these quantities in
the benchmark. Heat Deposition algorithm for thick spallation targets and thin films was
modified and benchmarked as mentioned in Ref. \cite{hkheat08}. The code was further developed for
the Neutron shielding and dosimetry applications \cite{hkumawat09}. The code can be used for single nucleus interaction in basic reaction studies and can be invoked for the thick target simulation during the transport. Energy loss of the charged particle is calculated during the transport in the thick target.

Point data is used for the low energy neutron transport as described in \cite{hkvenkata13,hkroot}. The processing of ENDF/B neutron data library and generation of point data at required temperature is inherent feature of the code. Linear chain method is implemented to solve the Bateman's\cite{bateman06} general solution for decay and build-up of isotope inventories. ENDF-decay data library is used for the decay properties of different radio-active isotopes.

\section{\label{sec:level3}Production of Actinium}

The production of $^{225}$Ac at low energy is governed by generation of $^{229}$Pa through $^{232}$Th(p, 4n)$^{229}$Pa reaction. The reaction for  production of $^{229}$Pa as given in Eq. \ref{eqpa229}, has a threshold of $\sim$19.5MeV. Direct production of $^{225}$Ac starts at higher energies. The cross-section for direct production of $^{225}$Ac at low energies is rather low but it is generated by decay of $^{229}$Pa through direct $\alpha$ decay with 0.48$\%$ branching ratio; rest of it decays through $\beta^-$ decay to $^{229}$Th. Full decay chain is given in Fig. \ref{acchain}. The decay products of the $^{225}$Ac are also $\alpha$-emitters untill it gives $^{209}$Bi as stable isotope.
\begin{figure}
\includegraphics[scale=0.5]{ac-chain.pdf}
\caption{Decay chain of $^{225}$Ac.} \label{acchain}
\end{figure}
\begin{equation}
 p + ^{232}Th \Rightarrow 4n + ^{229}Pa  (\Delta Q = -19.446 MeV) \label{eqpa229}
\end{equation}
It is clear from Fig. \ref{acchain} that $\alpha$ decay branching ratio leading to production of $^{225}$Ac in a short span of time is only 0.48$\%$ and remaining 99.52$\%$ goes to $^{229}$Th which has long half life of 7340 years and is also available from weapons program or reactors. In case of reactor based production from Thorium, the route is given as

\begin{equation}
\begin{aligned}
{} & \{n + ^{232}Th \Rightarrow ^{233}Th \Rightarrow ^{233}U +\beta^- \\
      & \Rightarrow^{229}Th+\alpha\Rightarrow^{225}Ra+\alpha \Rightarrow^{225}Ac+\beta^-\}\label{eqra229}
\end{aligned}
\end{equation}

In order to have quantitative estimate of $^{225}$Ac activity produced by proton+$^{232}$Th system, total reaction and individual channel cross-sections are calculated and compared with experimental data. The optimum energy from proton+$^{232}$Th reaction cross-section point of view is $\sim$ 150MeV which is shown in Fig.\ref{pthcrs}. The low energy proton accelerators with higher current are easy to build compared to high energy accelerators so we have studied the production of $^{225}$Ac by low energy proton beam.

\begin{figure}
\includegraphics[scale=0.6]{p_th232.pdf}
\caption{Reaction cross-section for Proton+$^{232}$Th system using MONC} \label{pthcrs}
\end{figure}
Economical production of $^{225}$Ac would require thick target irradiation leading to energy loss of the primary proton energy. The energy loss shows a range of $\sim$2mm and $\sim$16mm at 30MeV and 100MeV proton energies for Thorium target, as shown in Fig.\ref{heatth}. The energy of the primary proton also changes along its path in thick target due to continuous energy loss. The secondary protons undergoing nuclear reaction are shown in Fig. \ref{heatth2}.
\begin{figure}
\includegraphics[scale=0.55]{heat_th1.pdf}
\caption{Heat deposition and range of proton in $^{232}$Th target for 100MeV and 30MeV proton energies.} \label{heatth}
\end{figure}
\begin{figure}
\includegraphics[scale=0.37]{p_th232_proton_dist_eloss.pdf}
\caption{Proton energy distribution after energy loss in thick $^{232}$Th target.} \label{heatth2}
\end{figure}

More than 99$\%$ energy is deposited as heat at 30MeV which reduces to $\sim$96$\%$  at 100MeV for complete beam dump. The Temperature rise of Thorium metal of diameter 10cm and thickness 2mm after one hour irradiation of 30MeV proton beam with one $\mu$A current is calculated using the following rather simple Eq.\ref{temp} without considering any cooling.

\begin{equation}
 ms\Delta T = Q (Heat) \label{temp}
\end{equation}

Here, s=0.12J/gK is specific heat of Thorium metal, m is mass and Q is heat deposited by proton beam. The temperature comes out to be ~5000K which demands dedicated cooling of the target if it is used as beam dump. A small amount of Thorium as thin foil can be irradiated to avoid such large heating.

\begin{figure}
\includegraphics[scale=0.4]{pth232_pa229_2.pdf}
\caption{Excitation function/production cross-section for the $^{232}$Th(p, X)$^{229}$Pa reaction.} \label{pthpa229}
\end{figure}

\begin{figure}
\includegraphics[scale=0.4]{pth232_th229.pdf}
\caption{Excitation function/production cross-section for the $^{232}$Th(p, X)$^{229}$Th reaction.} \label{pthth229}
\end{figure}

\begin{figure}
\includegraphics[scale=0.4]{pth232_ac225_cum.pdf}
\caption{Excitation function/production cross-section for the $^{232}$Th(p, X)$^{225}$Ac (cumulative yield) reaction.} \label{pthac225cm}
\end{figure}

Individual channel cross-section in MONC are based on the isotope production cross-section but not identification of channel in particular. The excitation function for the production of $^{229}$Pa, $^{229}$Th and $^{225}$Ac for p+$^{232}$Th system are compared with experimental data in Figs.\ref{pthpa229}, \ref{pthth229}, \ref{pthac225cm}, respectively. The cross-section data for $^{229}$Pa are taken from EXFOR data base maintained by IAEA \cite{Jost13,Lefort61}. The estimation from MONC for this isotope compared well at low energies of current interest but it overestimates between 50MeV to 100MeV range. Direct production of $^{229}$Th leading to $^{225}$Ac with long half life also has significant cross-section \cite{Lefort61} which is very well reproduced by MONC, although it has only single measured data point reported. Direct production of $^{225}$Ac has higher threshold and the measured cross-section \cite {Ermolaev12,Weidner2590,Mashnik2602,Griswold16} is also low. It should be noted that experimental data are derived from cumulative yield but MONC calculations are for independent yields. The measured data for independent yield are given by \cite{Gauvin} and depicted in the Fig.\ref{pthac225cm} by solid circles. It is to be noted that MONC compared well with these data points although the difference in cumulative and independent data is rather small.

\begin{figure}
\includegraphics[scale=0.4]{ac225_12f.pdf}
\caption{Production of $^{225}$Ac and its $\alpha$-emitter decay products after different irradiation time using proton beam of 30MeV with 1$\mu$A current for p+$^{232}$Th system} \label{ac2251}.
\end{figure}

After comparing the cross-section and heat deposition, produced activity for a thick target are estimated at different irradiation time periods. Simulation was performed for full beam deposition. Production of $^{225}$Ac in MBq per $\mu$A proton current of 30MeV energy and it's daughter products which are also $\alpha$-emitters are given in Fig.\ref{ac2251}. The combined activity for 10 days irradiation is $\sim$ 20MBq per $\mu$A which can be increased to 2GBq for 100 $\mu$A current. The main contributor of this production is $^{229}$Pa isotope as shown in Table \ref{tab:keffur}.

\begin{table}
\caption{\label{tab:keffur} Contribution of different decay channel in forming $^{225}$Ac at 30MeV proton energy for p+$^{232}$Th system.}
\begin{ruledtabular}
\begin{tabular}{ccc}
Target Thickness (mm)& Parent nucleus &$\%$ share\\\hline
 1.0    & $^{229}$Th    & 6.4452139E-08\\
 1.0    & $^{233}$Th    & 8.5865402E-15\\
 1.0    & $^{229}$Pa    & 0.999999936\\
 1.0    & $^{229}$Th    & 8.9715132E-14\\
\end{tabular}
\end{ruledtabular}
\end{table}

A comparative study for full proton beam dump in $^{232}$Th target shows significantly increased activity of $^{225}$Ac with energy as the cross-section for direct production of $^{225}$Ac increases with proton energy. The activity continuously increases with increase in energy as shown Fig.\ref{ac225_1}. Ratio of $^{225}$Ac activity at 100MeV and 30MeV shows a gain of $\sim$ 100 for complete dump of the beam. The gain factor for 300MeV compared to 100MeV is $\sim$ 80 for full beam dump in the target as shown in Fig.\ref{ac2252}. Although there is an increase in activity with proton energy increment but energy spent per MBq of $^{225}$Ac produced in this reaction as shown in Fig.\ref{ac2253}, shows that higher energies are not attractive as no significant gain in activity after 300MeV which may be termed as most optimum energy.
\begin{figure}
\mbox{\subfigure{\includegraphics[scale=0.5]{ac225_activityf.pdf}}}
\quad\subfigure{\includegraphics[scale=0.5]{ac225_mg_f.pdf}}
\caption{Production of $^{225}$Ac at different energies with 1$\mu$A current for p+$^{232}$Th system} \label{ac225_1}
\end{figure}

\begin{figure}
\includegraphics[scale=0.6]{ac225_ratiof.pdf}
\caption{Relative yield of $^{225}$Ac at 30MeV, 100MeV, and 500MeV for 1$\mu$A current for p+$^{232}$Th system.} \label{ac2252}
\end{figure}

 \begin{figure}
 \includegraphics[scale=0.4]{ac225_optimum_enef.pdf}
 \caption{proton energy spent per micro gram production of $^{225}$Ac for one and 10 day accelerator operation with 1$\mu$A current for p+$^{232}$Th system.} \label{ac2253}
 \end{figure}

\begin{figure}
\includegraphics[scale=0.4]{ra226p2n_crs.pdf}
\caption{calculated reaction $^{226}$Ra(p,2n)$^{225}$Ac cross-section using MONC} \label{pracrs}
\end{figure}

\begin{table}
\caption{\label{tab:keffur2} Production of $^{225}$Ac for 1$\mu$A proton beam current of different energies, 1mm target thickness and for different irradiation times.}
\begin{ruledtabular}
\begin{tabular}{ccccc}
Target &Thickness& Activity & Irradiation & Energy\\
       &(mm)& (MBq/$\mu$A) &  (Days)& (MeV)\\\hline
$^{232}$Th &1.0    &  5.2 & 10 &30\\
$^{232}$Th &1.0    &  9 & 20 &30\\
$^{232}$Th &1.0    &  11 & 30 &30\\
$^{232}$Th &1.0    &  83 & 10 &100\\
$^{226}$Ra &1.0    &  1643 & 10 &20\\
$^{226}$Ra &1.0    &  2465 & 20 &20\\
$^{226}$Ra &1.0    &  2876 & 30 &20\\
$^{226}$Ra &1.0    &  1709 & 10 &30\\

\end{tabular}
\end{ruledtabular}
\end{table}

\begin{figure}
\includegraphics[scale=0.4]{ac225_th_raf.pdf}
\caption{Production of $^{225}$Ac and its $\alpha-emitter$ decay products after different irradiation time using p(30MeV) + $^{232}$Th and  p(20MeV) + $^{226}$Ra with 1$\mu$A current} \label{ac225thra}
\end{figure}
Other reaction channel with $^{226}$Ra as target material which gives rise to $^{225}$Ac at rather low energy is as follows
\begin{equation}
 p + ^{226}Ra \Rightarrow 2n + ^{225}Ac  (\Delta Q = -6.823 MeV) \label{eqra229}
\end{equation}
The production cross-sections/excitation function are compared with the experimental data \cite{Apostolidis05} for this reaction as given in Fig.\ref{pracrs}. The area under peak is in good agreement with the experimental data with slight shift in the peak position. The activity (MBq/$\mu$A) of $^{225}$Ac is compared in Table \ref{tab:keffur2} for 1mm thick $^{232}$Th and $^{226}$Ra targets at different beam energies and irradiation times. It is clear from Table \ref{tab:keffur2} that the $^{226}$Ra target can give much higher activity compared to $^{232}$Th target and it is also much cleaner from co-produced radio isotopes. The Activity of the four $\alpha$-emitting isotopes is compared as shown in Fig.\ref{ac225thra} where the combined activity may meet the demand of the world community.

\section{\label{sec:level4} Conclusion}
The cross-section of different channel reactions p+$^{232}$Th systems has been calculated with MONC code and compared with experimental data and the results are in good agreement. Further, production of $^{225}$Ac is analysed at different proton energies for $^{232}$Th target material for full beam dump and 1mm thick targets. There are many challenging tasks like removal of other Actinium isotopes and others which may be difficult to separate. The production of $^{225}$Ac activity is very high for $^{226}$Ra target and seems very promising from practical and economical use, whereas availability and handling of Radium-226 target might be a challenge. The produced activity of $^{225}$Ac in a week of irradiation through $^{226}$Ra target may be equal to present total annual production by milking $^{229}$Th. Thorium yields smaller $^{225}$Ac activity at low proton energies ($\sim$30MeV) but one can be benefited from higher current, stable proton accelerators.  Proton energy of 100MeV or above with hundreds of $\mu$A current can produce reasonable $^{225}$Ac activity for practical use. The contamination of other co-produced radio-isotopes is much less at low proton energies hence low energy high current proton accelerators might also be a viable alternative to generate Actinium-225 radio isotope using $^{232}$Th target.

\begin{acknowledgments}
The authors are immensely thankful to Dr. A. K. Mohanty (Director, BARC) to support this work.
\end{acknowledgments}


\subsubsection{Dealing with instances which have more than one most-specific types}\label{multiInherit}

In this work, we assumed that each individual has exactly  one most-specific type. According to the W3C recommendation document on OWL 2, this is a common assumption in many semantic web applications, since by assuming otherwise ``many potentially useful consequences can get lost"~\cite{owl2pri}. However, we acknowledge that a KMGT needs to support mapping generation for such KBs~\cite{gh2019} since
large KBs in particular may violate this assumption.  To extend our approach, our definition of semantic association must be extended to include $\texttt{rdfs:subClassOf}^\wedge$ paths.

The reason for this assumption was that if we didn't assume that the most-specific types are disjoint, in our discovery phase we had to also follow $\texttt{rdfs:subClassOf}^\wedge$, since this new assumption implies that the relatedness of aligned concepts are no longer just expressed explicitly through data-level object properties of the KB (data-level to indicate that we are not talking about schema level object properties such as rdfs ones). To give an example, suppose that in a KB, instance $i$ is both an \texttt{Employee} and a \texttt{Student}, but there is no path between \texttt{Employee} and a \texttt{Student} (except of course a path in which you have to traverse to their most specific common parent from one and then from that parent traverse down to the other - note that such path exists in well formed KBs for any two concepts).  This means that \texttt{Employee} and a \texttt{Student} are associated because they are not disjoint (instance $i$ is in both). This association is not defined through explicit data-level object properties. If we want to show this type of association we have to also follow $\texttt{rdfs:subClassOf}^\wedge$ which will significantly increase the number of paths created, many of them unwanted.

Currently, to handle such cases, we go through a preparation phase, in which we create a dictionary in which each aligned concept is paired with a set of other aligned concepts which have intersection with it. This dictionary can be populated using instances of KBs and/or axioms such as \texttt{owl:disjointWith}. Note that when instances are used, one can define a threshold, expressing for instance, if there is at least 20\% intersection, assume these concepts are associated. Using this dictionary,  when we are creating associations, for each concept which is added to the association, we automatically add its paired concepts indicated in the hash map as well. Performance-wise, in real-world scenarios, this should not pose a problem, since although expanding with new concepts will increase the number of interpretations by increasing the number of object properties that needs to be traversed, we have already stressed test Kensho\xspace using very large settings. However, note that using this approach, we no longer guarantee to find all possible associations (unless of course a KB is annotated completely with \texttt{owl:disjointWith} axioms). In addition, if there is no cue in the KB that could be used to create the hash, this approach will not work at all.  It is worth mentioning that in future, it is interesting to see whether schema summarization methods such as~\cite{pham2015deriving} can help in combining concepts and pruning properties so that this adjustment is not necessary.

\subsubsection{Dealing with unnecessary blank nodes}\label{bn}
It is not hard to observe that the query in Figure~\ref{mapping} will produce unnecessary blank nodes. That is, even if none of the attributes of the blank node is bounded, since we always add a triple pattern that defines the type of the blank node, the blank node will be created. One approach to address this problem is to create and bound the blank nodes in the optional phrases of the where clause of the query (instead of defining the blank nodes in the construct clause of the query.) To demonstrate, assume that we have the following construct query:

\begin{linenumbers}
{\obeylines\obeyspaces\scriptsize
\texttt{\underline{construct}\{
~~~~-:trgt a trgt:Atype.
~~~~-:trgt trgt:AnAttribute ?trgtAttr\}
~~\underline{where}\{
~~~~?src a src:AnotherType.
~~~~OPTIONAL\{ ?src src:otherAttr ?srcAttr.\}
~~~~bind(?srcAttr as ?trgtAttr)\}
   \resetlinenumber
}}
 \end{linenumbers}
\medskip

In this query, even if \texttt{?srcAttr} (and as a result \texttt{?trgtAttr}) is not bounded, line 2 will cause a blank node of type \texttt{trgt:Atype} to be created. This is not desirable when creating mapping rules since we only need to create a blank node if an actual data needs to be translated. In other words, we only want to create the blank node for solutions in which the optional phrase in the source is matched. To achieve this, we need to create the blank node within the optional phrases' scope. For instance, we can use the following query instead of query above.

\begin{linenumbers}
{\obeylines\obeyspaces\scriptsize
\texttt{\underline{construct}\{
~~~~?trgt a trgt:Atype.
~~~~?trgt trgt:AnAttribute ?trgtAttr\}
~~\underline{where}\{
~~~~?src a src:AnotherType.
~~~~OPTIONAL\{ ?src src:otherAttr ?srcAttr.
~~~~~~~~~bind(BNODE("trgt") as ?trgt)\}
~~~~bind(?srcAttr as ?trgtAttr)\}
    \resetlinenumber
}} \end{linenumbers}
\medskip

Note that when using this strategy, a renaming function is defined as $\Re: T_{vars} \rightarrow S_{vars} \cup \{\epsilon\} \cup \beta$ where $\beta$ is a set of blank node IRIs.

\subsubsection{Dealing with large KBs}\label{scale}
When dealing with large general KBs, usually only a small fragment of an underlying KB is useful to the exchange problem. Trying to find associations among all elements of a very large KB can be a waste of resources. Thus we have adopted the knowledge fragment selection approach~\cite{hellmann2009learning}, to gather knowledge about the resources most important to the exchange problem at hand. Through this process, we can create a small fragment of the general KB and find associations only within this fragment. The goal of the knowledge fragment selection in general is to select relevant knowledge by traversing the knowledge graph starting from important resources up to a certain given recursion depth. This method is usually used in machine learning approaches that relies on a significant amount of reasoning. In these approaches usually a set of individuals is given as positive / negative examples, and thus the fragmentation algorithm starts from those given instances and explore the neighbours of those instances up to a given recursion depth.

In our problem, the starting point of the algorithm is a set of aligned elements of the KB. If a concept is reachable from a node within a certain recursion depth, we assume that all of the concept's attributes (but not its object properties) and their values are reachable within that range. If an object property node is reachable within a certain recursion depth, we assume that both its subject and object are reachable within that depth (see Figure~\ref{fig:expansionStep}). Note that the statements which aim to identify same concepts or properties (i.e. \texttt{owl:equivalentClass, owl:equivalentProperty}) are not adding to the recursion depth. Obviously the recursion depth can affect the quality of the generated mappings.

This is a preliminary solution. We plan to investigate whether
sophisticated methods such as modularization ~\cite{grau2008modular,konev2013model,stuckenschmidt2009modular,Ghazvinian:2011:MMU:1999676.1999684,Grau:2007:JRA:1242572.1242669} or partitioning~\cite{stuckenschmidt2004structure,grau2005automatic,Seidenberg:2006:WOS:1135777.1135785} can help in dealing with knowledge translation between large KBs.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{expansion.png}
\caption{\label{fig:expansionStep} The solid inner border represents the graph that is produce by expanding the corresponded nodes with recursion depth 1. The solid outer border represents the recursion depth 2. The darker section within the solid borders represents nodes which are not in the recursion depth i, but added to this depth since they are attributes of some nodes in this recursion depth or the object of the object property in this depth.}
\end{figure}
\subsection{Benchmark Evaluation}\label{benchmark}
STBenchmark~\cite{alexe2008stbenchmark} introduced the use of (micro) scenarios for comparing data exchange systems that use a structured or semi-structured model.  This idea was generalized by
the meta-data generator iBench~\cite{arocena2015ibench} that permits the efficient creation of benchmarks with large and complex schemas and data exchange scenarios.
DTSBenchmark~\cite{rivero2011benchmarking}
provides a set of scenarios where the source and target are both KBs. These scenarios were later refined in LODIB (linked open data integration benchmark)~\cite{rivero2012benchmarking}
which is mainly designed to benchmark the expressive power of mapping languages. Both Mosto and Kensho\xspace can automatically generate the desirable mapping rules for all the scenarios proposed in DTSBenchmark. In addition, it is reported that queries generated by Mosto can support the expression of all fifteen LODIB scenarios except for three (the ones which need conditional clauses or aggregation queries)~\cite{rivero2012benchmarking}. Queries generated by Kensho\xspace have the same expressive power.
Kensho\xspace, like Mosto, cannot automatically learn the relationship between values (e.g., when a value must be transformed using function \texttt{usDollarsToEuros}), and thus it cannot automatically generate the mapping rules for the LODIB scenarios that require these types of transformations

Additional scenarios have recently been identified that need to be supported by KMGTs~\cite{gh2019}.  Two of these scenarios are inspired by value invention in relational data exchange.  A third involves handling source KBs that are incomplete.  A fourth involves mapping creation even when the set of given correspondences are incomplete (a very common case in practice).  Finally, a fifth scenario involves mappings that use cyclic property paths.  Kensho\xspace can handle all five scenarios while the previous approaches (Mosto and Qin et al.) cannot.
It is important to note that since the associations that existing KMGTs create are a subset of what Kensho creates, and since their mapping language is not more expressive than Kensho's, there would be no scenario in which these KMGTs can create a mapping which Kensho cannot.

\subsection{Knowledge Translation Usecases}\label{usecase}

\input{tblSettingComparison.tex}

We now investigate the effectiveness of
mapping generation and ranking strategies implemented in Kensho\xspace using several scenarios that
showcase some of the important applications of KB translation.
Note that it is important to evaluate Kensho on real scenarios because all mappings which are created by our algorithm are valid interpretations of the set of correspondences, however, depending on the context, some mappings may be more desirable than others.
In all settings presented,
an expert identified
the desired (gold) mapping rule in the selected skeleton, henceforth called $\Re_{gold}$.
For each scenario (described below), in
Table~\ref{comp},
column {baseline} reports the number of mappings which are {baseline} valid, column {c2a} reports the number of mappings which are {baseline} and \emph{c2a} valid, column {r2r} reports the number of mappings which are {baseline} and \emph{r2r} valid , and column Kensho\xspace shows number of mappings that adhere to all of our validity constraints.
Table~\ref{comp} also shows the effect of our ranking methods in facilitating the selection of the best set of mappings.
For the different ranking strategies, we report on
the rank of $\Re_{gold}$ in the Kensho\xspace rankings, and since our rankings can have ties, we report on the number of other mappings ranked better than $\Re_{gold}$, then the number of mappings ranked equal to $\Re_{gold}$ (cols.~9-12).
For example, 2-1-0 means $\Re_{gold}$ was ranked second, with only one other mapping ranked ahead of $\Re_{gold}$ and with no ties.
The last column of Table~\ref{comp} reports the similarity between the two KBs (informally, the number of resources that model the same real world entities).

\subsubsection{Populating a KB using Open Data}\label{patent}

We believe the most important application of Kensho is populating an existing domain-specific ontology using other currently available structured data sources where the data source does not have to be a KB as long as it can be automatically converted to one.
Expertise finding is one area for which having a domain-specific KB can be very beneficial~\cite{hansen2004build,paquette2007ontology}.
For this reason, there are carefully designed ontologies in the literature that model expertise for competency management.
In this setting, for our target KB, we use
one of these ontologies~\cite{fazel2012ontology} and augment it with
two more concepts, \texttt{Employee} and \texttt{Organization}, to be able to
model the skills of employees in various companies. Our goal in this scenario (Row 1 of Table~\ref{comp}) is to generate mapping rules that can be used to populate this KB using open data published by the US Patent and Trademark Office (USPTO).
To use the USPTO corpus as our source KB, we started with a subset of the USPTO's patent XML corpus~\cite{pat}
and automatically
created a linked data corpus from it
using Xcurator~\cite{yeganeh2011linking} and further enriched it using Vizcurator~\cite{GhadiriBashardoost:2015:VVT:2740908.2742845}.
The original set of correspondences was provided by a domain expert and then was verified by the crowd using
the protocol proposed by Sarasua et al.~\cite{sarasua2012crowdmap}.

Our two KBs mainly model different domains (one models skills in an organization and the other models patent applications), so the similarity between these two KB
is low with only 2.6\% of the concepts and properties modeling the same information (last column of Table~\ref{comp}).
Additionally, there are two correspondences between concepts and only one between attributes (col.~4).
Mosto and Qin et al.~\cite{qin2007discovering} cannot find the gold mapping which connects the associated concepts and
attributes through properties with no correspondences.
Kensho\xspace produces two possible  mappings
including the gold mapping.

One side benefit of our approach is that the results can be used to enrich the
alignment. For instance, in this scenario $\Re_{gold}$ suggests that a
Rel2Rel correspondence may exists between the source \texttt{Patent - Inventor} path and the target \texttt{hasSkill - Skills} path.

\subsubsection{Migrating Data between KBs}\label{migration}
This
example (Row 2 in Table~\ref{comp}) is
from Mosto~\cite{rivero2013exchanging}, the source is a portion of DBpedia version 3.2 and the target is the similar portion of DBpedia version 3.6.
In order to generate the mapping rules in this scenario, Mosto
requires the correspondences and also
a user-provided
 axioms called \texttt{mosto:strongRange}.
 Note that Kensho\xspace does not require users to specify axioms such as these to guide the algorithm.
In Mosto, if two source concepts ($s_1$ and $s_2$) have correspondences to two target concepts ($t_1$ and $t_2$) then these
concepts will only be included in the same mapping if both the source and the target concepts are in a subclass relation, or if they are the domain and range of an \emph{aligned} property, or if a data engineer has manually added a \texttt{mosto:strongRange}
or \texttt{mosto:strongDomain} relation between them.
In this scenario, without the annotation, Mosto would exchange the \texttt{Actor} and \texttt{AcademyAward} data in DBpedia, but not the relationship between these two concepts (representing about 850 facts indicating who won which award).

In this scenario,
Kensho\xspace generates four mappings.  If we do not use our r2r strategy, then we generate seven mappings.
(including some that are inconsistent with the Rel2Rel correspondences).  The four mappings that Kensho\xspace produces include $\Re_{gold}$ and another three that are less complete (containing some existential target variables).  Our {\bf \mbox{Coverage}\xspace} ranking strategy
correctly ranks the gold mapping before these more incomplete mappings.

\subsubsection{Enriching the Result of Ontology Alignment}\label{alignment}
In this
scenario (Row 3),
we highlight
the fact that
Kensho\xspace can enrich the rules produced by the current state-of-the-art alignment tools. Note that while alignment tools generate correspondences, Kensho\xspace enriches these correspondences and produces \emph{executable queries }
by interpreting the
correspondences collectively.
Previous to this work, KMGTs assumed that the set of property correspondences are complete. Thus, if there is no correspondence
to or from an object property, the KMGT did not
automatically consider any path that included that property.
One of the main advantages of Kensho\xspace
is that it
considers such properties in mapping generation.
To show the benefit of this approach,
in this experiment, we have used two KBs from the OAEI (Ontology Alignment Evaluation Initiative) campaign and the correspondences between them which were produced by AML (Agreement Maker Light) -- one of the best performers in the 2018 matching challenge~\cite{faria2018results}.
The KBs we have used, \emph{confTool} and \emph{Sigkdd}, are from the OntoFarm dataset~\cite{zamazal2017ten}
of the {\it Conference} track of the OAEI.

In this scenario, Kensho\xspace produces 26 mappings (including the gold mapping).
These two KBs are not very similar, so our structural rankings are not helpful.  For example, our {\bf \mbox{Path}\xspace} ranking ranked all 26 mappings equally. Our
{\bf Consistency}
ranking did better with only
eighteen mappings ranked equal or higher than the gold mapping. Our results suggest some interesting possible correspondences between two KBs which are not provided in the results of AML, for instance, inverse property correspondences such as:

$\texttt{sigkdd:submit}^\wedge \leadsto_{r2r}
\texttt{conftool:writtenBy}$\\
In this scenario, the number of
given property correspondences
is very low. As a result, existing KMGTs
do not create the gold mapping.

\subsubsection{Translating KBs with Cycles}\label{synthSecen}
In this scenario (Row 4),
we show that unlike existing KMGTs,
Kensho\xspace can handle cycles, a situation that occurs in many existing KBs such as those created from social networks. Cycles define associations between resources of the same type such that multiple resources in the source can be mapped into multiple resources in the target, a situation resulting in a large number of possible mappings. This scenario showcases that our mapping generation and ranking strategies are especially useful in cases where the number of possible interpretations becomes very large due to the existence of cyclic paths.

This setting (depicted in Figure~\ref{mainex}) was created
from the example proposed by Qin et al.~\cite{qin2007discovering} which was developed using Carnegie Mellon's \emph{Person \& Employee Ontology} and the University of Maryland's \emph{People Ontology}. To add complexity, we incorporated a cycle by adding an additional object property, \texttt{src:related}, which has \texttt{src:Employee} as its
domain and range.
This caused a large number of mappings to be created. However, our mapping generation validity strategies reduce the number of mappings to a few hundred (which is still unmanageable for a human), but the {\bf Consistency} ranking ranks the gold mapping first, in a tie with only 15 other mappings (a much more reasonable task for an engineer to understand).  Together,  our Path and Consistency ranking reduces the ties to only three.

\subsection{Performance Evaluation}\label{synth}
Mapping generation tools are usually evaluated using metadata generators~\cite{alexe2008stbenchmark,arocena2015ibench}.
They
allow the data engineer to systematically vary specific parameters that influence the difficulty of relational mapping creation or data exchange.
In a similar vein, MostoBM~\cite{rivero2012benchmarking2}
identifies
three schema-level
parameters (namely, {\bf $L$ or depth} of the class relationships, {\bf $C$ or breadth}
of the class relationships, and {\bf $D$}, the number of attributes) that can affect the complexity of the task of KB mapping generation. To investigate the effect of breadth,
we followed the MostoBM approach and
generated ten settings for one of
the MostoBM exchange scenarios - called \emph{sink properties}. More specifically, we fixed $D$ = 10,
$L$ = 1, and vary the value of $C$ between one and ten. We call this group of settings that vary $C$, $E_1$.
For the first setting of $E_1$, \texttt{\{L=1, C=1, D=10\}}, the source contains two concepts, $\texttt{A}_0$ and its child $\texttt{A}_1$, and $\texttt{A}_0$ is the domain of ten attributes \{$\texttt{d}_1$,...,$\texttt{d}_{10}$\}. The target has the same structure, except that the domain of $\texttt{d}_1$ is $\texttt{A}_1$. Resources with the same labels correspond to each other (e.g., $\texttt{src:A}_0 \leadsto_{c2c} \texttt{trgt:A}_0$). For the next setting in $E_1$, \texttt{\{L=1, C=2, D=10\}}, $\texttt{A}_0$ has one more child, $\texttt{A}_2$, in both the source and target and the domain of $\texttt{d}_2$ in the $target$ is $\texttt{A}_2$.
We repeated the same procedure for investigating the effect of depth and created a group of ten depth settings, $E_2$
by keeping $C$ constant and varying $L$. The difference here is that the new concept for each consecutive setting will be nested inside the most specific type (as opposed to being added to the root). For instance,
when $L=2$
, $\texttt{A}_2$ is a child of $\texttt{A}_1$ and $\texttt{A}_1$ is a child of $\texttt{A}_0$. In this section, we report on the number of $all$ mappings created (as opposed to the number of mappings created for a specific skeleton as was done in the previous section). Note that changing $D$ while fixing $L$ and $C$ will not change the number of mappings created and so we did not include such settings in our evaluation.

Figure~\ref{DvsB}
shows
the number of mappings generated by Kensho\xspace in each of the settings.
Note that Mosto does not create all possible mappings and thus in our evaluation we could not compare it with  Kensho\xspace.
\input{plotBvsD2.tex}
As the breadth ($C$) of the KB increases, the number of mappings generated
also increases linearly and Kensho\xspace's performance also scales linearly, remaining under
a second
for a
setting with breadth of 8.
In contrast, increasing the depth ($L$) has an exponential effect on the number of mappings generated. This is expected since increasing the depth actually adds a layer of nesting.  Kensho\xspace's performance passes one second at a depth of five which corresponds to the generation of 21 mappings.

Settings in $E_1$ and $E_2$ include relatively small KBs. To push Kensho\xspace further, we  created
a set of 10 settings, $E_3$, for the same scenario using parameters \texttt{\{L=x, C=2, D=10\}}, where $1 \leq \texttt{x} \leq 10$. The taxonomy created using these parameters contains $2^\texttt{n}$ concepts at depth \texttt{n} from the root. For instance, when \texttt{L = 10}, both the source and target contain $2^{10}$ most specific types (in total each contains more than 2000 concepts - more than three times greater than the number of concepts in DBpedia).
Figure~\ref{DvsB3} left, shows the number of mappings created in
$E_3$ vs.~$E_1$ and $E_2$, note the scale change on the Y-axis.
When \texttt{L = 10}, Kensho\xspace creates more than 2000 mappings and the creation time is almost three hours. One factor that affects the number of mappings is the number of correspondences. In
$E_3$, the number of correspondences grows as the depth $L$ increases.
To explain this effect, we have also plotted \textbf{$\Delta$} as the difference between the number  of mapping rules generated for each setting and the number of correspondences. The right plot in Figure~\ref{DvsB3} shows the result. Obviously, the difference \textbf{$\Delta$} is constant for the
$E_1$ (breadth) settings (all have $L=2$). However it is important to note that for
$E_2$ and $E_3$, \textbf{$\Delta$} is exactly the same for each value of the depth $L$.
This is because the number of possible mappings becomes greater than number of correspondences if there are various ways for interpreting correspondences. As we have seen, correspondences can be interpreted in various ways only if the resources can be associated with each other in multiple ways.
In this scenario, multiple interpretations are the result of various ways that one can interpret Concept2Concept correspondences in conjunction with Attr2Attr correspondences. Thus increasing only the number of concepts and Concept2Concept correspondences (as we are doing here) will not result in multiple interpretations of the correspondences.
\input{plotBvsD3.tex}

Nonetheless, Kensho\xspace is sensitive to the number of possible interpretations of a correspondence, so we created a final set of 20 settings ($E_4$) to understand how far we can push Kensho\xspace on this dimension.
We have used the setting represented in Figure~\ref{mainex}, our running example which already includes multiple interpretations, as our least complex setting (Setting 1).  To create the rest of the settings, we injected
elements into the source, such that in each setting, the number of possible assignments for each target variable is increased by one. For instance, Figure~\ref{mapping} shows that there are three source variables of type \texttt{country} that can be assigned to variable \texttt{tC1}.  The next setting contains four possibilities for this variable, and so on. Figure~\ref{stress} represents the result of our various mapping strategies.
The number of mappings generated grows exponentially; however, this figure demonstrates that Kensho\xspace is able to reduce this search space by only generating valid mappings.
In our largest setting, the source KB contains nearly 120 object properties and 5 concepts leading to over 500K interpretations (we have kept the target fixed in this experiment). Only one fifth of these properties corresponds to a property in the target. Note that real world KBs usually contain many fewer object properties among concepts. Kensho\xspace created 4579 possible mappings for this setting. For the biggest skeleton in this setting, Kensho\xspace ranked 42 mappings as rank one. This highlights one of the weaknesses of Kensho\xspace. As the number of \emph{property paths} among corresponding concepts or attributes grows, the number of mappings generated by Kensho\xspace will grow exponentially and this makes the process of selecting the best set of mappings overwhelming. However, note that in the previous experiment we have shown that Kensho\xspace is not as sensitive to the increasing number of concepts, and most large real world KBs such as medical KBs
tend not to have a large number of properties for all concepts as we do in this case (which included an average of 24 properties for every concept in this experiment).

\input{plotStressTest.tex}

In summary, we performed experiments on synthetic scenarios (inspired by existing KB exchange benchmarks~\cite{rivero2012benchmarking2}) to show how the performance of our mapping generation algorithm is affected by increasing
complexity of the scenarios.
Our results show that Kensho\xspace scales very well as the KB size increases, with the largest bottleneck being the number of possible interpretations of a correspondence.

\subsection{Case Study} \label{casestudy}\label{sec:casestudy}

In
this study,
we make use of a scenario from OntoMerge~\cite{dou2005ontology}.
It includes
their
Yale bibliography ontology as our source, and their CMU
bibliography ontology as our target.
We also use
their manually curated
mapping rules
as our gold standard.
We  manually identified the set of correspondences between these two ontologies (from the gold standard mapping rules).
These ontologies are very simple, the source contains only 6 classes and no object properties, the target contains 9 classes and 3 object properties. In Phase I of our experiment, we
asked two collaborators, \emph{c1} and \emph{c2}
(both
experienced
in SPARQL) to create  mapping rules by manually writing  SPARQL queries.
We gave each collaborator 20 minutes to familiarize themselves with the ontologies and one hour to write the mapping rules.
The queries created by \emph{c1} were able to transfer 78$\%$ of the facts
while queries created by \emph{c2} transferred 61$\%$ of the facts. In
Phase II, we used a ranked
list of examples created by Kensho
and gave
\emph{c1} and \emph{c2} each 30 minutes to go through
them and choose desirable examples. Note that examples were created based on query solutions obtained by running queries using query pattern of each renaming.
Both \emph{c1} and \emph{c2}
identified all (and only) the desirable examples.
In
Phase III we gave them 20 minutes to
update
the queries they generated in Phase I,
based on what they
learned from the examples. Collaborator \emph{c2}
was able to write all the queries correctly while \emph{c1} was able to make changes
such that 92\% of the facts translated correctly.
It is possible that \emph{c1} and \emph{c2} were able to more easily identify examples from Kensho\xspace's ranked list because in Phase I they had each tried to generate their own mapping rules. To account for this,
we
asked a third collaborator \emph{c3}
(also with SPARQL experience)
to first
select desirable
examples from Kensho\xspace's automatically generated list. Similar to \emph{c1} and \emph{c2}, \emph{c3} was given 30 minutes and
was also able to pick the desirable (and only desirable) examples. We then
gave \emph{c3} one hour to write
queries that can transfer data from the source to the target.
The resulting queries
were able to transfer only 78$\%$ of the facts.

In summary, all participants were able to correctly
identify the desirable examples (including the
correct optional combinations) which highlights the fact that it is more intuitive for humans to
select from examples
than
to write queries manually.

\section{Acknowledgments}
This research was funded in part by an NSERC Strategic
Partnership Grant.\\\\

\bibliographystyle{abbrv}

\subsection{Correspondences}\label{sec:prelim}

We distinguish between two important types of properties in a KB: 1)  a \emph{datatype property} or \emph{attribute} which represents a relationship between an IRI and a Literal
and 2) an \emph{object property}
which expresses a relationship between two IRIs.
A property path is a
list of properties in
an RDF graph between resources~\cite{sparql2013}.
An
attribute or an object property is a property path of length one.
Property paths are either data property paths (a path between an IRI and a Literal) or object property paths (a path between two IRIs).
Property paths can be expressed using a regular expression grammar.
We use the
grammar from W3C~\cite{sparql2013} to represent them.

In this work, we
define three  types of correspondences. First, a {\bf Concept2Concept} correspondence
associates
a concept $\texttt{s}$ in the source to a concept $\texttt{t}$ in the target, represented as $\texttt{s} \leadsto_{c2c} \texttt{t}$.
In Figure~\ref{mainex}, $C3$ is a Concept2Concept correspondence between the source concept \texttt{Person} and the target concept \texttt{Person}.
Second, a {\bf Rel2Rel} correspondence  associates an object property path \texttt{P} in the source to an object property path \texttt{R} in the target, represented as $\texttt{P}_{(\texttt{s}_1, \texttt{s}_2)} \leadsto_{r2r} \texttt{R}_{(\texttt{t}_1,\texttt{t}_2)}$ where \texttt{$\texttt{s}_1$} and \texttt{$\texttt{s}_2$} are connected by \texttt{P}  and  \texttt{$\texttt{t}_1$} and \texttt{$\texttt{t}_2$} are connected by \texttt{R}.
In Figure~\ref{mainex}, $C4$ is a Rel2Rel correspondence that associates the source object property \texttt{employer} with the target object property \texttt{works\_for}.
An {\bf Attr2Attr} correspondence associates a data property path
in the source with a data property path
in the target, represented as $\texttt{a}_{{\texttt{s}}} \leadsto_{a2a} \texttt{b}_{{\texttt{t}}}$, where \texttt{$\texttt{s}$} and \texttt{$\texttt{t}$} are concepts
that are connected by a data path to attribute values of $\texttt{a}$ and $\texttt{b}$, respectively.
In Figure~\ref{mainex}, $C2$ is an Attr2Attr correspondence that associates the source attribute \texttt{address} with the target attribute \texttt{address\_line}.
Correspondences can represent various relationships.
In this work, we use correspondences that express subset-or-equal relations since correspondences produced by automated tools are often of this type ~\cite{Euzenat:2013:OM:2560129}. Following the terminology of Euzenat and Shvaiko~\cite{Euzenat:2013:OM:2560129}, we call a \textbf{set} of correspondences an \emph{alignment}.

We say a concept is an \emph{aligned concept} if it either directly participates in a Concept2Concept correspondence or if it participates in  an Attr2Attr correspondence (meaning for $\texttt{a}_{{\texttt{s}}} \leadsto_{a2a} \texttt{b}_{{\texttt{t}}}$, it is the concept \texttt{s} or some concept along the path from \texttt{s} to the attribute \texttt{a}).   Note that we treat Rel2Rel correspondences differently, and use them to refine how concepts are mapped collectively using a notion we call {\bf r2r validity} defined in the next section.
Finally, in general we call any KB resource that participates in a correspondence an \emph{aligned element}. It is worth mentioning that Mosto also uses another type of correspondence that matches an attribute value to an instance of a concept. In these situations, we create an Atr2Atr that matches the attribute in the source to the \texttt{rdfs:label} attribute of the concept in the target.
Note that this type of correspondence is different from metadata-data correspondences~\cite{hernandez2008data,Mil98} which Kensho\xspace does not support.

\section{Introduction}\label{sec:introduction}
\input{introClioBased.tex}
\section{Methodology}
\input{Method.tex}

\subsection{Semantic Association Discovery}\label{SAD}\label{sec:semanticassociation}
\input{SemanticAssociationDisc.tex}

\subsection{From Correspondence to Mapping}
\label{sec:interp}
\input{interprtFinal.tex}

\subsection{Mapping Generation}
\label{sec:mapgen}
\input{CQGen.tex}

\subsection{Discussion}\label{sec:discussion}
\input{DiscussionFinal.tex}

\input{Ranking.tex}

\section{Evaluation}\label{eval}
\input{Eval.tex}

\section{Related Work}\label{sec:rw}
\input{relatedWorkRevision.tex}

\section{Conclusion}\label{conclusion}
\input{conclusion.tex}

\section{Mapping Ranking} \label{sec:ranking}

\newcommand{\mbox{Path}\xspace}{\mbox{Path}\xspace}
\newcommand{\mbox{Consistency}\xspace}{\mbox{Consistency}\xspace}
\newcommand{\mbox{Coverage}\xspace}{\mbox{Coverage}\xspace}

For a given skeleton, the set of possible renamings, even valid renamings, each of which creates a different mapping,
might be large due to the diverse ways in which knowledge can be represented in KBs.
Thus, we introduce a set of heuristics that help rank
renamings of each skeleton.
A data engineer can then browse through the ranked set of mappings (or through a set of examples created using mapping queries)
and choose the most desirable set.

Many cues in the KB can be used to rank our mappings. For instance, Maponto~\cite{an2006discovering}, which produces mapping rules in settings that involve relational models and KBs (see Section~\ref{sec:rw} for details) suggests that reach axioms such as functionality or cardinality can be used to select  better mappings. However, these reach axioms are usually not available~\cite{buhmann2012universal}. In addition, instances of source and target KBs can be used to select  mappings which exchange more facts
that are already present in the target~\cite{Qian:2012:SSM:2213836.2213846}. However, one of the most important applications of this work is to populate a target, and thus it is not reasonable to assume that target is already populated with a large
amount
of the source's data. Furthermore,
in the presence of set of  positive or negative facts,  rule mining approaches (s.a. ~\cite{galarraga2015fast,meng2015discovering,ortona2018robust}) can help identify important paths (or rules) that best fit a set of given examples.
However, we cannot always  assume that such examples exists and creating a good set of examples is itself an interesting research challenge.
In this work, we present three complementary heuristics that do not require the information mentioned above, but that can be used in concert with other information when available.
Our first two heuristics are structural, giving higher ranks to mappings that are more consistent with the structure of the KBs, the third is based on the coverage of the mappings, giving higher ranks to renamings that cover more target elements.

First, we rank mappings based on the degree to which source and target {\bf paths} are collectively mapped.
Recall that an association path does not go through any other aligned concept.
If a mapping maps two target concepts between which there is an association path, to two source concepts that have no association path between them, we
rank this mapping lower than a mapping that uses
two source concepts which are connected with an association path.
\TRep{
\begin{example}
In Figure~\ref{fig:saEmp}, \texttt{sC3} represents a \texttt{Country} (the country in which an employee was born) and
some mappings will map it to \texttt{tC1}.
However, such mappings are less desirable than
mappings that map either \texttt{sC1} or \texttt{sC2} to \texttt{tC1}.
To see why, note that \texttt{sC3} represents countries which are directly related to employees.
While, in the
target KB there is no such direct association between employees and countries.
On the other hand,
\texttt{sC1} or \texttt{sC2} represent \texttt{Countries} which are related to \texttt{Employee} via \texttt{src:Organization} (which is mapped to \texttt{trgt:Organization}), and there are
association paths between (\texttt{trgt:Employee},\texttt{trgt:Organization}) and (\texttt{trgt:Organization},\texttt{trgt:Country}) in the target. In other words, the target KB
models countries as locations of organizations
so mappings that use source countries that are also locations of organizations are likely to be better models of the domain.
\qed
\end{example}
Our {\bf \mbox{Path}\xspace Priority} ranking is based on this intuition.}
\theoremstyle{definition}
\begin{definition} {\bf (\mbox{Path}\xspace Priority)}
Assume $s_0 \leadsto_{c2c} t_0$. For any association path $p$ with root $s_0$, the cost of adding $p$ to $s_0$  with respect to the $target$ KB, $Cost(s_0,p)$, is 1 if there exists no association path between $t_0$ and $t_1$, where $s_1 \leadsto_{c2c} t_1$,
and $s_1$ is the tail of $p$, and is 0 otherwise.

The cost of adding a set of ordered association paths, $ \{p_1,...p_k\}$, to $s_0$, where $k > 2$, and $s_0$ is the root of $p_1$, $s_i$ is the tail of $p_i$ and the root of $p_{i+1}$,
with respect to the $target$ KB, $Cost(s_0,p_k)$, is:
\[ Cost(s_0,p_{1}) + \sum_{i=1}^{k-1} Cost(s_{i}, p_{i+1})\]

\noindent For node $n$ in $\sa{u_0}$, where $concept(n)$ is an aligned concept, a set of ordered association paths, $P$, can be defined such that $P$ includes association paths that are used to connect $n_0$ to $n$, in that order, where $n_0$ is the root of the association tree. The \mbox{Path}\xspace score of variable $v$ of node $n$ is the cost of adding $P$ to $u_0$, and is  $score(v, \sa{u_0})$.
For Skeleton $\langle S,T \rangle$, The \mbox{Path}\xspace cost of $\Re$ is:
\[Path_{cost}(\Re,\langle S,T \rangle) = \sum_{v} score(v,S)\]
where $v$ ranges over all the variables of nodes of aligned concepts in $S$.
We say $\Re_{i}$ has higher \mbox{Path}\xspace priority than $\Re_{j}$
if it has a lower cost. \qed
\end{definition}

\begin{example}\label{shortestPath}
In Figure~\ref{fig:saEmp}, the $score(\texttt{sC3},\sa{\texttt{src:Employee}})$ is 1, since there is no association path between \texttt{trgt:Employee} and \texttt{trgt:Country} in the \textbf{target} KB, while $score(\texttt{sC1},\sa{\texttt{src:Employee}})$ or $score(\texttt{sC2},\sa{\texttt{src:Employee}})$ are 0. Note that sometimes it is tempting to pick the shortest path between two concepts as the best property path that describes the relationship between them
(e.g., \texttt{src:born\_in} here), however this example shows that the shortest path is not always best. \qed
\end{example}

\TRep{
The \mbox{Path}\xspace heuristic
ranks higher mappings that faithfully map paths of aligned concepts.
 Of course, there are times where this heuristic
is incorrect.  For instance, assume that in the source KB of Figure~\ref{mainex}, instead of the attribute \texttt{src:address} we had an actual concept \texttt{src:Address} which was connected to \texttt{src:Organization} via \texttt{src:hasAddress} object property. Also, assume that $\texttt{src:Address} \leadsto_{c2c} \texttt{trgt:Address}$. Finally, assume that \texttt{src:Person} is connected to \texttt{src:Address} via \texttt{src:hasHomeAddress}. In this case, the renaming that picks the home address of a person as an organization's address will get higher priority. The reason is that, in the target, address is the property of a person and not the organization, and thus the address which directly describes a person in the source, \texttt{src:hasHomeAddress}, (and not the organization) will be picked.
}

Next, we consider semantic associations that include multiple subpaths containing identical concepts (like the two \texttt{Organization, Country} paths in our running example).  These paths will have identical \mbox{Path}\xspace scores.  Mappings that only use a single one of these multiple paths (rather than mixing concepts in two or more such identical paths) are generally better reflections of the domain.
\TRep{
\begin{example}\label{reachabilityP}
In Figure~\ref{fig:saEmp}, \texttt{sC1} and \texttt{sC2} both represent the source concept \texttt{Country}.
Assume there are renamings $\Re_y$ such that $\Re_y\texttt{(tO2)} = \texttt{sO2} $, and $\Re_y\texttt{(tC2)} = \texttt{sC1}$ and $\Re_z$ such that $\Re_z\texttt{(tO2)
}= \texttt{sO2}$, and $\Re_z\texttt{(tC2)} = \texttt{sC2}$.
It is not hard to see that $\Re_z$ is
almost certainly
more desirable. Intuitively,
it does not make sense to transfer the country of an employee's former \texttt{Organization} (\texttt{has\_worked\_for}) to target and associate it with the country of her current \texttt{employer}, or vice versa.  One would almost always want an organization to be translated with its own country.
Our {\bf \mbox{Consistency}\xspace Priority} aims to capture
this intuition.\qed
\end{example}
}

To define {\bf \mbox{Consistency}\xspace Priority}, we note that the variables in a semantic association (either $S$ or $T$) are organized in a tree starting at the variable for the root.  We say $v_j$ is reachable from $v_i$, if $v_j$
is a descendant of $v_i$ in this tree.\\
\theoremstyle{definition}
\begin{definition}{\bf (\mbox{Consistency}\xspace Priority)}
For skeleton
$\langle S,T \rangle$, set the \mbox{Consistency}\xspace cost of the renaming $\Re$, $Consistency_{cost}(\Re,\langle S,T \rangle)$, to zero.
For each pair of target variables $v_i$ and $v_j$ which both are bounded by some source variables in $\Re$:
\squishlist
\item
if $v_j$ is reachable from $v_i$ (in $T$),
and $\Re(v_j)$ is {\bf not} reachable from $\Re(v_i)$ (in $S$), then increase
$Consistency_{cost}(\Re,\langle S,T \rangle)$ by 1;
\item
if $v_j$ is {\bf not} reachable from $v_i$ (in $T$) and $\Re(v_j)$ {\bf is} reachable from $\Re(v_i)$ (in $S$), then increase
$Consistency_{cost}(\Re,\langle S,T \rangle)$ by 1;
\squishend
We say $\Re$ has higher priority if it has lower cost.
\qed
\end{definition}
\TRep{
\mbox{Consistency}\xspace priority might wrongly prioritize renaming functions. One obvious case is when two mapped concepts which are associated using a property path $p$ in the source are associated with $p^{\wedge}$ in the target. Kensho\xspace
takes this into account when the mapping is from a property to a reverse property.}

In addition to the two structural heuristics, we also use
{\bf \mbox{Coverage}\xspace Priority} which prioritizes renamings that contain translations for (or cover) more target elements.
\theoremstyle{definition}
\begin{definition}{\bf (\mbox{Coverage}\xspace Priority)}
For a skeleton $\langle S,T \rangle$, \mbox{Coverage}\xspace cost of $\Re$, $Coverage_{cost}(\Re,\langle S,T \rangle)$, is the number of variable in T that are
mapped to $\epsilon$. We say $\Re$ has higher priority if it has lower cost.
\qed
\end{definition}