Major change

[u/philim/db2osl_thesis.git] / bootstrapping_iris.tex

\section{Generating unique IRIs for OBDA specification map fields}
\label{iris}
As explained in Section~\fullref{back_basic}, IRIs play a central role in
diverse topics related to ontology-based data access.
They provide the means to uniquely identify entities, which of course is
a necessity for data retrieval.
As also explained in Section~\ref{back_basic}, every URI is also a IRI, so
although Skjæveland et al. use the term ``URI'' in the introduction of
their approach of using OBDA specifications for ontology bootstrapping --
and that term is also used in Section~\ref{bootstrap_spec}, which describes
this approach -- in this section the general term ``IRI'' is used, marking
that the introduced concepts are valid for all types of IRIs.

When dealing with ontology bootstrapping using OBDA specifications, it is
important to differentiate between the three types of IRIs occurring
in this matter, which will be underlined by the following unambiguous naming:
\begin{itemize}
	\item \emph{Data IRIs} identify entities in the bootstrapped ontology
	\item \emph{OBDA IRIs} are used as values for the fields of
	OBDA specification entities
	\item \emph{OSL IRIs} identify components in serialized OBDA specifications,
	using the \oslboth{} introduced in Chapter~\ref{osl} for serialization
\end{itemize}

Skjæveland et al. do not define or assume a particular scheme for IRI generation
in their introduction of OBDA specifications \cite{eng}.
Instead, the IRI generation strategy is only adumbrated by giving examples
of entities having IRIs.
The examplified scheme was used for the implementation of the \myprog{} software
bootstrapping OBDA specifications from relational database schemata, which is
described in this thesis
(see Section~\fullref{program} and Section~\fullref{impl}).
The direct mapping approach for ontology bootstrapping described in
Section~\ref{dirm}, on the other hand, introduces a scheme for
IRI generation \cite{dirm}, but with this scheme, name clashes can occur,
as explained in Section~\ref{dirm_iris}.
The \oslboth{}, finally, defines a proper scheme for OSL IRIs,
as is explained in Section~TODO.

In the following, an enhanced scheme for the generation of OBDA IRIs
is proposed, which resembles the previously mentioned scheme used for
OSL IRIs and which also may serve as a blueprint for
other IRI generation strategies.

\subsection{Requirements for the IRI scheme}
\label{iris_req}
As explained in Section~\fullref{back_basic}, the main requirement on a IRI
generation scheme is uniqueness of the IRIs: no two entities must be possibly
assigned the same IRI, regardless of their kind, of how low the probability
of a name clash (IRI collision) is or of the conditions leading
to a name clash.
Additionally, IRI uniqueness shall be independent from the base IRIs,
thus a base IRI shall be arbitrarily selectable for each generation process
without introducing name clashes even with IRIs having other base IRIs.

As to OBDA specification entities, the following kinds of IRIs
have to be available, including IRI patterns:
\begin{itemize}
	\item Entity map OWL class IRIs
	\item Identifier map IRI patterns
	\item Attribute map OWL property IRIs
	\item Attribute map IRI patterns
	\item Relation map OWL property IRIs
	\item Subtype map (IRI) prefixes
	\item Subtype map (IRI) suffixes
	\item Subtype map OWL superclass IRIs
\end{itemize}

As Subtype map OWL superclass IRIs are IRIs of data entities
already existing in the target ontology by some means
(see Section~\fullref{bootstrap_spec_using}), they do not have to be
generated and thus are ignored in the following.
Exactly the same holds for Attribute map IRI patterns.
Furthermore, this approach creates Subtype map IRI prefixes already leading to
unique IRIs for Subtype map subclasses and so Subtype map IRI suffixes are
ignored in the following.
Since an IRI generation scheme cannot avoid collisions with existing IRIs
out of its outreach and these collisions can easily be prevented,
for example, by giving them another base IRI (see Setion~\fullref{back_basic}),
this case is excluded from the requirement that no two URIs must collide
under any circumstances.
However, the user shall be able to chose such externally generated IRIs
from an infinite set of IRIs, while being sure that no name clashes
will occur.

So compendious, the requirements on the IRI generation scheme are that
Entity map OWL class IRIs, Identifier map IRI patterns,
Attribute map OWL property IRIs, Relation map OWL property IRIs and
Subtype map IRI prefixes can be generated that, regardless of the
chosen base IRIs, don't clash among another, while leaving an
infinite set of predictable IRIs that don't clash with any of the
generated IRIs.

\subsection{Avoiding name clashes in the IRI scheme}
\label{iris_clashes}
Generating unique Entity map OWL class IRIs ignoring base IRIs is not much of
a problem, assuming database table names are distinct, which is guaranteed in a
common database system like SQL \cite{sql}.
Including the table name into an Entity map OWL class IRI is sufficient to
prevent it from colliding with other IRIs with the same base IRI.
However, when taking two different base IRIs into account that are used for
two IRIs created according to this scheme, things get more complicated.\\
Consider, for example, a database table named ``\code{Persons}'' and a
table named \\ ``\code{Persons\_\_TABLE\_\_Persons}''.
Generating an IRI according to the scheme
``<base:>\code{TABLE\_\_}   <table name>'' for each of these tables, using the
base IRI ``\code{TABLE\_\_Persons\_\_}'' for the first one and the
empty base IRI for the second one, both tables will get the IRI\\
``\code{TABLE\_\_Persons\_\_TABLE\_\_Persons}'', although
the table name was included into the IRI in both cases.
The problem is that the ``\code{TABLE\_\_}'' string occurring in the
table name cannot be discriminated from the ``\code{TABLE\_\_}'' string
added in the course of IRI generation or the ``\code{TABLE\_\_}'' string
occurring in the base IRI.
To solve the problem, a marker has to be included in the URI which definitely
indicates the beginning of the table name. In addition, this marker will
uniquely identify Entity map OWL class IRIs.
For both aims to be achieved, an escape symbol must be used, which makes
the marker unique at least outside the base IRI part, by escaping the marker
whenever it occurs in the table name.

Regarding Identifier map IRI patterns, the IRI resulting from the expansion of
the pattern will contain the column names of the primary key represented by
the respective Identifier map \cite{eng}.
Further on, the table name of the database table containing that primary
key has to be included in the IRI pattern, since
two distinct tables may have primary keys with equally named columns.
This will make the IRI pattern a unique Identifier map IRI pattern,
since a database table can be assumed to only have one primary key,
as is the case in common database systems like SQL \cite{sql}.
The fact that primary key values are unique for each dataset ensures that
unique Identifier map IRI patterns expand to unique IRIs.
Moreover, it has to be ensured, that IRIs resulting from the expansion of
Identifier map IRI patterns do not collide with IRIs of other kinds.\\
Taking arbitrary and particularly varying base IRIs into account,
a definite marker has to be included in the IRI pattern and other occurrences
of this marker in the IRI pattern have to be escaped. This uniquely
identifies Identifier map IRI patterns and unambiguously
distinguishes the table name from the rest of the IRI.

Concerning Attribute map OWL property IRIs, they will be unique among their
kind when they include the column name of the database column they
represent besides the table name of the table containing it,
since database table names can be assumed to be distinct and
column names can be assumed to be unique within a table, which is
guaranteed in a common database system like SQL \cite{sql}.
Furthermore, Attribute map OWL property IRIs have to be prevented from
colliding with IRIs of other kinds.\\
Taking arbitrary and particularly varying base IRIs into account,
definite markers have to be included in the IRI and other occurrences
of this marker in the IRI have to be escaped. This uniquely
identifies Attribute map OWL property IRIs and unambiguously
distinguishes the table name and the column name from the rest of the IRI
and from one another.

Regarding Relation map OWL property IRIs, including the table name and
the column names of both the foreign key represented by the Relation map
(or the containing table, respectively) and the referenced key (or its
containing table, respectively) in the IRI will make it a unique
Relation map OWL property IRI.
Note that including only the table name and the column names of the foreign
key (or its containing table, respectively) would not be sufficient, since
several distinct foreign keys covering exactly the same columns can exist
in a table (this is what the IRI generation scheme of the direct mapping
approach misses). The same applies of course for the referenced table and
its columns -- several foreign keys can reference them.
Moreover, these Regarding Relation map OWL property IRIs have to be
prevented from colliding with IRIs of other kinds.\\
Taking arbitrary and particularly varying base IRIs into account,
definite markers have to be included in the IRI pattern and other occurrences
of this marker in the IRI have to be escaped. This uniquely
identifies Relation map OWL property IRIs and in particular their parts
providing the table and column names.

Concerning Subtype map IRI prefixes, they must include the column name of
the database column containing the values to be declared belonging to
the subclass. Further on, since another database table could contain a
column of the same name, the IRI must include the table name of the
database table containing the column.
This will make Subtype map IRI prefixes unique among their kind.
Note that a Subtype map IRI prefix, similarly to a IRI pattern,
does not specify the final IRI but is subject to expansion.
This expansion can yield the same IRI for different data records, which,
however, is not considered a collision, since this behavior is
intentional -- every two data records having the same value in
the respective column, and only those, will get the same IRI.
Additionally, it has to be ensured, that IRIs resulting from such an
expansion do not collide with IRIs of other kinds.\\
Taking arbitrary and particularly varying base IRIs into account,
definite markers have to be included in the IRI pattern and other occurrences
of this marker in the IRI prefix have to be escaped. This uniquely
identifies Subtype map IRI prefixes and unambiguously
distinguishes the table name and the column name from the rest of the IRI
and from one another.

For an example that makes awkwardly -- or fraudulently -- chosen base
IRIs introduce name clashes, see the paragraph about Entity map
OWL class IRIs at the beginning of this section.

\subsection{The proposed IRI generation scheme}
\label{iris_scheme}
This section introduces an IRI generation scheme meeting the requirements
formulated in Section~\ref{iris_req}.

In this section, the following strings are subsumed under the term
\emph{marking strings}:\\
``\code{TABLE\_\_}'', ``\code{TBL\_\_}'', ``\code{PROP\_\_}'',
``\code{REF\_\_}'' and ``\code{SUBTYPE\_\_}''.\\
The string built by escaping (prefixing) all occurrences of marking strings or
`\textasciitilde' characters in a string $s$ with a `\textasciitilde'
character will be called the \emph{IRI-safe version} of $s$.

The IRI generation scheme is presented in Table~\ref{bootstrap_tab_iris}.
Here, \\ \emph{<base:>} refers to the base IRI to be used for
the generated IRI (see Section~\fullref{back_basic}),\\
\emph{<cl. tbl name>} refers to the table name of the database table
concerning (see Section~\ref{iris_clashes}) in its IRI-safe version,\\
\emph{<cl. name 1st pk col>} refers to the name of the first primary key
column concerning (see Section~\ref{iris_clashes}) in its IRI-safe version,\\
\emph{<\code{/}...>} refers to the continuation of the previous pattern
using the remaining primary key or foreign key columns,\\
\emph{<cl. col name>} refers to the name of the column in question
(see Section~\ref{iris_clashes}) in its IRI-safe version,\\
\emph{<cl. src tbl>} refers to the table name of the database table
containing the respective foreign key (see Section~\ref{iris_clashes})
in its IRI-safe version,\\
\emph{<cl. 1st src col>} refers to the name of the first foreign key
column of the respective foreign key (see Section~\ref{iris_clashes})
in its IRI-safe version,\\
\emph{<cl. tgt tbl>} refers to the table name of the table referenced by
the respective foreign key (see Section~\ref{iris_clashes})
in its IRI-safe version and\\
\emph{<cl. 1st tgt col>} refers to the name of the first column referenced
by the respective foreign key (see Section~\ref{iris_clashes})
in its IRI-safe version.\\

\begin{table}[H]\begin{centering}
		\begin{tabular}{p{6.3cm}|p{9.7cm}}
			\textbf{IRI type} & \textbf{Proposed IRI} \\ \hline
			Entity map OWL class IRI & <base:>\code{TABLE\_\_}<cl. tbl name>\\
			Identifier map IRI pattern & <base:>\code{TBL\_\_}<cl. tbl name>\code{/}<cl. name 1st pk col>\newline \ind{} \code{/\{\$1\}/}<\code{/}...>\\
			Attribute map OWL property IRI & <base:>\code{PROP\_\_}<cl. tbl name>\code{\_\_}<cl. col name>\\
			Relation map OWL property IRI & <base:>\code{REF\_\_}<cl. src tbl>\code{/}<cl. 1st src col>\newline \ind{} <\code{/}...>\code{/}<cl. tgt tbl>\code{/}<cl. 1st tgt col><\code{/}...>\\
			Subtype map IRI prefixes & <base:>\code{SUBTYPE\_\_}<cl. tbl name>\code{\_\_}\newline \ind{} <cl. col name>\code{/}\\
%			% Slanted and with underscores and without "clean":
%									Entity map OWL class IRI & \textit{<base>}\code{:TABLE\_\_}\textit{<table\_name>}\\
%									Identifier map IRI pattern & \textit{<base>}\code{:TBL\_\_}\textit{<table\_name>}\code{/}\textit{<name\_1st\_pk\_col>}\newline \ind{} \code{/\{\$1\}/}\textit{<\code{/}...>}\\
%									Attribute map OWL property IRI & \textit{<base>}\code{:PROP\_\_}\textit{<table\_name>}\code{\_\_}\textit{<col\_name>}\\
%									Relation map OWL property IRI & \textit{<base>}\code{:REF\_\_}\textit{<src\_table>}\code{/}\textit{<1st\_fk\_src\_col>}\newline \ind{} \textit{<\code{/}...>}\code{/}\textit{<tgt\_table>}\code{/}\textit{<1st\_fk\_tgt\_col>}\textit{<\code{/}...>}\\
%									Subtype map IRI prefixes & \textit{<base>}\code{:SUBTYPE\_\_}\textit{<table\_name>}\code{\_\_}\textit{<col\_name>}\code{/}\\
		\end{tabular}
		\caption{Proposed IRIs to be used in OBDA specification map fields}
		\label{bootstrap_tab_iris}
\end{centering}\end{table}

It is easily verified that the proposed IRI scheme is correct
regarding the requirements described in Section~\ref{iris_req}:
it provides unique IRIs for all types of IRIs it allows to create,
regardless of the chosen base IRI
(see proof in Section~\ref{iris_proof}).
Furthermore, the IRI scheme is expressive: ignoring the base
IRI part, the kind of entity identified by the IRI can be
determined by beginning of the IRI.
In addition, it is regular in that
the name of the containing table always occurs before the
name of the first database column.

Taking the information in Section~\ref{iris_clashes} into account,
it is trivial to observe that the suggested IRI scheme, leaving
out the demand of IRI-safe versions, is still correct, given that
all IRIs are generated using the same base IRI.

Note that it is in any case necessary that the beginnings
of all kinds of IRIs be mutually different:
if, for example, an Identifier map IRI pattern also would
commence with ``<base:>\code{TABLE\_\_}'', a table named
``\code{PERSONS/\{17\}}'' -- which is a valid table name for
example in SQL \cite{sql} -- possibly could get an Entity map OWL
class IRI assigned which clashes with the IRI resulting from the
expansion of the IRI pattern
``<base:>\code{TABLE\_\_PERSONS/\{\$1\}}''.

\subsection{Proof of correctness of the proposed IRI scheme}
\label{iris_proof}
As described in Section~\ref{iris_req}, the previously described
IRI schema is required to generate several types of IRIs without
introducing name clashes, thus two equal IRIs for two distinct
entities, independently of the chosen base IRIs.
Additionally, the user shall be able to chose additional IRIs
he can be sure won't collide with IRIs generated with the scheme
from an infinite set.

In this proof, like in Section~\ref{iris_clashes}, the strings
``\code{TABLE\_\_}'', ``\code{TBL\_\_}'', ``\code{PROP\_\_}'',
``\code{REF\_\_}'' and ``\code{SUBTYPE\_\_}'' are called
\emph{marking strings}.\\
Strings prefixed by `\textasciitilde' are referred to as
\emph{escaped}, while strings not prefixed by `\textasciitilde'
are referred to as \emph{unescaped}.

In the following, it is proven that the IRIs of each type do not
clash, neither among themselves nor with IRIs of other types.
Since all generated IRIs begin with a marking string, every IRI \emph{not}
beginning with a marking string, thus an infinite quantity,
is sure not to collide with any of the generated IRIs, and so,
the correctness regarding to the stated requirements is then proven.

Each Entity map OWL class IRI (including its base IRI) is of the form
$\alpha$\code{TABLE\_\_}$\beta$, with $\alpha$ not ending with `\textasciitilde'
and $\alpha$ and $\beta$ not containing any unescaped marking strings.\\
Thus, $\beta$ is the table name, making the IRI unique among all
other Entity map OWL class IRIs (see considerations in
Section~\ref{iris_clashes}).
Because the IRI does not contain any unescaped marking strings,
it cannot collide with any IRI of another type and thus is indeed unique.

The proof for Identifier map IRI patterns, Attribute map OWL property IRIs,
Relation map OWL property IRIs and Subtype map IRI prefixes is exactly
analog.

\hfill $\Box$