-\section{Generating unique IRIs for OBDA specification entities}
+\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$
\ No newline at end of file
git://git.uio.no / u / philim / db2osl_thesis.git / blobdiff