%% REWERSE Annual Meeting, I4, Extended Abstracts 2: 
%%   Efficient Querying with Xcerpt: Theory, Complexity, and Algorithms
%% Authors: Andreas Schroeder, Tim Furche

% The "draftcls", not "draft", option should be used if it is desired 
% that the figures are to be displayed in draft mode.
\documentclass[journal,10pt,a4paper,twoside]{styles/IEEEtranMOD}
\usepackage{styles/epigraph}
\lstset{float=tbp}

\newcommand{\optional}[1]{\textcolor{gray}{#1}}
\usepackage[utf8]{inputenc}
\hyphenation{} % Correcting TeX's
                                % hyphenation algorithm
  \lstset{basicstyle=\ttfamily\footnotesize,xleftmargin=3pt,xrightmargin=5pt}%

%% Frontmatter ---------------------------------------------------------
\title{Reusable Xcerpt: Principles and Exemplars}

\author{Jakob Henriksson, Uwe A\ss{}mann, Fran\c{c}ois Bry, Tim Furche, Benedikt Linse% <-This % stops a space
\thanks{This research has been funded by the European Commission and
  by the Swiss Federal Office for Education and Science within the 6th
  Framework Programme project REWERSE number 506779
  (cf. \protect\url{http://www.rewerse.net/}).\vspace*{-5cm}}%
% \revisions{
%   \revision{1) initial draft}{January 24\sup{th}}{derived from deliverable I4-D6, incomplete}  
%   \revision{2) restructuring}{January 29\sup{th}}{grouping and
%   aggregation to separate report}
%   \revision{3) revised draft}{January 31\sup{th}}{input for graduate class}
%   \revision{4) revised draft}{February 1\sup{st}}{revision based on
%     feedback from Andreas and Benedikt}
  %\revision{5) revised draft}{February 3\sup{rd}}{revision based on team discussion}
  %\revision{6) final}{February 3\sup{rd}}{final draft}
%  }% <-this % stops a space
}%

% Paper headers:
\makeatletter
\markboth{Henriksson \MakeLowercase{\textit{et al.}}: Reusable Xcerpt: Principles and Exemplars. 2006}{Henriksson \MakeLowercase{\textit{et al.}}: Reusable Xcerpt: Principles and Exemplars. 2006}
\makeatother

\begin{document}
\maketitle

\begin{abstract}
  ...
\end{abstract}

\begin{keywords}
  reuse, composition, Xcerpt, aspect-oriented programming, query components
\end{keywords}

%% Mainmatter ---------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Introduction}

- resuability critical for practical success
- general applicability for rule languages
- query language Xcerpt as use case
- applicability to languages such as XQuery?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Principles}
[Jakob]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Related Work}

possibly work on modular logic programming

Ianni et al. propose in

\cite{Ianni2004Answer-Set-Programming-with-Templates} ``templates'' as
a reuse concept for answer-set programming languages. Templates are
sets of rules and facts that can contain formal predicates. Formal
predicates are declared in the template header (including their arity)
and instantiated with actual predicates in the template call (called
``template atom'' in
\cite{Ianni2004Answer-Set-Programming-with-Templates}). The template
header also specifies the number $n$ of parameter terms that are used
to interface with the template: In the template call, an output list
of size $n$ must be given that consists either of variables or
constants and is used to instantiate occurrences of parameter terms in
the template. A program with templates is realized by rewriting the
program to a template-free program replacing template calls with
instantiated definitions of the corresponding template.
\cite{Ianni2004Answer-Set-Programming-with-Templates} also discusses
cycles in template programs: They prove the intuitive property that
template programs with acyclic dependency graph over template and
templates call always terminate. It is equally intuitive that the
resulting program is at most polynomially larger than the size of the
template program and the template definitions, more precisely
$O(|\mathit{templates}| \times |\mathit{templates}| +
|\mathit{program}|)$. Therefore, ASP programs with templates have the
same expressiveness as programs with templates, though allowing more
succinct encodings. 

-> composition only at the level of sets of rules, no ``in-rule''
composition. Indeed, comparable to Generics/Templates in C++, whereas
reuse Xcerpt allows composition and parameterization of arbitrary
language components. ? maybe in practice limitations to make the
composition language ``fit'' ? 


clause-view approach in object-oriented logic programming,
cf. A. Davison ``A survey of logic programming-based object-oriented
languages'', 1993.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Exemplar: Parsing RDF/XML in Xcerpt}

[description of the following programs]
[introduction to RDF/XML]
[motivation]


\begin{lstlisting}
DECLARE
  ns-prefix rdf = "http://www.w3.org/1999/02/22-rdf-syntax-ns#"
  ns-prefix xml = "http://www.w3.org/XML/1998/namespace"
  ns-prefix rxmlp = "http://xcerpt.org/2004/rdf-xml-parser/"

  programHook *pHook
END
\end{lstlisting}

\texttt{rxmlp:document} is a view that merges all RDF/XML descriptions
that are to be normalized to RXR triples.

\subsection{Finding all RDF Subjects: Stripped Traversal of Document}
\begin{lstlisting}
# Top-Level Subjects
CONSTRUCT
  rxmlp:subject-element(origin=var Origin)[ idvar Subject ]
FROM
  rxmlp:document-collection{{
    rdf:RDF((xml:base=var Origin)) {{
      var Subject
    }}
  }}
END

# Recursion, subject-predicate-object nesting
CONSTRUCT
  rxmlp:subject-element(origin=var Origin)[ idvar OId ]
FROM
  and(
    rxmlp:document-collection{{
      rdf:RDF((xml:base=var Origin)) {{
        desc idvar OId @ *{{ }} 
      }}
    }},
    rxmlp:subject-element{
      *{{ # node already known to represent a subject resource
        *((without rdf:parseType="Literal", 
           without rdf:parseType="Resource"))
          {{ # predicate with child as object
            idvar OId @ *{{ }}
          }}
      }}
    }
  )
END

# Recursion, subject-predicate-object nesting where objects are blank
#  nodes and omitted using parseType "Resource"
CONSTRUCT
  rxmlp:subject-element(origin=var Origin)[ idvar OId ]
FROM
  and(
    rxmlp:document-collection{{
      rdf:RDF((xml:base=var Origin)) {{
        desc idvar OId @ *{{ }} 
      }}
    }},
    rxmlp:subject-element{
      *{{ # node already known to represent a subject resource
        idvar OId @ *((rdf:parseType="Resource")) {{ }} 
      }}
    }
  )
END
\end{lstlisting}

% ------------------------   
\subsection{From RDF/XML Elements to URIs}

\begin{lstlisting}
# regular URI reference
CONSTRUCT
  rxmlp:node2uri[ idvar Ident, uri[ var URI ] ]
FROM
  rxmlp:subject-element[
    idvar Ident @ *((rdf:about=var URI)){{ }}
  ]
END

# relative URI reference
CONSTRUCT
  rxmlp:node2uri[ idvar Ident, uri[ var Origin ++ "#" ++ var ID ] ]
FROM
  rxmlp:subject-element(origin=var Origin)[
    idvar Ident @ *((rdf:ID=var ID)){{ }}
  ]
END

# blank node with explicit identifier
CONSTRUCT
  rxmlp:node2uri[ idvar Ident, blank[ var Origin ++ "#" ++ var ID ] ]
FROM
  rxmlp:subject-element(origin=var Origin)[
    idvar Ident @ *((rdf:blankID=var ID)){{ }}
  ]
END

# blank node without explicit identifier
CONSTRUCT
  rxmlp:node2uri[ idvar Ident, blank[ var Origin ++ "#" ++ doc-uid(var Ident) ] ]
FROM
  rxmlp:subject-element(origin=var Origin)[
    idvar Ident @ *((without rdf:about=*,
         without rdf:nodeID=*,
         without rdf:ID=*)){{ }}
  ]
END
\end{lstlisting}

% ------------------------   
\subsection{Constructing Triples}


\subsubsection*{Objects as Elements}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ var OUriOrBlank ]
  ]
FROM
  and (
    rxmlp:subject-element[
      idvar SId @ *{{
        var P_NS:var P_LN((without rdf:parseType=*)){
          idvar OId @ *{{}}
        }
      }}
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ],
    rxmlp:node2uri[ idvar OId @ *{{ }}, var OUriOrBlank ],
  )
END
\end{lstlisting}

\subsubsection*{Objects as Literals}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    literal(optional xml:lang=var Language, 
            optional rdf:datatype= var DType)[ optional var Literal ]
  ]
FROM
  and( 
    rxmlp:subject-element[
      idvar SId @ *{{
        var P_NS:var P_LN((optional xml:lang=var Language,
                           optional rdf:datatype=var DType)){
          optional var Literal -> /.*/
        }
      }}
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}

\subsubsection*{Objects as Attributes}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ uri [ var OUri ] ]
  ]
FROM
  and(
    rxmlp:subject-element[
      idvar SId @ *{{
        var P_NS:var P_LN((rdf:resource=var OUri)){ }
      }}
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}

\subsubsection*{Properties as Attributes}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ literal(optional xml:lang=var Language)[ var Literal ] ]
  ]
FROM
  and(
    rxmlp:subject-element[
      idvar SId @ *((var P_NS:var P_LN=var Literal, 
                     optional xml:lang=var Languages)){{ }}
      where P_NS != "http://www.w3.org/1999/02/22-rdf-syntax-ns#" and
            P_NS != "http://www.w3.org/XML/1998/namespace"

    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}

\subsubsection*{Objects as XML Literals (\texttt{parseType} Literal)}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ literal(rdf:datatype="rdf:XMLLiteral")[ all var XMLLiterals ] ]
  ]
FROM
  and(
    rxmlp:subject-element[
      idvar SId @ *{{
        var P_NS:var P_LN((rdf:parseType="Literal")){{
           var XMLLiterals
        }}
      }}
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}

\subsubsection*{Property and Object Elements (omitting blank nodes,
  \texttt{parseType} Resource)}
\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ blank[ var OUriOrBlank  ] ]
  ]
FROM
  and(
    rxmlp:subject-element((origin=var Origin))[
      idvar SId @ *{{
        idvar OId @ var P_NS:var P_LN((rdf:parseType="Resource")){{  }}
      }}
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ],
    rxmlp:node2uri[ idvar OId @ *{{ }}, var OUriOrBlank ]
  )
END
\end{lstlisting}

% ------------------------   
\subsubsection*{Properties as Subject Attributes}

\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ literal[ var Literal ] ]
  ]
FROM
  and(
    rxmlp:subject-element((origin=var Origin))[
      idvar SId @ *((without rdf:resource=*, 
                    without rdf:parseType=*,
                    var P_NS:var P_LN = var Literal)) {{
      }} where P_NS != "http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}

% ------------------------   
\subsubsection*{Typed Node Elements}

\begin{lstlisting}
CONSTRUCT
  declare ns-default "http://xcerpt.org/2004/xrdf"
  triple [
    subject[ var SUriOrBlank ], 
    predicate[ uri [ ver P_NS ++ var P_LN ] ],
    object[ uri[ var SClassNS ++ var SClassLN ] ]
  ]
FROM
  and(
    rxmlp:subject-element((origin=var Origin))[
      idvar SId @ SClassNS:SClassLN((
                    without rdf:parseType="Resource")) {{
      }} where SClassNS != "http://www.w3.org/1999/02/22-rdf-syntax-ns#" and
               SClassLN != "Description"
    ],
    rxmlp:node2uri[ idvar SId @ *{{ }}, var SUriOrBlank ]
  )
END
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Exemplar: Reusable Transformation Queries}

[transformation rules]

``Change all attributes in the \element{xcerpt} namespace to children
of the corresponding element.''

\begin{lstlisting}
desc p((var Attr -> xcerpt:var ALocal=var AValue, delete var Attr)){{
      insert xcerpt:var ALocal{ var AValue }
}} 
\end{lstlisting}

\begin{lstlisting}
CONSTRUCT
  transform[var InputID, 
      result[var Label((all var NonXcerptAttribute))[[ 
           all xcerpt:var ALocal[ var AValue ],
           all var ChildResult ]] ]
  ]
FROM
  and (
    desc idvar InputID @ var Label((
           var NonXcerptAttribute ->var NS:*=*,
           xcerpt:var ALocal=var AValue))[[
             var Child -> idvar ChildID @ *{{ }}  
         ]] where NS != "http://xcerpt.org/"
    transform[var ChildID, var ChildResult]
  )
END
\end{lstlisting}

``Replace all \element{a} within \element{p} elements with
\element{link} elements.'' (two ways, second is more flexible, first
more efficient :-)).

\begin{lstlisting}
CONSTRUCT
  transform[var InputID, 
      result[link((all var Attribute))[[ all var ChildResult ]] ]
  ]
FROM
  and (
    desc p {{ 
         desc idvar InputID @ a((var Attribute))[[
           var Child -> idvar ChildID @ *{{ }}  
         ]] }},
    transform[var ChildID, var ChildResult]
  )
END

CONSTRUCT
  transform[var InputID, 
      result[all var ChildResult] ]]
  ]
FROM
  and (
    desc(!p)* idvar InputID @ var Label[[
           var Child -> idvar ChildID @ *{{ }}  
         ]],
    transform[var ChildID, var ChildResult],
  )
END
\end{lstlisting}


\begin{lstlisting}
CONSTRUCT
  transform[var InputID, 
      result[p((all var Attribute))[[ all var ChildResult ]] ]
  ]
FROM
  and (
    desc idvar InputID @ p((var Attribute))[[
        var Child -> idvar ChildID @ *{{ }}  
      ]] }},
    transform-within[var ChildID, var ChildResult]
  )
END

CONSTRUCT
  transform[var InputID, 
      result[all var ChildResult] ]]
  ]
FROM
  and (
    desc idvar InputID @ !/p/[[
           var Child -> idvar ChildID @ *{{ }}  
         ]],
    transform[var ChildID, var ChildResult],
  )
END

CONSTRUCT
  transform-within[var InputID, 
      result[link((all var Attribute))[[ all var ChildResult ]] ]
  ]
FROM
  and (
    desc idvar InputID @ a((var Attribute))[[
        var Child -> idvar ChildID @ *{{ }}  
      ]] }},
    transform-within[var ChildID, var ChildResult]
  )
END

CONSTRUCT
  transform-within[var InputID, 
      result[all var ChildResult] ]]
  ]
FROM
  and (
    desc idvar InputID @ !/a/[[
           var Child -> idvar ChildID @ *{{ }}  
         ]],
    transform-within[var ChildID, var ChildResult],
  )
END
\end{lstlisting}


``Remove all \element{p}'s by moving the children of each \element{p}
to its parent.''

\begin{lstlisting}
# Not p case ...
CONSTRUCT
  transform[var InputID, 
      result[var Label((all var Attribute))[[ all var ChildResult ]] ]
  ]
FROM
  and (
    desc idvar InputID @ var Label -> !/p/((var Attribute))[[
           var Child -> idvar ChildID @ *{{ }}  
         ]],
    transform[var ChildID, var ChildResult]
  )
END

# p case
CONSTRUCT
  transform[var InputID, 
      result[all var ChildResult] ]]
  ]
FROM
  and (
    desc idvar InputID @ p[[
           var Child -> idvar ChildID @ *{{ }}  
         ]],
    transform[var ChildID, var ChildResult],
  )
END
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
\section{Conclusion}


\bibliographystyle{IEEEtranS}
\bibliography{publications}

\end{document}

% Local Variables:
% fill-column: 90
% End;