\section{Introduction and basic notation}

Consider the control system
\begin{align}
\label{E}&\dot x = \tilde{f}(x,u,v) + \displaystyle\sum_{\alpha=1}^m  \tilde g_\alpha(x,u)\dot u^\alpha, \\
\label{E0}&x(a)=\bar{x},\quad u(a)=\bar{u},
\end{align}
where $v:[a,b] \to V \subset \mathbb{R}^l$ is a {standard bounded control} while  $u:[a,b] \to U \subseteq \mathbb{R}^m$ is  an $\mathcal{L}^1-$function, which we refer to  as the {\em impulsive control.} The presence of the derivative $\dot u$ on the right hand-side  raises the issue of the definition of a (possibly discontinuous) solution  $x:[a,b] \to \mathbb{R}^n.$
Several applications of this type of system are known, e.g. in mechanics, biology and economics. In optimal control theory impulses arise as soon as the control is unbounded and the cost lacks coercivity properties.
It is well-known that an approach based on Schwartz distributions cannot work (see e.g. \cite{Haj85}), this fact marking a crucial difference with the case when the vector fields $\tilde g_\alpha$ are constant.
However, an  appropriate  concept of solution for \eqref{E}-\eqref{E0} has been proposed in the late eighties (see e.g. \cite{Bre87,BreRam91,Dyk94}), also in connection with optimal control problems.
(Notice that  one cannot exploit  the notions of solutions  utilized for $u$  e.g. in \cite{BreRam88,Mil89,SilVin96}, for the controls are allowed to have {\it unbounded} variation).
In this paper we adopt and slightly extend the notion in \cite{BreRam91},   calling  it {\it pointwise defined solution} (shortly: {\it p.d. solution}\footnote{Actually, we call it {\em limit solution} in the subsequent articles (see \cite{AroRam13a,AroRam13b})}).
We begin by stating and partially proving elementary properties of p.d. solutions, like existence, uniqueness and continuous dependence on the data.  Afterwards, we focus on the question whether a Mayer type  optimal control  problem on the interval $[a,b],$
\begin{equation}
\label{infL1}
\inf_{(u,v)\in \mathcal{L}^1\times L^1}\psi(x( b), u(b)),
\ee
 is in fact a {\it proper extension} of the standard problem
 \begin{equation}
 \label{infAC}
 \inf_{(u,v)\in AC\times L^1}\psi(x( b), u(b)),
 \ee
where $\mathcal{L}^1$ and $L^1$ stand for the ``set of Lebesgue integrable functions"  (on [a,b])  and its quotient set, respectively; while $AC$ means ``absolutely continuous".

Loosely speaking, a {\it proper extension} of a minimum problem is a new problem in which the old one is embedded, in such a way  that the domain of the original problem is (somehow) dense in the new domain and the two problems have the same infimum value.

Our motivation  to study proper extensions of \eqref{infAC} comes mainly  from the need of  giving a physically acceptable meaning to  typical investigations for optimal control problems involving p.d. solutions. An instance is represented by necessary conditions for optimality. Indeed, in order that such necessary conditions are of practical use  one should rule out  the occurrence of  {\em Lavrentiev-like phenomena,} namely the fact that the infimum value of the extended problem is strictly less then that of the original system. Another instance that makes the search for proper extensions reasonable is dynamic programming and  its PDE expression, the Hamilton-Jacobi equation (see Section \ref{SecLast}).
Of course, the case where terminal constraints are imposed on the trajectories is of great  interest both for necessary conditions and dynamic programming. This case, which poses non-trivial additional difficulties, is investigated  in \cite{AroRam13c}.

The paper is organized as follows: in the remaining part of the present Section we introduce the notation and state some general  preliminary results. In Section \ref{SecCauchy} we present the definition and basic results on Cauchy problems involving p.d. solutions.
In Section \ref{SecProper} it is shown that the minimum problem with p.d. solutions is in fact a proper extension of the standard problem. In Section \ref{SecBV} we prove that the minimum problem with p.d. solutions is also the limit when $K\to+ \infty$ of the (impulse) problems corresponding  to $u$ with total variation bounded by $K$. In Section \ref{SecLast}, we propose some final considerations concerning existence of minima and the Hamilton-Jacobi equation for the problem \eqref{infL1}.

\subsection{Notation and preliminaries}

Let $[a,b]$ be a real interval and $E \subseteq \mathbb{R}^d.$
$\mathcal{L}^1([a,b];E)$ will denote  the space of Lebesgue integrable functions defined on $[a,b]$ and having  values in $E.$  We shall use $L^1([a,b];E)$ to denote the corresponding set of equivalence classes, and $AC([a,b];E)$ to denote the space of absolutely continuous functions defined on $[a,b]$ with values in $E.$

Let us extend the functions $\tilde f,\tilde g_\alpha$, $\alpha =1,\dots,m$  to vector fields $f,g_\alpha$  on $\mathbb{R}^{n+m}$ by setting
\begin{equation}\label{fieldsgf}
f:= f^j\frac{\partial}{\partial x^j},\qquad g_\alpha:= g_{\alpha}^j \frac{\partial}{\partial x^j} +     \frac{\partial}{\partial z^\alpha}\,,
\end{equation}
where $\left(\frac{\partial}{\partial x^1},\dots,\frac{\partial}{\partial x^n}, \frac{\partial}{\partial z^1},\dots, \frac{\partial}{\partial z^m}\right)$ is the canonical basis of $\mathbb{R}^{n+m}$ and  we have adopted the {\em summation convention }over  repeated indexes. When not otherwise specified, Latin indexes run from $1$ to $n,$ while Greek indexes run from $1$ to $m.$

The hypothesis below is assumed throughout  the article.

\begin{assumption}[Commutativity]
\label{AssComm}
For every pair $\alpha,\beta,$
\begin{equation}\label{gicomm}
{[{g}_\alpha,{g}_\beta]=0,}
\ee
where $[{g}_\alpha,{g}_\beta] $ denotes the {\em Lie bracket}
of  $g_\alpha$ and $g_\beta,$ that in coordinates is defined by $[{g}_\alpha,{g}_\beta] := Dg_\beta\, g_\alpha - Dg_\alpha \, g_\beta.$
(Notice, in particular,  that the last $m$ components of $[{g}_\alpha,{g}_\beta]$ are zero.)
\end{assumption}

\begin{remark}
While this commutativity assumption is not a generic hypothesis, we impose it here motivated by the following reasons: 1) the scalar case and some mechanical applications are covered, and 2) we can ensure uniqueness of the solution of the impulsive Cauchy problem.
\end{remark}

Besides Hypothesis \ref{AssComm} we shall assume the following:

\begin{assumption}
\label{H1}
\begin{itemize}

 \item[(i)] $V \subseteq \mathbb{R}^l$ is compact.
 \item[(ii)] For every $v \in V$, ${f}(\cdot,\cdot,v):\mathbb{R}^{n+m}\to\mathbb{R}^{n+m}$ is locally Lipschitz continuous and, for every $(x,u)\in\mathbb{R}^{n+m}$ one has that ${f}(x,u,\cdot): V \to\mathbb{R}^{n+m}$ is continuous.
 \item[(iii)] There exists $M>0$ such that $|f(x,u,v)| \leq  M(1+|(x,u)|),$ for every $(x,u) \in \mathbb{R}^{n+m},$ uniformly in $v \in V.$
 \item[(iv)] The vector fields $g_\alpha:\mathbb{R}^{n+m}\to\mathbb{R}^{n+m}$ are of class $\mathcal{C}^1$ and there exists $N>0$ such that $|g_\alpha(x,u)| \leq  N(1+|(x,u)|),$ for every $(x,u) \in \mathbb{R}^{n+m}.$
\end{itemize}
\end{assumption}

We observe that the sublinearity in (iii) and (iv) can be replaced by other conditions guaranteeing existence of the integral trajectories.

Let $h$ be a locally Lipschitz vector field on a $\mathcal{C}^1-$manifold $M$, and let $m\in M$. Whenever the solution to
\begin{equation}
\frac{\rm d}{{\rm d} t}  x(s) = h(x(s)),\quad h(0)=m
\ee
is defined on a interval $I$ containing $0$,   we use  ${\rm exp}({t h})(m)$ to denote the value of this  solution at time $t,$ for every $t\in I.$
We remark that the identification ${\rm exp}({h})={\rm exp}({1h})$
is consistent with this definition.

\section{The Cauchy problem}\label{SecCauchy}
Let us introduce a change of coordinates $\phi$ in the space $\mathbb{R}^{n+m}$ that -thanks to Hypothesis \ref{AssComm}- simultaneously  transforms the vector fields $g_\alpha$ into constant vector fields.

 \subsection{A crucial change of coordinates}

Let  $\mathrm{Pr}:\mathbb{R}^{n} \times \mathbb{R}^m\rightarrow \mathbb{R}^n$ denote the {canonical projection} on the first factor,
$\mathrm{Pr}(x,z) := x,$
and let the function  $\varphi:\mathbb{R}^{n+m}\to \mathbb{R}^n$ be defined by
\begin{equation*}
\varphi(x,z) :=
\mathrm{Pr} \Big( \exp \left({- z_{\alpha} g_{\alpha}}\Big)
(x,z)\right).
\end{equation*}
 Let us consider the map $\phi:\mathbb{R}^{n+m}\rightarrow \mathbb{R}^{n+m}$ defined by
\begin{equation*}
\phi(x,z) := (\varphi(x,z),z).
\end{equation*}
It  is straightforward to prove the following result:

\begin{lemma}
Assume that the vector fields $g_1,\dots,g_m$ are of class $\mathcal{C}^r,$ with $r\geq 1.$ Then $\phi$ is a $\mathcal{C}^r$-diffeomorphism of $\mathbb{R}^{n+m}$ onto itself and, for every $(\xi,\zeta)\in \mathbb{R}^{n+m},$ one has
\begin{equation}\label{phiinv}
\phi^{-1}(\xi,\zeta) = (\varphi(\xi,-\zeta), \zeta).
\end{equation}
\end{lemma}

The $\mathcal{C}^r$-diffeomorphism  $\phi$  induces a $\mathcal{C}^{r-1}$-diffeomorphism $D\phi$ on the tangent bundle. For each $\alpha=1,\hdots,m,$ let us set
\begin{equation}\begin{array}{l}
F(\xi,\zeta,v):= D\phi (x,z) \, f(x,z,v),
\\
G_\alpha(\xi,\zeta):= D\phi (x,z) \, g_{\alpha}(x,z).
\end{array}
\ee

\begin{lemma}
\label{flowbox}
For every $i=1,\dots, n,$ $\alpha=1,\dots, m,$
\begin{equation}
F =\left(\frac{\partial \varphi^i}{\partial x^j} \tilde{f}^j \right) \frac{\partial}{\partial x^i},\quad {G}_{\alpha}
= \frac{\partial }{\partial z^\alpha},
\ee
where we have set $\varphi=(\varphi^1,\dots,\varphi^n).$
\end{lemma}

\begin{remark}
The proof of Lemma \ref{flowbox} (see \cite[Lemma 2.1]{BreRam91} for details) is in fact a direct consequence of the  {\em Simultaneous Flow-Box Theorem}  (see e.g.  \cite{Lang}).
\end{remark}

Notice that the last $m$ components of $F$ are zero.  Therefore, in the new coordinates $(\xi,\zeta),$ the control system \eqref{E} turns into  the simpler form
\begin{equation}
\label{xieq}
 \dot\xi(t) = \tilde{ F}(\xi(t),u(t),v(t)).
\ee
From now on we assume that the data are such that the Cauchy problem for \eqref{xieq} has a unique solution defined on $[a,b],$ for each $u\in AC([a,b];\mathbb{R}^m),$ $v\in L^1([a,b];V).$ For instance, one can verify that this property holds true as soon as condition (iv) in Hypothesis \ref{H1} is replaced by (iv') below, which implies that $D \phi$ is globally bounded,
\vspace{1pt}
\begin{itemize}
\item[(iv')] $g_\alpha$ and $\mathcal{C}^1$ are globally Lipschitz.
\end{itemize}

\vspace{1pt}

Lemma \ref{equivC1} below concerns relations between the solutions of the control systems in both systems of coordinates.

Since we are going to exploit the diffeomorphism $\phi:\mathbb{R}^{n+m} \to \mathbb{R}^{n+m} $ it is convenient to embed \eqref{E}-\eqref{E0} in the $n+m$-dimensional Cauchy problem
\begin{equation}\label{AS}\left\{\begin{array}{l}
\vspace{1pt}
\begin{pmatrix}
\dot{x}\\
\dot{z}
\end{pmatrix}
= f(x,z,v)+   {g}_\alpha(x,z) \dot  u^\alpha,\\
\begin{pmatrix}
{x}\\{z}
\end{pmatrix}(a)= \begin{pmatrix} \bar{x} \\ \bar{z} \end{pmatrix}.\end{array}\right.
\ee
 Recall that the vector fields $f$ and $g_\alpha,$ are defined in $\mathbb{R}^{n+m}\times V$ and $\mathbb{R}^{n+m},$ respectively.
When $u\in AC([a,b];\mathbb{R}^m),$ for every $(\bar{x},\bar{z}) \in \mathbb{R}^{m+n}$ and $v \in L^1([a,b];V),$  there exists a unique solution to \eqref{AS} in the interval $[a,b].$ We let  $(x,z)(\bar{x},\bar{z},u,v)(\cdot)$ denote this solution.

We shall also consider  the  Cauchy problem
\begin{equation}\label{TS}\left\{\begin{array}{l}
\vspace{1pt}
\begin{pmatrix}
\dot{\xi}\\
\dot{\zeta}
\end{pmatrix}
= F(\xi,\zeta,v)+   G_\alpha  \dot u^\alpha,\\
\begin{pmatrix}
{\xi}\\{\zeta}
\end{pmatrix}(a)= \begin{pmatrix} \bar{\xi} \\ \bar{\zeta} \end{pmatrix}
.\end{array}\right.
\ee
When $u\in AC([a,b];\mathbb{R}^m),$ there exists a unique solution to \eqref{TS} in $[a,b].$ We let  $(\xi,\zeta)(\bar{\xi},\bar{\zeta},u,v)(\cdot)$ denote this solution.

The essential difference between the two systems relies on the fact that the {\em vector fields  $G_\alpha$ are constant}.  This allows us to give a notion of solution for  \eqref{TS} also for merely  integrable controls $u.$ Indeed, it is natural to set
\begin{equation*}
\zeta(t) := \bar{\zeta} +u(t) - u(a),
\end{equation*}
 for all $t \in [a,b]$  and to let $\xi$ be  the Carath\'eodory  solution of the Cauchy problem $\dot\xi = F(\xi,\zeta,v),\,\,\xi(a) = \bar{\xi}.$

When $u\in AC([a,b];\mathbb{R}^m)$ the relation between the two systems is described in Lemma \ref{equivC1} below.
Let $(\xi,\zeta)(\bar{\xi},\bar{\zeta},u,v)(\cdot)$ denote  the unique solution of \eqref{TS} associated with $(\bar{\xi},\bar{\zeta})\in \mathbb{R}^{n+m}$ and $(u,v) \in AC([a,b];\mathbb{R}^m) \times L^1([a,b];V).$

\begin{lemma}
Let us consider $(\bar{x},\bar{z})\in \mathbb{R}^{n+m}$ and controls
\label{equivC1}$u\in AC([a,b];\mathbb{R}^m),$ $v \in L^1([a,b];V).$
Then,
\begin{equation}\label{xieta}
(\xi,\zeta)(\bar{\xi},\bar{\zeta},u,v)(t) = \phi\Big((x,z)(\bar{x},\bar{z},u,v)(t)\Big), \ee
\hbox{for all}~ $t\in [a,b],$ where $(\bar{\xi},\bar{\zeta}) := \phi(\bar{x},\bar{z}).$
\end{lemma}

The latter result is a straightforward consequence of the definition of $F$ and $G_\alpha.$

\subsection {Ponitwise defined solutions}

Throughout the paper we shall assume that $U$ is an {\it impulse domain}:
\begin{definition}
Let $U\subseteq\mathbb{R}^m.$ $U$ is called an {\em impulse domain} if, for every bounded interval $I \subset \mathbb{R},$ for each  function $u\in\mathcal{L}^1(I;U)$ and for every $t \in I,$ there exists a sequence $\{u_k\} \subset AC(I;U)$ such that $\|u_k-u\|_1\to 0$ and $u_k(t) \to u(t),$ when $n \to \infty.$
\end{definition}

Examples of impulse domains are:
\begin{itemize}
\item $U=\bar \Omega,$ with $\Omega$ a bounded, open, connected subset with Lipschitz boundary;
\item an embedded differentiable submanifold of $\mathbb{R}^m$.
 \item a convex subset $U\subseteq\mathbb{R}^m$ .
 \end{itemize}

\begin{definition}
Consider an initial data $\bar{x} \in \mathbb{R}^n$ and let  $(u,v)\in\mathcal{L}^1([a,b];U)\times L^1([a,b];V).$
We say that a map $x:[a,b]\to \mathbb{R}^{n}$ is an {\em pointwise defined solution} (shortly  {\em p.d. solution}) of the Cauchy problem \eqref{E}-\eqref{E0} if, for every $t\in [a,b],$ the following conditions are met:
\begin{itemize}
\item[(i)] there exists a sequence $\{ u_k \} \subset AC([a,b];U)$ such that
$u_k\to u$ in $L^1([a,b];U),$ $u_k(a) \to u(a),$ $u_k(t) \to u(t),$ when  $k \to \infty,$ and  ;
\item[(ii)] for each $k \in \mathbb{N},$ there exists a (Carath\'eodory) solution
$x_k:[a,b]\to\mathbb{R}^{n}$ of  \eqref{E}-\eqref{E0} corresponding to the control $(u_k,v)$ and the initial condition $(\bar{x},\bar{u} := u(a));$
\item[(iii)] the sequence $\{ x_k \}$  has uniformly bounded values and converges to $x$  in $L^1([a,b];\mathbb{R}^{n})$ and, moreover, $\displaystyle \lim_{k \to \infty} x_k(t) = x(t).$
\end{itemize}
\end{definition}

 \begin{remark}
When $u$ is absolutely continuous, the  notion of e.d solution  is equivalent to  the standard concept of Carath\'eodory solution. Moreover, in \cite{AroRam13a}, we show that the notion of p.d. solution is quite general and when controls $u\in BV$ it coincides with the most  known concepts of solution, even in the generic case when the Lie brackets do not vanish.
\end{remark}

\begin{theorem}[Existence, uniqueness, representation]
\label{ex-un}
For every $\bar{x} \in \mathbb{R}^{n},$ and every control pair $(u,v)\in\mathcal{L}^1([a,b];U)\times L^1([a,b];V),$ there exists a unique p.d. solution of the Cauchy problem \eqref{E}-\eqref{E0} defined on $[a,b],$ where we have set $\bar{u} := u(a).$ We shall use $x(\bar{x},u,v)(\cdot)$ to denote this solution.
Moreover, setting $\bar{\xi} := \varphi(\bar{x},u(a)),$ one has
\begin{equation}
x(\bar{x},u,v)(t) = \varphi(\xi(t),-u(t)),
\ee
for all $t\in [a,b],$ where $\xi(\cdot):=\xi(\bar{\xi},u,v)(\cdot)$ is the Carath\'eodory solution of the Cauchy problem
\begin{equation}\label{xiCO}
\dot\xi=F(\xi,u,v),\quad\xi(a) = \bar{\xi}.
\ee
\end{theorem}

To prove this theorem, which extends an analogous result in \cite{BreRam91} where $f$ did not depend on the standard control $v,$ we shall make use of the following result.

 \begin{lemma}[see \cite{AroRam13b}]
 \label{cont-depAC}
 The following assertions hold true:
\begin{itemize}
\item[(i)] For $r>0$ and $K\subseteq U$ compact, there exists a compact subset $K'\subset \mathbb{R}^{n},$ such that the trajectories $x(\bar x,u,v)(\cdot)$ have values in $K',$ whenever we consider $\bar{x} \in B_r(0),$ $u\in AC([a,b];K)$ and $v\in L^1([a,b];V).$
\item[(ii)] For each $r$ and $K$ as in  (ii), there exists a constant $M>0$ such that, for every $t \in[a,b],$ for all $\bar{x}_1, \bar{x}_2 \in B_r(0),$ for all $u_1,u_2 \in AC([a,b];K)$ and for every $v \in L^1([a,b];V),$ one has
\begin{equation*}
\begin{split}
|x_1(t)-x_2(t)|& +   \|x_1-x_2\|_1 \leq\\
& M\Big[ |\bar{x}_1-\bar{x}_2|+ |u_1(a)-u_2(a)| \\
& + |u_1(t)-u_2(t)|+\|u_1-u_2\|_1
\Big].
\end{split}
\end{equation*}
where $x_1 := x(\bar{x}_1,u_1,v_1),$ $x_2 := x(\bar{x}_2,u_2,v_2).$
\end{itemize}

\end{lemma}

\begin{proof} {\it (of Theorem \ref{ex-un}) }
Set  $\bar{u}:= u(a),$ $(\bar{\xi},\bar{\zeta}) := \phi(\bar{x},\bar{u}), $  $\zeta(\cdot):= \bar\zeta +u(\cdot)-\bar{u},$  and let $\xi$ be the solution of the differential equation \eqref{xieq} with initial condition $\xi(a) = \bar{\xi}.$ Observe that $\bar{\zeta} := \bar{u}$ and hence, $\zeta \equiv u.$

Define $(x,z) := \phi^{-1}\circ(\xi,\zeta).$ Let us show that $(x,z)$ is a p.d. solution of \eqref{AS}. Choose $t \in [a,b]$ and a sequence of absolutely continuous controls $u_k: [a,b] \to U$ converging to $u$ in the $L^1$ topology and verifying $u_k(a) \to \bar{u},$ $u_k(t) \to u(t)$  when $k\to \infty.$
Since $u$ is bounded it is not restrictive to assume that the functions $\{ u_k \}$ have equibounded values.  Let $(\xi_k,\zeta_k)$ be the corresponding solutions to \eqref{TS} and set
\begin{equation}
\label{xkdef}
(x_k,z_k):=  \phi^{-1}\circ(\xi_k,\zeta_k).
\ee
Note, in particular, that  the paths $(\xi_k,\zeta_k)$ and $(x_k,z_k)$ are equibounded.
Then
\begin{equation*}
\begin{split}
\|(x,z)-&(x_k,z_k)\|_1 \\
&= \| \phi^{-1}\circ(\xi,\zeta) -
 \phi^{-1}\circ(\xi_k,\zeta_k)\|_1 \rightarrow_{k \to \infty} 0,
 \end{split}
 \end{equation*}
as the map
 $\phi^{-1}$ is Lipschitz continuous on compact sets.
 Moreover, since $\zeta_k(t) = \bar{\zeta} + u_k(t) - u_k(a),$ one has $\zeta_k(t) \to \zeta(t).$  Therefore, in view of \eqref{xkdef} and since $\xi_k \to \xi$ uniformly, $(x_k(t),z_k(t)) \to (x(t),z(t)).$
 This concludes the part concerning existence and representation of a solution.

In order to prove uniqueness, let $x^1(\cdot)$ and $x^2(\cdot)$ be solutions of \eqref{E}-\eqref{E0} both associated with the same data $\bar{x} \in \mathbb{R}^n,$ $(u,v) \in \mathcal{L}^1 \times L^1$ and where $\bar{u}:=u(a).$  Assume by contradiction that there exists $t \in [a,b]$ such that
 $x^1(t)\neq x^2(t)$. According to the definition of p.d. solution there exist sequences  $\{ u^1_k\}_{k\in\mathbb{N}}$, $\{u^2_k\}_{k\in\mathbb{N}}$  in $AC ([a,b];U)$ such that, for $i=1,2$, one has
 \begin{equation}\ba{c}
u^i_k(a) \to u(a),\quad u^i_k(t) \to u(t), \\
\|u^i_k - u\|_1\to 0,\quad \|x(\bar{x},u^i_k,v)-x^i\|_1\to 0.
 \ea
\end{equation}
Hence, by Lemma \ref{cont-depAC} above, we have,
\begin{equation*}
\ba{c}
 |x^1_k(t)-x^2_k(t)| \leq M
\left( |u_k^1(a) - u_k^2(a)| \right.\\
\qquad\qquad\left.+ |u_k^1(t)-u_k^2(t)|+ \|u^1_k-u^2_k\|_1\right) \to 0.
\ea
\end{equation*}
Therefore,
$
 |x^1(t)-x^2(t)|
 = \lim_{k\to\infty}
 |x^1_k(t)-x^2_k(t)|  = 0,
$
which is a contradiction. The proof is concluded.
\end{proof}

 \vspace{2pt}

Let us give below a toy example of a p.d. solution corresponding to a discontinuous $u$ with unbounded variation.
\begin{example}
Let us consider the differential equation
\begin{equation}
\label{eqex}
\dot{x} = xv+ x\dot{u},\quad x(0)=\bar{x},
\ee
on the interval $[0,1],$ with
\begin{equation*}
v(t):=
\left\{
\ba{cl}
1, & \text{for } t\in[0,1/2[,\\
0, & \text{for } t\in [1/2,1].
\ea
\right.
\end{equation*}
Observe that, if $u \in AC([0,1];\mathbb{R}),$ then, for any $[a,b]\subseteq [1/2,1],$ the associated Carath\'eodory solution of \eqref{eqex} verifies
\begin{equation}
\label{forex}
x(t)=x(a)e^{u(t) - u(a)}.
\ee
Consider now the $\mathcal{L}^1-$control
\begin{equation*}
u(t):=
\left\{
\ba{cl}
(-1)^{k+1}, & \text{for } t\in[1-\frac{1}{k},1-\frac{1}{k+1}[,\,\, k \in \mathbb{N},\\
0, & \text{for } t=1.
\ea
\right.
\end{equation*}
On the subintervals of $[1/2,1]$ where $u(\cdot)$ is absolutely continuous, one may use \eqref{forex} to compute $x(\cdot).$ On the other hand, one can easily check that
\begin{equation*}
\begin{split}
x(1-1/k _+) &= x(1-1/k_-)e^2, \quad \text{if $k$ is odd},\\
x(1-1/k _+) &= x(1-1/k_-)e^{-2}, \quad \text{if $k$ is even},
\end{split}
\end{equation*}
where $x(1-1/k_-)$ and $x(1-1/k _+)$ denote the left and right limits of $x$ at $t=1-1/k,$ respectively.
Hence, the p.d. solution $x(\cdot)$ of \eqref{eqex} associated with $u(\cdot)$ is given, for any $t\in [0,1],$ by
\begin{equation*}
x(t):=
\left\{
\ba{cl}
\bar{x} e^t, & \text{for } t\in[0,\frac{1}{2}[,\\
\bar{x} e^{1/2} e^{-2}, & \text{for } t \in \bigcup_{k=1}^{\infty} [1-\frac{1}{2k},1-\frac{1}{2k+1}[,\\
\bar{x} e^{1/2}, & \text{for } t \in \bigcup_{k=1}^{\infty} [1-\frac{1}{2k+1},1-\frac{1}{2k+2}[,\\
\bar{x} e^{-1/2}, & \text{for } t=1.
\ea
\right.
\end{equation*}
Notice that both $u$ and $x$ have infinitely many discontinuities and  unbounded variation, and are everywhere pointwise defined.
\end{example}

 \begin{theorem}[Dependence on the data]
 \label{cont-depL1}
 The following assertions hold.
\begin{itemize}
\item[{(i)}] For each $\bar{x} \in \mathbb{R}^{n}$ and $u\in \mathcal{L}^1 ([a,b];U)$ the function $v(\cdot)\mapsto x(\bar{x},u,v)(\cdot)$ is continuous from $L^1([a,b];V)$ to $L^1([a,b];\mathbb{R}^n).$
\item[(ii)] For $r>0$ and $K\subseteq U$ compact, there exists a compact subset $K'\subset \mathbb{R}^{n},$ such that the trajectories $x(\bar x,u,v)(\cdot)$ have values in $K',$ whenever we consider $\bar{x} \in B_r(0),$  $u\in \mathcal{L}^1([a,b];K),$ and $v\in L^1([a,b];V).$
\item[(iii)] For each $r$ and $K$ as in  (ii), there exists a constant $M>0$ such that, for every $t \in[a,b],$ for all $\bar{x}_1, \bar{x}_2 \in B_r(0),$ for all $u_1,u_2 \in \mathcal{L}^1([a,b];K)$  and for every $v \in L^1([a,b];V),$ one has
\begin{equation*}
\begin{split}
|x_1(t)-&x_2(t)| +  \|x_1-x_2\|_1 \\
\leq &\, M\Big[ |\bar{x}_1-\bar{x}_2|+ |u_1(a) - u_2(a)| \\
& + |u_1(t)-u_2(t)|+\|u_1-u_2\|_1
\Big].
\end{split}
\end{equation*}
where  $x_1 := x(\bar{x}_1,u_1,v_1),$ $x_2 := x(\bar{x}_2,u_2,v_2).$
\end{itemize}

\end{theorem}

 A detailed proof of this result is available in \cite{AroRam13b}.

 \section{Proper extension of a standard minimum problem}\label{SecProper}

Let us consider  the (standard)  optimal control problem
 \begin{equation}\label{ottimoCed}
 \inf_{(u,v)\in AC\times L^1}\psi(x(b), u(b))\,,
\ee
where it is assumed that:
 \begin{itemize}
  \item[(i)] the cost map $\psi: \mathbb{R}^{n+m}\to\mathbb{R} $ is continuous;
  \item[(ii)] $ AC\times L^1$  stands for  $ AC([a,b ];U) \times L^1 ([a,b ];V);$  \item[(iii)] $x(\cdot)=x(\bar x,u,v)(\cdot),$ i.e. $x(\cdot)$ is the p.d. solution of the Cauchy problem \eqref{E}-\eqref{E0} where $\bar{u} := u(a).$
 \end{itemize}

Our main concern here is to define  a {\it proper extension} of the minimum problem \eqref{ottimoCed}.

Let us give a formal notion of {\it proper extension}:

\begin{definition} Let $E$ be a set and let $\mathcal{F}:E\to\mathbb{R}$ be a function. A  {\em proper extension} of a minimum problem
 \begin{equation}\label{original} \inf_{e\in E} \mathcal{F}(e)\end{equation}
 is  a new minimum  problem
   \begin{equation}\label{new} \inf_{{\hat e}\in {\hat E}} {\hat \mathcal{F}}({\hat e})\end{equation}
on a set $\hat E$ endowed with a limit notion and     such that there exists an injective map $i: E\to {\hat E}$
   verifying the following properties:
   \begin{itemize}
     \item[(i)] $\hat \mathcal{F}(i(e)) = \mathcal{F}(e)$ for all $e\in E$ and, moreover, for every ${\hat e}\in {\hat E}$ there exists a sequence $(e_k)$ in $E$ such that, setting ${\hat e}_k:= i(e_k)$, one has
         \begin{equation}\label{limite}
         \lim_{k \to \infty} \big(\hat e_k,\hat \mathcal{F}(\hat e_k) \big) = ({\hat e},\hat\mathcal{F}(
         \hat  e)),
         \ee
        \item[(ii)]  $\displaystyle \inf_{e\in E} \mathcal{F}(e) =  \inf_{{\hat e}\in {\hat E} }{\hat \mathcal{F}}({\hat e}).$ \end{itemize}
     \end{definition}

After identifying $E$ and $\hat E$ with the set of pairs $(x(\cdot),u(\cdot))$ corresponding to controls in $AC \times L^1$ and  $\mathcal{L}^1 \times L^1,$ respectively,
we wish to investigate the question whether the  optimal control problem \begin{equation}\label{ottimoCed}
 \inf_{(u,v)\in \mathcal{L}^1\times L^1}\psi(x(b), u(b))\,,
\ee is a proper extension (with $i$ equal to the identity map) of the problem
\begin{equation}\label{ottimoC}
\inf_{(u,v)\in AC\times L^1}\psi(x(b), u(b)).
\ee

\begin{remark}
\label{rem-dense}
Notice that, in view of the definition of p.d. solution, the density property {(i)} is automatically satisfied.
\end{remark}

      To investigate the validity of  (ii), let us consider the reachable sets (at time $b$ for a fixed initial values $\bar{x}$ and $\bar{u}$):
\begin{equation}\label{reach1}
\begin{split}
\mathcal{R}:=  \{ (x,u)(b) :\,& (u,v) \in \mathcal{L}^1 \times L^1,\\
& u(a)=\bar{u},\ x = x(\bar x, u,v)\},
\end{split}
\ee
\begin{equation}\label{reach2}
\begin{split}
\mathcal{R}^+ := \{ (x,u)(b): \,& (u,v) \in AC \times L^1,\\
& u(a)=\bar{u},\  x = x(\bar x, u,v)\}.
\end{split}
\ee
Since the (Carath\'eodory) solution corresponding to an absolutely continuous $u$ is also a p.d. solution, one has
\begin{equation}\label{incl}
\mathcal{R}^+\subset \mathcal{R}.
\end{equation}
The inclusion is in general strict. However, the closure of the two sets always coincide.
\begin{theorem}\label{reach-th1}
\begin{equation}\label{reach-eq1}
\overline{{\mathcal{R}}} = \overline{{\mathcal{R}^+}}.
\ee
\end{theorem}

\begin{proof}
In view of \eqref{incl} it suffices to prove that $\overline{{\mathcal{R}}}  \subseteq \overline{{\mathcal{R}^+}}$. Assume by contradiction that there exists $y\in \overline{{\mathcal{R}}}$ such that
\begin{equation}\label{contr1}
d\Big(y,{\mathcal{R}^+}\Big)=\eta>0,\end{equation}
and let $\{(u_k,v_k)\} \subset \mathcal{L}^1([a,b];U)\times L^1([a,b];V)$ be a sequence of controls with $u_k(a)=\bar{u}$  and such that the final points $y_k:= \Big(x(\bar x,u_k, v_k)(b)\,,\,u_k(b) \Big)$ verify
$d(y_k, y)\leq  \eta/3,$ for all $k\in \mathbb{N}.$
Because of the definition of p.d. solution, for every $k\in\mathbb{N}$ there exists  $(\hat u_k, v_k)\in AC([a,b ];U)\times L^1([a,b ];V)$ such that, setting $\hat y_k:= \Big(x(\bar x, \hat u_k,v_k)(b),\hat{u}_k(b)\Big)$, one has $ d(\hat y_k ,y_k)\leq \eta/3,$
  so that
  $$
  d(y\, ,\, \hat y_k) \leq d(y\, ,\,  y_k) +  d(y_k , \hat y_k) \leq 2\eta/3,
  $$
  which contradicts \eqref{contr1}, as $\hat y_k\in {\mathcal{R}^+}.$
\end{proof}

Let us define the {\it value functions}
$$\begin{array}{c}
\vspace{2pt} \displaystyle V_{AC}(\bar{x},\bar{u}) :=  \inf_{(u,v)\in AC\times L^1}\psi(x(b), u(b))  \left(  = \inf_{\mathcal{R}^+} \psi(x,u)  \right),\\
\displaystyle V_{\mathcal{L}^1} (\bar{x},\bar{u})  :=\inf_{(u,v)\in \mathcal{L}^1\times L^1}\psi(x(b), u(b)) \left(  = \inf_{\mathcal{R}} \psi(x,u) \right),
\end{array}$$
where it has been made explicit that these values depend on the initial data $(\bar{x},\bar{u}).$

 \begin{corollary}
 \label{infug-th}
 For every  $(\bar x,\bar{u}) \in \mathbb{R}^{n+m},$ one has
\begin{equation}\label{infug}
V_{AC}(\bar x,\bar{u}) =  V_{\mathcal{L}^1}(\bar x,\bar{u}).
 \ee
  \end{corollary}

 Hence, also in view of Remark \ref{rem-dense}, we can conclude that problem \eqref{ottimoCed} {\em is a proper extension of   problem \eqref{ottimoC}}.

\section{Limits of minimun problems \\ with bounded variation}\label{SecBV}

Let us assume that $U$ is a convex set.

When the impulsive (possibly discontinuous) control $u$ has bounded total variation one can give a notion of solution based on the concept of  {\it graph completion} (see e.g. \cite{BreRam88}, \cite{Mil89}, \cite{SilVin96}).  This approach differs from the one above and can, in fact, be applied also to systems with no commutativity assumptions. However, if the commutativity hypothesis is standing, one can establish a one-to-one correspondence between the two concepts, as shown in Proposition \ref{ident} below.

For every $K\geq 0$, let us consider  the original system, supplemented with the variable $x_0=t,$
\begin{equation}\label{or+1}
\left\{
\ba{l}
\dot x_0 = 1,\\
\dot{x} = \tilde f(x,u,v)+ \sum_{\alpha=1}^m {\tilde g}_\alpha(x,u) \dot u^\alpha,\\
(x_0,x,u)(a) = (a,\bar x,\bar{u}),
\ea
\right.
\ee
where the impulsive controls $u$  belong to the set
$$
BV_K([a,b];U) := \Big\{u: [a,b] \to U,\, {\rm Var}[u]\leq K\Big\},
$$
where ${\rm Var}[u]$ denotes the {\em total variation of $u.$} We also consider the subset
$$
AC_K([a,b];U):= AC([a,b];U)\cap BV_K([a,b];U).
$$
\if made of absolutely continuous maps $u(\cdot)$ with values in $U$ and such that $\displaystyle \int_a^b |\dot u(t)|dt \leq K$.
\fi

\begin{definition}
We shall use $\mathcal{U}_K$ to denote the set  of maps $ ({\bf{u}}_0,{\bf{u}})\in Lip( [0,1];[a,b]\times U)$ \footnote{\,Here $Lip( [0,1];[a,b]\times U)$ denotes the space of Lipschitz continuous function defined in $[0,1]$ and with values in $[a,b]\times U.$} such that, for a.a. $s\in [0,1]$, ${\bf{u}}_0'(s)\geq 0$, ${\bf{u}}_0'(s)+ |{\bf{u}}'(s)| \leq b-a+K,$  and, moreover, $ {\bf{u}}_0([0,1]) = [a,b]$.  These maps will be called {\em space-time controls with  variation not larger than $K$.}
 Furthermore,   $\mathcal{U}_K^+\subset \mathcal{U}_K$ will denote  the subset made of those space-time controls $({\bf{u}}_0,{\bf{u}})$ such that ${\bf{u}}_0'>0$ for a.a. $s\in [0,1]$.
 \end{definition}

 Let us consider the {\it space-time control system} in the interval $[0,1]$ given by
\begin{equation}\label{spacetime}
\left\{
\begin{array}{l}
{\bf y}_0' = {\bf{u}}_0',\\
 \displaystyle\frac{d{\bf y}}{ds}= {\bf{u}}_0'\tilde f({\bf y},{\bf u},{\bf v})+ \sum_{\alpha=1}^m {\tilde g}_\alpha({\bf y},{\bf{u}}) {{\bf{u}}^\alpha}' , \\
({\bf y}_0,{\bf y},{\bf{u}})(0) = (a,\bar x,\bar{u})\,,
\end{array}\right.
\ee
where the apex denotes differentiation with respect to the {\it pseudo-time} $s$,  $({\bf{u}}_0,{\bf{u}})\in \mathcal{U}_K$, and ${\bf v} \in L^1([0,1];V)$.
If   ${\bf{u}}$ is absolutely continuous,  \eqref{spacetime} can be regarded as an {\em ad hoc}  Lipschitz continuous  time-reparameterization of \eqref{or+1}, as it is made precise in the following statement (whose proof merely relies on the chain rule for derivatives).

\begin{proposition}
\label{ident}
Let us consider controls  $(u,v)\in AC_K([a,b];U)\times L^1([a,b];V)$  and an initial data $\bar x\in \mathbb{R}^n.$  Let us set
$$
s(t) := \frac{\int_a^t (1 +|\dot u|) d\tau}{\int_a^b (1 +|\dot u|) d\tau}, \quad t(\cdot)={\bf y}_0(\cdot) := s^{-1}(\cdot),
$$
and
${\bf{u}}_0(s):= t(s)$, ${\bf{u}}(s) =  u\circ t(s)$, ${\bf v}(s):=  v\circ t(s).$
Then, $({\bf{u}}_0,{\bf{u}})\in \mathcal{U}_K^+$, $v\in L^1([0,1];V)$ and,  setting $x(\cdot):= x(\bar x, u,v)(\cdot) $, ${\bf y}(\cdot) ={\bf y}(\bar x, {\bf{u}},{\bf v})(\cdot)$, one has
\begin{equation}\label{repar}
x\circ t(s)  = {\bf y}(s), \quad \hbox{for all}~ s\in [0,1].
\ee
Conversely, if  $({\bf{u}}_0,{\bf{u}})\in \mathcal{U}_K^+$ , ${\bf v}\in L^1([0,1]; V)$,  setting
$
s(\cdot) := {\bf{u}}_0^{-1}(\cdot) $
and
$u(t) =  {\bf{u}}\circ s(t)$, $ v(t):=  {\bf v}\circ s(t)$,
one has that $(u,v) \in AC_K ([a,b];U)\times L^1([a,b];V)$ and
$$
x(t) = {\bf y}\circ s(t),  \qquad \hbox{for all}~ t\in [a,b],
$$
where $x(\cdot):= x(\bar x, u,v)(\cdot) $, ${\bf y}(\cdot) ={\bf y}(\bar x, {\bf{u}},{\bf v})(\cdot)$.
\end{proposition}

\vspace{1pt}

On the other hand, the space-time control system makes sense also when we allow ${\bf{u}}_0'(s)=0$  on some interval $[s_1,s_2]\subseteq[0,1]$. This accounts for a trajectory's { jump }  at  $t={\bf{u}}_0(s_1) \big(={\bf{u}}_0(s_2) \big).$ Notice that the trajectory `during' the jump is governed by the dynamics  $\sum_{\alpha=1}^m {\tilde g}_\alpha({\bf y},{\bf{u}}) {{\bf{u}}^\alpha}'.$ The commutativity hypothesis is here crucial, for it implies that the magnitude ${\bf y}(s_2)-{\bf y}(s_1)$ of the jump is independent of the path  $[s_1,s_2]\to{\bf{u}}(s).$

Consider now the {\em reachable sets} (at time $b$):
\begin{equation}\label{reach1K}
\mathcal{R}_K := \{ (x,u)(b) : (u,v)\in {BV}_K\times L^1\},
\ee
\begin{equation}\label{reach2K+}
\mathcal{R}_K^+ := \{ (x,u)(b) : (u,v)\in {AC}_K\times L^1\},
\ee
\begin{equation}\label{reach3}
\mathcal{R}_{K}^{BV} := \{ ({\bf y}(1),{\bf{u}}(1)) : \left(({\bf{u}}_0,{\bf{u}}),{\bf v}\right)\in \mathcal{U}_K\times L^1\},
\ee
\begin{equation}\label{reach4}
\mathcal{R}_{K}^{BV+} :=  \{ ({\bf y}(1),{\bf{u}}(1)) : \left(({\bf{u}}_0,{\bf{u}}),{\bf v}\right)\in \mathcal{U}_K^+\times L^1\},
\ee
where it is meant that the involved trajectories are the solutions of the corresponding Cauchy problems with given initial point $(\bar x,\bar{u}).$

It follows easily that
\begin{equation}\label{reachinc}\begin{array}{c}
\qquad \mathcal{R}_{K}^{BV+}\subset \mathcal{R}_{K}^{BV}\,\,\hbox{for all}~ K>0, \\\,\\
0 \leq K_1< K_2 \,\Rightarrow\,\mathcal{R}_{K_1}^{BV+} \subset \mathcal{R}_{K_2}^{BV+},\, \mathcal{R}_{K_1}^{BV} \subset \mathcal{R}_{K_2}^{BV}.
\end{array}
\ee
Moreover, in view of Proposition \ref{ident}, absolutely continuous solutions of \eqref{or+1} coincide with solutions of \eqref{spacetime} corresponding to $\mathcal{U}_K^+$, up to reparameterization. In particular,
\begin{equation}\label{reacheq}
\mathcal{R}^+_K  = \mathcal{R}_{K}^{BV+},\quad \text{for all } K\geq 0.
\ee
Furthermore,
\begin{equation}
\mathcal{R}_K = \mathcal{R}_K^{BV}.
\ee
This identity can be verified by exploiting the commutativity assumption (Hypothesis \ref{AssComm}), which makes all the graph completions equivalent, and then by associating to each control $u \in BV$ its {\em rectilinear graph completion.} The latter is a Lipschitz continuous path in space-time obtained by bridging the discontinuities of $u$ by means of rectilinear segments.

One can also prove  (see \cite{MotRam96}) the following statement.

 \begin{proposition}\label{st-th1}
 For  every solution ${\bf y}(\bar x, {\bf{u}}_0,{\bf{u}}, {\bf v})$ corresponding to a control $({\bf{u}}_0,{\bf{u}})\in \mathcal{U}_K$ there exists a sequence $ \{({{\bf{u}}_0}_h,{{\bf{u}}}_h)\}_{h\in\mathbb{N}}$ in $\mathcal{U}_K^+$ such that
 $$
 ({{\bf{u}}_0}_h,{{\bf{u}}}_h)\to ({\bf{u}}_0,{\bf{u}}), \quad {\bf y}(\bar x, {{\bf{u}}_0}_h,{{\bf{u}}}_h,  {\bf v}) \to  {\bf y}(\bar x, {\bf{u}}_0,{\bf{u}},  {\bf v}),
 $$
 uniformly on $[0,1].$ In particular, one gets,
\begin{equation}\label{reachcleq1}
 \overline{\mathcal{R}_{K}^{BV+}} = \overline{\mathcal{R}_{K}^{BV}}.
\ee
\end{proposition}

\begin{remark}\label{st-th2}
(see \cite{BreRam88})
If the vector field $\tilde f$ is independent of the ordinary control $v$, then the set of solutions to \eqref{spacetime} corresponding to controls in $\mathcal{U}_K$ is closed in the $\mathcal{C}^0-$topology. In particular,
the reachable set $\mathcal{R}_{K}^{BV}$ is compact, so that
$$
\overline{\mathcal{R}_{K}^{BV}}= \mathcal{R}_{K}^{BV}.
$$
\end{remark}

\begin{remark}
Let us point out that relations \eqref{reachinc}, \eqref{reacheq}, Proposition \ref{st-th1} and Remark \ref{st-th2} are valid also in the case when the commutativity in Hypothesis \ref{AssComm} is not imposed.
\end{remark}

 \begin{theorem}
\label{reach-th}
\begin{equation}\label{reach}
\overline\mathcal{R} =\overline{ \bigcup_{K \geq 0}  \mathcal{R}_{K}^{BV}} = \overline{ \bigcup_{K \geq 0}  \mathcal{R}_{K}^{BV+}}.
\ee
\end{theorem}

We refer to \cite{AroRam13b} for a proof of the latter result.

Let us to consider the value functions corresponding to problems with bounded variation:
\begin{equation*}
\ba{c}
V_{AC_K} (\bar{x},\bar{u})= \displaystyle\inf_{(u,v)\in AC_K\times\mathcal{L}^1}\psi(x(b), u(b)),\\
V_{BV_K^+}(\bar{x},\bar{u})=\displaystyle\inf_{({\bf{u}}_0,{\bf{u}},{\bf v})\in \mathcal{U}_K^+\times\mathcal{L}^1}\psi({\bf y}(1), {\bf{u}}(1)),\\
V_{BV_K} (\bar{x},\bar{u}) =\displaystyle \inf_{({\bf{u}}_0,{\bf{u}},{\bf v})\in \mathcal{U}_K\times\mathcal{L}^1}\psi({\bf y}(1), {\bf{u}}(1)).
\ea
\end{equation*}

\begin{corollary}\label{inftyed-th}
For every $(\bar{x},\bar{u}) \in \mathbb{R}^n \times U,$ one has
\begin{equation}\label{infty}
 \lim_{K\to \infty} V_{BV_K} (\bar{x},\bar{u}) = V(\bar{x},\bar{u}).
\ee

\end{corollary}

\section{Considerations on dynamic programming}\label{SecLast}

For every $K \geq 0,$ let us consider the map $W_K: [a,b]\times \mathbb{R}^M\times U\times [0,K]$ defined by letting $W_K(t,x,u,k)$ be the value function of the (impulsive)  minimum problem in $[t,b]$ with $u$-variation less than or equal to $K-k.$
By a reparameterization approach akin to the one in \cite{MotRam96}  one might prove that $W$
 is continuous and is the unique solution of a boundary value problem for a Hamilton-Jacobi equation involving the {\em compactified}  Hamiltonian
 \begin{equation*}
 \ba{l}
 H(t,x,u,k,p_t,p_x,p_u,p_k) \\
  \ \ :=\sup_{w_0+ |w|\leq 1, v\in V} {\mathcal H}(t,x,u,k,p_t,p_x,p_u,p_k; w_0,w,v),
 \ea
  \end{equation*}
 where the ${\mathcal H}$ is defined by
 $$
 \begin{array}{l}
 {\mathcal H}(t,x,u,k,p_t,p_x,p_u,p_k; w_0,w,v):=\\
 (p_t + p_x\cdot f(x,u,v)) w_0 + ( p_x \cdot g_\alpha + p_{u_\alpha}) w_\alpha + p_k|w_\alpha|.\end{array}$$

 Notice that $W_K(a,x,u,0)=V_{BV_K}(x,u)$, for all $(x,u)\in \mathbb{R}^n\times{U}$. In particular  the Hamilton-Jacobi  equation
 $$
 H(t,x,u,k,\nabla W_K) = 0
 $$
 may be utilized  for both {sufficient conditions} of optimality and  { numerical analysis} of the problem with ${\rm Var} (u)\leq K.$ Via Corollary \ref{inftyed-th}, one can then address the general problem.

 \if{
 \subsection{Regularity of vector fields} Finally, let us comment the issue of the regularity of the data. The commutativity assumption $[g_\alpha, g_\beta]=0$ and the Simultaneous Flow-Box Theorem, which allow to define the coordinate change $\phi,$  have a classical interpretation for smooth vector fields. However, a notion of Lie bracket for locally Lipschitz continuous vector fields and a connected  Simultaneous Flow Box Theorem have been recently provided (see e.g.
 \cite{RamSus06}). Thus, one may conjecture that a notion of p.d. solution can be given also for the case when the $g_\alpha$'s are locally Lipschitz. Of course, one should somehow address the question raised by the non differentiability of the  transformation $\phi.$
 It is expectable that some notion of generalized differential has to be utilized. Accordingly, the vector field  $F$ would be  multivalued.
  }\fi

\bibliographystyle{plain}


\section{Introduction}
\subsection{Motivation}

The majority of the data within the internet is available nowadays in form
of tree-structured data (i.e. HTML, XML or 'XML dialects'). When searching for
certain information in huge document collections, the user typically (1) has no
knowledge of the structure of the document collection itself and
(2) is a non-expert user without any technical knowledge of XML or
XML query languages.
These requirements are met by XML keyword search where the user specifies the
searched information in form of a list of keywords (i.e., neither knowledge
of the document structure nor of any specific query language is required) and
document fragments are returned that contain each keyword of the specified keyword list.
For this purpose, the need for
efficient keyword search appraoches on XML data is high.

\subsection{Contributions}
Our paper presents \textit{IDCluster}, an approach to efficient keyword
search within XML data that is based on a DAG representation of the XML data,
where repeated substructures exist only once and therefore have to be searched
only once.
IDCluster combines the following features and advantages:
\begin{itemize}
\item Before building the index, IDCLuster removes redundant sub-trees and
splits the document into a list of so-called \textit{redundancy
components}, such that similar sub-trees have to be indexed and searched
only once.
\item For keyword search queries where parts of the results are contained
partially or completely within repeated sub-trees, the DAG-based keyword search
 outperforms the XML keyword search by a factor of more
than two on large documents, whereas it is comparably
fast for keyword search queries where all results occur in sub-trees that exist only once within the document.
\end{itemize}
To the best of our knowledge, IDCluster is the first approach that shows these
advantages.

\subsection{Paper organization}

The rest of the paper is organized as follows. Section~\ref{sec:prel} introduces the underlying data model
and presents the ideas of the set intersection keyword
search algorithm \cite{setintersection}\cite{setintersection2} on which our
approach is based. Section~\ref{sec:ourapproach} presents our adaptation of the ideas of Zhou et al. to build the index
based on the document's DAG instead of the document's tree in order to avoid
repeated search within identical structures. Section \ref{sec:eval} contains
the performance evaluations, Section \ref{sec:relatedwork}
discusses the advantages of our approach to already existing approaches, and
finally, section \ref{sec:conclusions} concludes the paper with a short summary.

\section{Preliminaries}\label{sec:prel}

\subsection{Data model}

We model XML trees as conventional labeled ordered trees. Each node represents
an element or an attribute, while each edge represents a direct nesting
relationship between two nodes. We store a list of all keywords
$k_n$ contained in the element name or attribute name respectively, or
in any text value for
each node $n$. Thereby, we tokenize each text label into keywords at its
white-space characters. E.g., a node with label "name" and text value "Tom
Hanks" is split into the three keywords \textit{name}, \textit{Tom} and
\textit{Hanks}. The keywords in $k_n$ are called \textbf{directly contained}
keywords of $n$. Keywords that are directly contained in a descendant of $n$
are called \textbf{indirectly contained} keywords of $n$. Keywords that are
either directly or indirectly contained in $n$ are called \textbf{contained}
keywords of $n$. Furthermore, we assign each node its
pre-order traversal number assigned as ID. Fig.~\ref{fig:example} shows
a sample XML tree. The ID of each node is written top left next to it. The
element or attribute name is given inside the node's ellipse, while the text
values are given below.

\begin{figure}[htb]
	\centering
	\includegraphics[width=\linewidth]{ex_fullsize_cropped}
	\caption{Example of an XML tree.}
	\label{fig:example}
\end{figure}

\subsection{Query semantics}

In the last decade, different search goals for XML keyword search
queries have been proposed. These search goals form subsets of the common
ancestor (CA) nodes. For a query $Q$, the set of common ancestors $CA(Q)$ contains all nodes that
contain every keyword of $Q$. For the given query $Q_{ex}=\{USA,
English\}$ and the example tree of Fig.~\ref{fig:example}, the common ancestors are
$C(Q_{ex})=\{1,2,4,5,11,12\}$.
The two most widely adopted CA subsets are the smallest lowest common ancestor (SLCA) and
the exclusive lowest common ancestor (ELCA). All nodes in $CA(Q)$ that do not
have descendants in $CA(Q)$ are in $SLCA(Q)$, e.g. $SLCA(Q_{ex})=\{5,12\}$. A
node $n$ is in $ELCA(Q)$, when $n$ contains each
keyword of $Q$ outside of each subtree of a
descending CA node of $n$, e.g.,
$ELCA(Q_{ex})=\{2,5,12\}$. Node 2 is in $ELCA(Q_{ex})$, because when we would remove node 5
(which is CA) and its descendants, node 2 still contains both keywords:
\textit{USA} in node 9 and \textit{English} in node 10. Note that the given
definitions imply $SLCA(Q) \subseteq ELCA(Q) \subseteq CA(Q)$.

\subsection{IDLists}

This paper's algorithm is based on the set intersection keyword search
algorithm FwdSLCA and its modifications as proposed by Zhou et al.
\cite{setintersection,setintersection2}.

Zhou et al. use IDLists as an index to efficiently perform keyword search. An
IDList is an inverted list of nodes that contain (directly or indirectly) a
certain keyword. For each node $n$ the IDList provides three values:
The \textit{ID} of $n$, the position of $n$'s parent inside the IDList named
$PIDPos$, and the number $N_{Desc}$ of nodes within $n$'s subtree
directly containing the keyword. IDLists are sorted by
ID.
Fig.~\ref{fig:idlists} shows the IDLists $L_{USA}$ and $L_{English}$ of
the keywords \textit{USA} and \textit{English} respectively. IDLists can be easily generated by
a single pass through the document.

\begin{figure}[h]
	\centering
	\includegraphics[width=0.8\linewidth]{ex_idlists_cropped}
	\caption{IDLists for the keywords \textit{USA} and \textit{English}.}
	\label{fig:idlists}
\end{figure}

\subsection{Search}\label{sec:otherapproach}

The general idea is to use set intersection on the IDLists of the query
keywords to find CA nodes. The found CA nodes are then checked against the SLCA or ELCA
semantics respectively to calculate the result set.

The basic SLCA search algorithm of \cite{setintersection,setintersection2},
\textit{FwdSLCA}, uses the method \textit{fwdGetCA} to efficiently calculate all CA nodes in
ascending order. This is done by maintaining pointers to the current position $C_i$ in
each IDList $L_i$, selecting the highest ID of all $C_i$, and binary searching
for this ID in the remaining IDLists. Due to the ascending order, a CA
node $n$ is SLCA if and only if the next found CA node is not a child of $n$.
This can be checked using the IDList's $PIDPos$.

For checking the ELCA semantics, the algorithm \textit{FwdELCA} uses an
additional stack for storing two arrays for each visited node $n$: One holds the
$N_{Desc}$ values of $n$, the other holds the accumulated $N_{Desc}$ values of
$n$'s CA children. As soon as every CA child of $n$ has been found, the
differences of those two arrays indicate whether $n$ is ELCA or not.

Beside \textit{FwdSLCA}, two more SLCA search algorithms based on set
intersection are proposed in \cite{setintersection,setintersection2}: The
algorithm \textit{BwdSLCA} finds CA nodes in reversed order, and as a result can
efficiently skip ancestors of CA nodes (note that ancestors of CA nodes by
definition never can be SLCA). The algorithm \textit{BwdSLCA+} additionally improves the binary search required for CA calculation by shrinking the search space. The shrinkage is based on the parent position information given by the $PIDPos$ value.

For \textit{FwdELCA}, one alternative is proposed: The algorithm
\textit{BwdELCA} finds CA nodes in reversed order and shrinks the binary search space like
\textit{BwdSLCA+}. The ancestor skipping introduced in \textit{BwdSLCA} cannot
be implemented for ELCA search since inner nodes can be an ELCA too.

\section{Our Approach}\label{sec:ourapproach}

The algorithm described in section~\ref{sec:otherapproach} is not
redundancy-sensitive, i.e., whenever there are repeated occurrences of
the same sub-tree, these occurrences are searched repeatedly.
However, the goal of our approach is to
follow the idea of DAG-based compression approaches and to exploit structural redundancies in
order to perform faster keyword search. This is done by splitting the original
XML tree into disjoint \textbf{redundancy components}. A
redundancy component is a subgraph of the original tree which occurs more than once within the tree. We then search
each redundancy component only once and combine the results to get the complete
result set, i.e., the same result as if we had performed the
search based on the tree and not based on the DAG.

\subsection{Index}

Our index is called IDCluster. It contains the IDLists for each redundancy
component and the redundancy component pointer map (RCPM) which is used for
combining the results of redundancy components. The IDCluster is generated in
two passes through the document.

The first pass is an extended DAG
compression where nodes are considered as being identical when (a) they directly contain the same keywords and (b) all
children are identical. When a node $n'$ is found which is identical to a node
$n$ found earlier, node $n'$ is deleted and the edge from its parent
$parent(n')$ to $n'$ is replaced by a new edge from $parent(n')$ to $n$. This new edge is called an offset edge and contains the difference between the IDs of
$n'$ and $n$ as an additional integer value. The information contained in offset
edges will later be used to recalculate the original node ID of $n'$.
Furthermore, for each node, we store the $OccurrenceCount$ which indicates the
number of identical occurrences of this node. Fig.~\ref{fig:dag} shows the XML
tree after the first traversal. The nodes with a white background have an $OccurrenceCount$ of 1, while nodes with a grey background have an $OccurenceCount$ of 2. E.g., node 5 is identical to node 12 in the original
tree. Hence node 12 is deleted and implicitly represented by node 5 and an
offset edge on its path with the offset +7. Node 5 has an $OccurrenceCount$ of
2, which indicates that node 5 now represents two nodes of the original tree.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.58\linewidth]{ex_dag_cropped}
	\caption{DAG compressed XML tree after the first traversal.}
	\label{fig:dag}
\end{figure}

In the second pass, the $OccurenceCount$ values are used for selecting
redundancy components: Each connected component consisting only of nodes with
the same $OccurenceCount$ is selected as a redundancy component. (The redundancy
component furthermore includes additional dummy nodes which represent nested
redundancy components and are introduced below.) Identifying redundancy
components and constructing their IDLists can be done easily in a single
document traversal utilizing the $OccurenceCount$. For each redundancy
component, a distinct set of IDLists is created. Each IDList entry for nodes
belonging to a redundancy component $rc$ is stored in the set of IDLists for
$rc$. The IDLists also include additional entries that represent nested
redundancy components. These additional entries, called dummy nodes, have the
same ID as the root node of the represented nested redundancy component
$rc_{nested}$ and are only added to IDLists of keywords contained in $rc_{nested}$.
Fig.~\ref{fig:idcluster_idlists} shows the IDLists created for the keywords
\textit{USA} and \textit{English}. Dummy nodes are the entries at the positions
2 and 4 in $L^{rc0}_{USA}$ and positions 2 and 4 in $L^{rc0}_{English}$.

\begin{figure}[htb]
	\centering
	\includegraphics[width=\linewidth]{ex_idcluster_idlists_cropped}
	\caption{Created IDLists for the keywords \textit{USA} and \textit{English} as part of an IDCluster.}
	\label{fig:idcluster_idlists}
\end{figure}

The dummy nodes are added to the redundancy component pointer map (RCPM). The
key of each entry in the RCPM is the ID of the respective dummy node. Each
entry contains the identifier of the redundancy component which the dummy node
is representing and an offset. The offset is given by the offset edge between $rc$
and $rc_{nested}$, or +0 if the edge between $rc$ and $rc_{nested}$ is not an
offset edge. Fig.~\ref{fig:idcluster_rcpm} shows the RCPM of the IDCluster. Note that only one RCPM is required, no matter how many keywords are indexed.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.32\linewidth]{ex_idcluster_rcpm_cropped}
	\caption{Created redundancy component pointer map (RCPM) as part of an IDCluster.}
	\label{fig:idcluster_rcpm}
\end{figure}

\subsection{Search}

\subsubsection{SLCA computation}

The main idea for SLCA computation is to utilize the base algorithms for
searching each redundancy component individually. Due to the additionally added
dummy nodes, any SLCA which is found in a redundancy component and is not a
dummy node, is also SLCA in the original tree. SLCA, which are dummy nodes,
indicate that more SLCA are inside the redundancy component, which the dummy
node is representing. This way, all redundancy components containing SLCA can be
searched dynamically starting at the root redundancy component. The offset
values stored in the RCPM are used for recalculating the original ID of SLCA
contained in nested redundancy components.

The basic search algorithm for IDCluster is an extension of FwdSLCA
\cite{setintersection2} and is depicted in Fig.~\ref{algo:dagfwdslca}.
The algorithm starts searching in the redundancy component with the ID 0, which
by definition is the redundancy component containing the document's root
node. In lines \ref{line:startfwdslca}-\ref{line:endfwdslca} the procedure
DagFwdSLCA performs an SLCA search similar to FwdSLCA on one redundancy component.
In lines \ref{fwdslca:start}-\ref{fwdslca:end} the results from this redundancy
component are processed. To check whether an SLCA is a dummy node, the SLCA is
looked up in the RCPM in line \ref{fwdslca:checkrcpm}. If the SLCA is a dummy
node, more SLCA can be found in the nested redundancy component. Therefore, the
nested redundancy component is searched recursively in
line~\ref{fwdslca:recursion} if it was not searched before. The results from
the nested redundancy component are now modified by the offset and added to the
SLCA list in lines~\ref{fwdslca:replace}-\ref{fwdslca:addend}. Note that in
line~\ref{fwdslca:replace} the dummy node is deleted from the SLCA list by
replacing it with an actual SLCA contained in the nested redundancy component.
The only exception to this proceeding is when the SLCA list contains only the
root node of the current redundancy component. This is a special case since an
RCPM lookup would return dummy node information (the dummy node and the root
node of the nested redundancy component have the same ID) and cause an infinite loop.

\begin{figure}
\begin{algorithmic}[1]
\State \Call{DagFwdSLCA}{$IDCluster$,0}
\Statex
\Procedure{DagFwdSLCA}{$IDCluster$,$rc_{cur}$}
\State $IDLists \longleftarrow$ $IDCluster$.getIDLists($rc_{cur}$)
 \While{$\neg$ EoL($IDLists$)}\label{line:startfwdslca}
  \State $v \longleftarrow$ \Call{fwdGetCA}{$IDLists$}\label{line:fwdgetca}
  \If{$v \neq null$}
   \If{$u \neq null$ $\wedge$ $v$.parent $\neq u$}
    \State $SLCA[rc_{cur}]$.add($u$)
   \EndIf
   \State $u \longleftarrow v$
   \State \Call{advance}{$IDLists$}
  \EndIf
 \EndWhile
\If{$u \neq null$}
  $SLCA[rc_{cur}]$.add($u$)
\EndIf \label{line:endfwdslca}
\If{$SLCA[rc_{cur}][0] = IDLists[0].getID(0)$}\label{fwdslca:start}\label{fwdslca:root}
 \Return
\EndIf
\State $size \longleftarrow SLCA[rc_{cur}].$size
\For{$i\gets 0,size$}\label{fwdslca:startfor}
 \State $slca \longleftarrow SLCA[rc_{cur}][i]$
 \If{$slca \in IDCluster.RCPM$}\label{fwdslca:checkrcpm}
  \State $rc_{nes} \longleftarrow IDCluster$.getPointer($slca$)
  \State $os \longleftarrow IDCluster$.getOffset($slca$)
  \If{$\neg done[rc_{nes}]$}
   \State \Call{DagFwdSLCA}{$IDCluster$,$rc_{nes}$}\label{fwdslca:recursion}
  \EndIf
  \State $SLCA[rc_{cur}][i]$ $\longleftarrow$ $SLCA[rc_{nes}][0] + os$\label{fwdslca:replace}
  \ForAll{$slca_{nes} \in  SLCA[rc_{nes}] \setminus SLCA[rc_{nes}][0]$}\label{fwdslca:addstart}
   \State $SLCA[rc_{cur}]$.add($slca_{nes} + os$)
  \EndFor\label{fwdslca:addend}
 \EndIf
\EndFor \label{fwdslca:end}\label{fwdslca:endfor}
\State $done[rc_{cur}] \longleftarrow $true
\EndProcedure
\Statex
\Function{EoL}{$IDLists$}
 \ForAll{$IDList \in IDLists$}
  \If{$IDList.C_i \geq IDList.length$}
   \State \Return true
  \EndIf
 \EndFor
 \State \Return false
\EndFunction
\Statex
\Procedure{advance}{$IDLists$}
 \ForAll{$IDList \in IDLists$}
  \State $IDList.C_i \longleftarrow IDList.C_i$+1
 \EndFor
\EndProcedure
\end{algorithmic}
\caption{Alternative SLCA search algorithm for redundancy components}\label{algo:dagfwdslca}
\end{figure}

If we consider our example, a search for the keywords \textit{USA}
and \textit{English} starts with the call of the main algorithm for the root
redundancy component $rc_0$. In lines \ref{fwdslca:start}-\ref{fwdslca:end},
node 4 and node 11 are calculated as the SLCA results for this redundancy
component. In the first iteration of the loop in lines
\ref{fwdslca:startfor}-\ref{fwdslca:endfor}, node 4 is identified as a dummy
node (line~\ref{fwdslca:checkrcpm}). As there are no results yet for the nested
redundancy component, $rc_1$ is searched recursively now. In $rc_1$, the only
SLCA result is node 5. Since node 5 is not found in the RCPM
(line~\ref{fwdslca:checkrcpm}), the SLCA result list for $rc_1$ remains
unchanged and the recursive call terminates. Back in the parenting recursion
for $rc_0$, inside the SLCA result list, the dummy node 4 is replaced with the
first result of the nested redundancy component, increased by the offset, 5+0=5
in line~\ref{fwdslca:replace}. Since no more SLCA results exist in $rc_1$, the
loop in lines~\ref{fwdslca:addstart}-\ref{fwdslca:addend} is skipped. In the
next iteration of the outer loop, node 11 is identified as a dummy node in
line~\ref{fwdslca:checkrcpm}. The nested redundancy component is once again
$rc_1$, for which at this point results already exist. Therefore, $rc_1$ is not
searched again and the dummy node is replaced by the SLCA result from $rc_1$
increased by the offset given by the RCPM, 5+7=12. At this point, the outer loop
terminates, and with it, the algorithm terminates, while the SLCA result list for $rc_0$ contains node 5 and node 12 as the final result.

One advantage of this approach is that the algorithm given by Zhou et al. is
integrated as unmodified module. This means our approach will benefit from any improvements made to the base algorithm, like the parent skipping introduced in BwdSLCA or the improved binary search introduced in BwdSLCA+.

\subsubsection{ELCA computation}

ELCA search can be implemented in a similar manner, which is shown in Figure~\ref{algo:dagfwdelca}.
Lines~\ref{fwdelca:same_start}-\ref{fwdelca:same_end} are similar to the
algorithm given by Zhou et al. \cite{setintersection2}. The following lines are
adopted from the DagFwdSLCA algorithm. Note that a redundancy component can
contain multiple ELCA, even when the root is ELCA. So, if
the first ELCA is the root, the first ELCA is just skipped in
line~\ref{fwdelca:skipfirst} instead of aborting the whole function call as in DagFwdSLCA.

\begin{figure}
\begin{algorithmic}[1]
\State \Call{DagFwdELCA}{$IDCluster$,0}
\Statex
\Procedure{DagFwdELCA}{$IDCluster$,$rc_{cur}$}
\State $IDLists \longleftarrow$ $IDCluster$.getIDLists($rc_{cur}$)\label{fwdelca:same_start}
 \While{$\neg$ EoL($IDLists$)}
  \State $v \longleftarrow$ \Call{fwdGetCA}{$IDLists$}
  \If{$v \neq null$}
   \While{$\neg S$.empty $\wedge$ $ S.$top $\neq v.$parent}
    \State \Call{ProcessStackEntry}{}
   \EndWhile
   \State $S$.push($v$)
  \Else
   $ $ break
  \EndIf
  \State \Call{advance}{$IDLists$}
 \EndWhile
 \While{$\neg S$.empty}
  \State \Call{ProcessStackEntry}{}
 \EndWhile  \label{fwdelca:same_end}
\State $start \longleftarrow 0$
\If{$ELCA[rc_{cur}][0] = IDLists[0].getID(0)$}\label{fwdelca:start}\label{fwdelca:root}
 \State $start \longleftarrow 1$\label{fwdelca:skipfirst}
\EndIf
\State $size \longleftarrow ELCA[rc_{cur}].$size
\For{$i\gets start,size$}
 \State $elca \longleftarrow ELCA[rc_{cur}][i]$
   \If{$elca \in IDCluster.RCPM$}
    \State $rc_{nes} \longleftarrow IDCluster$.getPointer($elca$)
    \State $os \longleftarrow IDCluster$.getOffset($elca$)
    \If{$\neg done[rc_{nes}]$}
     \State \Call{DAGFwdELCA}{$IDCluster$,$rc_{nes}$}
    \EndIf
    \State $ELCA[rc_{cur}][i]$ $\longleftarrow$ $ELCA[rc_{nes}][0] + os$\label{fwdelca:replace}
    \ForAll{$elca_{nes} \in  ELCA[rc_{nes}] \setminus ELCA[rc_{nes}][0]$}\label{fwdelca:addstart}
     \State $ELCA[rc_{cur}]$.add($elca_{nes} + os$)
    \EndFor\label{fwdelca:addend}
   \EndIf
\EndFor
\State $done[rc_{cur}] \longleftarrow $true
\EndProcedure
\end{algorithmic}
\caption{Alternative ELCA search algorithm for redundancy components.}\label{algo:dagfwdelca}
\end{figure}

In a search for \textit{USA} and \textit{English}, the ELCA nodes found in
$rc_0$ are 2, 4 and 11. Node 2 is not in the RCPM and therefore a final ELCA.
Node 4 is a dummy node and forces a search in $rc_1$. The ELCA list in $rc_1$
contains node 5 only. Therefore, node 4 in the ELCA list of $rc_0$ is replaced
with 5 plus the offset 0. Node 11 is also a dummy node pointing to $rc_1$.
Since $rc_1$ was already searched, node 11 in the ELCA list of $rc_0$ is
replaced with 5 plus the offset 7. Therefore, the final ELCA results are 2, 5,
and 12.

\section{Evaluation}\label{sec:eval}

To test the performance of this paper's algorithms, comprehensive
experiments were run. The experiments focus on the comparison
between the base algorithms and their respective DAG variants introduced in this
paper. An evaluation of the base algorithms showing their
superior performance in comparison to other classes of keyword search
algorithms can be found in the original papers \cite{setintersection}\cite{setintersection2}.

\subsection{Setup}

All experiments were run on a Xeon E5-2670 with 256GB memory and Linux OS. The
algorithms were implemented in Java 1.6.0\_24 and executed using the OpenJDK
64-Bit Server VM. The time results are the averages of 1,000 runs
with warm cache.

The XML version of the music database
discogs.com\footnote{http://www.discogs.com/data/} is used as testdata. It
contains 4.2 million records of music releases of a size of 12.6GB.
To evaluate the effects of different database
sizes, smaller file sizes are created by successivly removing the second
half of the set of all remaining records. Thereby, additional databases
having the sizes of 0.8GB/1.6GB/3.3GB/6.5GB are created.

For the evaluation, 3 categories of querys are proposed:

\begin{itemize}
\item Category 1: Queries consisting of nodes that will not be compressed in a
DAG. DAG-based algorithms cannot exploit these
kinds of queries.
Since the DAG-based algorithms still need time for verifying the
absence of RC-Pointers (nodes with entries in the RCPM), they should have worse performance than the base algorithms.
\item Category 2: Queries consisting of nodes that will be compressed in a
DAG, but having common ancestors (CA) which still cannot
be compressed.
This means that all results will be in the first redundancy component.
DAG-based algorithms can exploit the fact that the IDLists for
the first redundancy can be shorter than the IDLists for the base algorithms. On
the other hand, the absence of all RC-Pointers still has to be
verified.
These advantages and disadvantages might cancel each other depending
on the situation.
\item Category 3: Queries with results that can be compressed in a
DAG.
This means that there has to be at least a second redundancy component
containing all keywords. DAG-based algorithms should have a
better performance than the base algorithms for queries from this category.
\end{itemize}

Queries of different lengths for all categories are selected randomly using the
200 most frequent keywords. The selected queries are shown in
Table~\ref{table:queries}. Table~\ref{table:queryproperties} shows
the properties of these queries. The columns \textbf{CA}, \textbf{ELCA} and
\textbf{SLCA} show the total number of CA-, ELCA- or SLCA-nodes respectively.
The columns \textbf{S$_{ca}$}, \textbf{S$_{elca}$} and \textbf{S$_{slca}$} show
the savings by DAG compression, e.g. a total number of 100 CA and
80\% CA savings imply that 20 CA are left in the XML tree after
DAG compression.
The properties of the used keywords can be found in
Table~\ref{table:keywords}.
The column \textbf{nodes} shows the number of nodes directly containing the respective keyword; the column \textbf{path} shows the number of nodes directly or indirectly containing the keyword. The columns S$_{nodes}$ and S$_{path}$ accordingly show the compression savings.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|l|}
\hline
\textbf{query}  & \textbf{category} & \textbf{length} & \multicolumn{1}{c|}{\textbf{keywords}} \\ \hline \hline
Q1 & \multirow{3}{*}{1} & 2 & image uri \\ \cline{1-1} \cline{3-4}
Q2 &  & 3 & image uri release \\ \cline{1-1} \cline{3-4}
Q3 &  & 4 & image uri release identifiers \\ \hline \hline
Q4 & \multirow{3}{*}{2} & 2 & vinyl electronic \\ \cline{1-1} \cline{3-4}
Q5 &  & 3 & vinyl electronic 12" \\ \cline{1-1} \cline{3-4}
Q6 &  & 4 & vinyl electronic 12" uk \\ \hline \hline
Q7 & \multirow{3}{*}{3} & 2 & description rpm \\ \cline{1-1} \cline{3-4}
Q8 &  & 3 & description rpm 45 \\ \cline{1-1} \cline{3-4}
Q9 &  & 4 & description rpm 45 7" \\ \hline
\end{tabular}
\end{center}
\caption{Queries for evaluation.}\label{table:queries}
\end{table}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\textbf{query} & \textbf{CA } & \textbf{S$_{ca}$} & \textbf{ELCA } & \textbf{S$_{elca}$} & \textbf{SLCA } & \textbf{S$_{slca}$} \\ \hline \hline
Q1 & 14818739 & 0\% & 7697608 & 0\% & 7697603 & 0\% \\ \hline
Q2 & 3560569 & 0\% & 3560568 & 0\% & 3560567 & 0\% \\ \hline
Q3 & 1299279 & 0\% & 1299278 & 0\% & 1299277 & 0\% \\ \hline \hline
Q4 & 824063 & 0\% & 823952 & 0\% & 823840 & 0\% \\ \hline
Q5 & 616919 & 0\% & 616907 & 0\% & 616905 & 0\% \\ \hline
Q6 & 207865 & 0\% & 207864 & 0\% & 207863 & 0\% \\ \hline \hline
Q7 & 3438507 & 78\% & 709713 & 98\% & 703949 & 99\% \\ \hline
Q8 & 2389299 & 78\% & 486093 & 98\% & 481211 & 99\% \\ \hline
Q9 & 1307891 & 73\% & 328419 & 99\% & 328386 & 99\% \\ \hline
\end{tabular}\end{center}
\caption{Properties of queries.}\label{table:queryproperties}
\end{table}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\textbf{keyword} & \textbf{path} & \textbf{S$_{path}$} & \textbf{nodes} & \textbf{S$_{nodes}$} \\ \hline \hline
image & 14862218 & 0\% & 7716896 & 0\% \\ \hline
uri & 22521466 & 0\% & 7699158 & 0\% \\ \hline
release & 4788936 & 9\% & 4447144 & 3\% \\ \hline
identifiers & 2845185 & 6\% & 1422641 & 12\% \\ \hline
vinyl & 9088129 & 72\% & 2343810 & 97\% \\ \hline
electronic & 5305014 & 66\% & 1773128 & 99\% \\ \hline
12" & 3976817 & 77\% & 812587 & 97\% \\ \hline
uk & 1753528 & 50\% & 872902 & 95\% \\ \hline
description & 36872585 & 76\% & 12774491 & 92\% \\ \hline
rpm & 3460698 & 78\% & 715987 & 98\% \\ \hline
45 & 2524740 & 76\% & 531299 & 95\% \\ \hline
7" & 3371487 & 77\% & 689983 & 97\% \\ \hline
\end{tabular}
\end{center}
\caption{Properties of keywords.}\label{table:keywords}
\end{table}

\subsection{Experiment I: Category}

In the first experiment, the performance of the base algorithm FwdSLCA
is compared to the DAG-based algorithm DagFwdSLCA. Database size
and query length are fixed, while the category is altered. The results are shown
in Fig.~\ref{eval:class}.

\begin{figure}[htb]
	\centering
	\includegraphics[width=0.5\linewidth]{klasse_cropped}
	\caption{Comparison with different categories. (database size:
	12.6GB; query length: 3)}
	\label{eval:class}
\end{figure}

The results confirm that in Category 1, the performance of the
DAG-based algorithm is a bit worse than the performance of the
base algorithm. This is as expected, since there are no redundancies which can
be exploited by a DAG-based algorithm, but
the DAG-based algorithm has a certain overhead for verifying that
no further redundancy components needs to be searched, resulting in a worse
performance. In Category 2, the performance of both algorithms is very
similar with the base algorithm being slightly faster. The better relative
performance of the DAG-based algorithm can be traced back to the
IDLists being shorter than the IDLists used in the base algorithm.
Finally, in Category 3, the DAG-based algorithm is more than
twice as fast as the base algorithm.

\subsection{Experiment II: Query length}

In this experiment, the length of the queries is modified.
Fig.~\ref{eval:length} shows the results for categories 1 and 3
with a fixed database size.

\begin{figure}[htb]
	\centering
	\includegraphics[width=\linewidth]{schluesselworte_cropped}
	\caption{Comparison with different query lengths. (database size:
	12.6GB)}
	\label{eval:length}
\end{figure}

The general tendency is the same: The base algorithm is a bit better for
Category 1 queries, while the DAG-based algorithms are better for
Category 3 queries. The Category 1 results suggest that the gap between both
algorithms get smaller the more keywords are used. This is plausible, since the
overhead for the DAG-based algorithms depends on the amount of
results.
Adding more keywords to a query can reduce the amount of results, but never
increase it (see Table~\ref{table:queryproperties}).

\subsection{Experiment III: Database size}

The third experiment examines the effects of database size and is shown in
Fig.~\ref{eval:size} for Category 1 and Category 3 with a fixed query
length.

\begin{figure}[htb]
	\centering
	\includegraphics[width=\linewidth]{dateigroesse_cropped}
	\caption{Comparison with different database sizes. (query length:
	3)}
	\label{eval:size}
\end{figure}

The exponential growth of the database size leads to an exponential growth
in the search time for both algorithms. Minor changes in the proportions between
both algorithms can be traced back to minor changes in the keyword frequencies
and compression savings. Therefore, the database size seems not to have
a direct impact on the performance ratio between base algorithm and
DAG-based algorithm.

\subsection{Experiment IV: Algorithm}

In the last experiment, algorithms FwdSLCA, BwdSLCA+, FwdELCA and BwdELCA as
proposed by Zhou et al. are compared to their DAG-based variants.
Database size and query length are fixed.

\begin{figure}[htb]
	\centering
	\includegraphics[width=\linewidth]{algorithmus_cropped}
	\caption{Comparison with different algorithms. (database size:
	12.6GB, query length: 3)}
	\label{eval:algorithms}
\end{figure}

For Category 1, the DAG-based algorithms always have a small
overhead independent of the algorithm. In Category 3, the
relative difference is smaller for backward algorithms, but still significant.
Backward search performs generally better than forward search of the same type.
The only exceptions are the DAG-based variants of
FwdSLCA and of BwdSLCA+ in Category 3. The backward algorithm is actually
slower.
This result suggests that a major part of the speedup in BwdSLCA+ is generated
by parent skipping. Due to the DAG compression many of the cases
in which parent skipping provides benefits are already optimized.

\subsection{Index Size}

The size of the IDCluster differs from the size of IDLists in two aspects.
On the one hand, additional space is required for storing the RCPM. On the other hand, less space is required for storing the IDLists due to DAG compression.

The RCPM can be stored in different ways which affect the required memory space and the time performance. In this evaluation, the RCPM is stored as an array containing the redundancy component identifier and the offset. The node ID is implicitly represented by the position in the array. The size of the array has to be big enough to contain all node IDs. This way of storing the RCPM is optimized for time performance.

The DAG compression strongly depends on the XML database used. The additionally created dummy nodes also have to be considered.

In a typical use case, both effects, additional memory for RCPM and
reduced memory due to DAG compression, are likely to cancel each other.

In the Discogs database, the total amount of nodes in
the IDLists index is 3.9 billion. Considering the 2 (3) integers per node
required for performing an SLCA (ELCA) search and an integer size of 4
byte, the total IDLists index sums up to 28.7GB (43.0GB). The amount of nodes in
an IDCluster is only 3.0 billion for the same database. Storing these nodes sums
up to 22.5GB (33.7GB) for SLCA (ELCA) search. However storing the RCPM in an array
as described above (with redundancy component identifier and offset both as 4
byte integer) for all 656 million distinct nodes requires an additional 4.9GB.
So, the total memory required for the IDCluster is 27.3GB (38.6GB) for SLCA (ELCA) search.

\section{Related Work}\label{sec:relatedwork}

There exist several approaches that address the problem of keyword search in
XML. These approaches can be roughly divided into two categories: approaches
that enhance the quality of the search results by considering the semantics of
the queries on the one hand, and approaches that enhance the performance
of the computation of the set of query results on the other hand.

Within the first category, XSEarch \cite{xsearch} presents a query
semantics that returns only those XML fragments, the result nodes of which
are \textit{meaningfully related}, i.e., intuitively belong to the same entity.
In order to check this, they examine whether a pair of result
nodes has two different ancestor nodes that have the same label (e.g., two nodes
with label ``author'', s.th. the first keyword belongs to author1
and the second one to author2).

\cite{xrank} not only focusses on an efficient, stack-based algorithm for
keyword search based on inverted element lists of the node's DeweyIDs, but also
aims to rank the search results in such a way, that the user
gets the (probably) most interesting results prior to the other results. SUITS \cite{demidovasuits} is a
heuristics-based approach, and the approach presented in
\cite{petkova2009refining} uses probabilistic scoring to rank the query results.
In order to enhance the usability, \cite{li2010suggestion} and
\cite{koutrika2009data} propose an approach on how to group the query results by
category.

Within the second category (efficient result computation) most approaches are
based on finding a set of SLCA (or ELCA) nodes for all
matches of a given keyword list.

Early approaches were computing the LCA for a set of given keywords on the fly.
\cite{schmidt2001querying} proposes the meet-operator that computes the
LCA for a pair of nodes that match two query strings without requiring additional
knowledge on the document structure from the user.

In contrast, recent approaches try to enhance the query performance by using a
pre-computed index.

\cite{florescu2000integrating} proposes an extension of the XML query
language XML-QL by keyword search. In order to speed-up the keyword search,
it computes the so-called ``inverted file'' for the XML
document -- a set of inverted element lists -- and stores the contents
within a relational database.

\cite{mlca} presents two approaches to compute the Meaningful Lowest
Common Ancestor (MLCA), a concept similar to the SLCA considered in our
approach. Its first approach allows computing the MLCA with the
help of standard XQuery operations, whereas its second approach
is a more efficient approach that is based on a stack-based algorithm for structural joins.

Similar to XRANK \cite{xrank} is the stack-based approach presented in
\cite{stacklca}. In contrast to the previous stack-based appraoches, the authors
do not used the DeweyID to identify a node and to calculate the
ancestor-descendant or even parent-child relationships, but they propose to use
a combination of preorder position, postorder position, and depth of the node.

XKSearch \cite{xksearch} is an indexed-based approach to compute the LCA. They
store inverted element lists consisting of DeweyIDs of the nodes. They start
searching for the results at node $n$ of the shortest relevant keyword list, and
they check for the other keyword lists whether the node $l$ being the next node
to the left of $n$ or the node $r$ being the next node to the right of $n$ has a
smaller distance to $n$. Then, they use $n$ and the nearest node ($l$ or $r$) to
compute the LCA.

\cite{multiway} presents an anchor-based approach to compute the SLCA. From the
set of current nodes of each relevant keyword list, they search the so-called
anchor, i.e., that node that is closest to all current nodes. As soon as an
anchor is identified, they try to exchange each node $n_i$ of each other keyword
list $L_i$ by the next node next($n_i$) of $L_i$, in order to check, whether
next($n_i$) is closer to the anchor than $n_i$ and whether next($n_i$) defines a
new anchor.
Finally, the set of anchor nodes form the set of LCA candidates that do not
have another LCA candidate child is then reduced to the set of SLCA nodes.

JDeweyJoin \cite{jdewey} returns the top-k most relevant
results. They compute the results bottom-up by computing a kind of join on the
list of DeweyIDs of the nodes in the inverted element list. Whenever they find a
prefix that is contained in all relevant element lists, the node with this
prefix as ID is a result candidate. In addition, they use a weight function to
sort the list entries in such a way, that they can stop the computation after k
results, returning the top-k most relevant results.

\cite{setintersection} and \cite{setintersection2} belong to the
intersection-based approaches. They present a more efficient, but more
space-consuming approach. The elements of their inverted element lists do not
only contain the nodes that have the keyword as label, but also contain all
ancestor-nodes of these nodes, and for each node, the inverted element lists
contain the ID of the parent node. Therefore, they can compute the SLCAs by intersecting the inverted
element lists of the keywords and by finally removing each result
candidate, the descendant of which is another result candidate.

Like the contributions of the second category, our paper focuses on efficient
result computation. It follows the idea of the intersection-based approaches.
However, different from all other contributions and similar to a prior
approach \cite{boettcher}, instead of computing an XML-index, we compute a DAG-Index.
This helps to compute several keyword search results in parallel, and thereby
speeds-up the SLCA computation. To the best of our knowledge, DAG-Index is the
first approach that improves keyword search by using XML compression before
computing the search index.

\section{Conclusions}\label{sec:conclusions}

We have presented IDCLuster, an indexing and search technique that shares
common sub-trees in order to index and to search redundant data only once.

As our performance evaluation shows, using the DAG-based index of
IDCluster, the intersection-based keyword search algorithms can be significantly
improved, i.e., gain a speed-up up to a factor of more than 2.

Therefore, we consider the idea to cluster repeated data collections to be
a significant contribution to all applications that have to search in large
data collections with high amounts of copied, backed-up or redundant data.

\section*{Acknowledgments}

We would like to thank Wei Wang for helpful discussions and comments during our
project cooperation.

This work has been supported by DAAD under project ID 56266786.

\bibliographystyle{IEEEtran}