\documentclass{scrartcl}
\usepackage[margin=1in, left=0.7in, right=0.7in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{hyperref}
%\renewcommand{\familydefault}{\sfdefault}
\usepackage{times}

\def\title#1{\gdef\@title{#1}\gdef\THETITLE{#1}}
\def\author#1{\gdef\@author{#1}\gdef\THEAUTHOR{#1}}
\def\date#1{\gdef\@title{#1}\gdef\THEDATE{#1}}
\newcommand{\psql}{\textsc{PostgreSQL}}
\newcommand{\res}[1]{ \\ \mbox{~} \hfill \emph{(#1 résultats)} \pagebreak[3]\\ }
\fancyhead[L]{\textsc{Bases de données -- td 4}}
\fancyhead[R]{{\THETITLE}} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{{\THEAUTHOR}}
\fancyfoot[R]{{\THEDATE}}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0.5pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%%%%solution/print = true % uncomment for tutors
}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\title{Complexité des langages de requête}
\author{Pierre Senellart \& Louis Jachiet}
\date{14 mars 2018}

\begin{document}
\pagestyle{fancy}

\begin{center}
\Huge  \THETITLE
\end{center}

\emph{Le but de ce TD est de se familiariser avec les preuves de complexité des
langages de requête.}



\section*{Rendu}

Le rendu de ce TD doit être fait sur le moodle, avant 23\string:59 le
17 mars en fournissant un fichier PDF contenant une version
électronique, des scans ou des photographies \emph{lisibles} de vos
réponses au TD.  Des pénalités seront comptées en cas de rendu tardif
(0,5 point par heure de retard). Les exercices sont par difficulté
croissante, il n'est pas nécessaire de finir tous les exercices de
la fiche de TD pour avoir une bonne note.

\section{Unions de requêtes conjonctives}
On considère le langage $\mathcal{L}$ des requêtes composées d'unions
de requêtes conjonctives.

\vfill
\begin{question}
  Quelle est la complexité en données du langage $\mathcal{L}$ ?

\hfill  \emph{C'est à dire, étant donné une requête $\mathcal{Q}\in\mathcal{L}$ fixée,
    quelle est la complexité du problème $\{ (x,D) ~|~ x\in \mathcal{Q}(D)\}$ ?}
\end{question}

\vfill
\begin{question}
  Quelle est la complexité combinée du langage $\mathcal{L}$ ?
  
\hfill  \emph{C'est à dire, 
    quelle est la complexité du problème $\{ (x,D,\mathcal{Q}) ~|~ x\in \mathcal{Q}(D)\}$ ?}
\end{question}

\section{$\alpha$-acyclicité}

\begin{question}
  Montrer qu'une requête conjonctive $\alpha$-cyclique peut devenir
  $\alpha$-acyclique quand un atome est ajouté à la requête.
\end{question}

\vfill
\begin{question}
Donner une caractérisation plus simples des requêtes conjonctives
    $\alpha$-acycliques sur les schémas relationnels dont toutes les
    relations sont d'arité $\leq 2$. Prouver l'équivalence de cette
    caractérisation avec la définition des requêtes $\alpha$-acycliques.
\end{question}

\vfill
\section{FO+$\mu^+$ capture la parité en présence d'un ordre total}

On étend dans cet exercice la preuve de capture de parité du nombre
d'éléments d'un ordre total par FO+$\mu^+$ à un cadre un peu plus
général.

On considère un schéma relationnel arbitraire contenant une relation
$n$-aire $R$. On considère la requête~$Q$: \og $R$ contient un nombre pair
de tuples.\fg

\vfill

\begin{question}
 Montrer (sans utiliser le théorème de Fagin !) que $Q$ peut
    s'exprimer en logique du second ordre existentielle.
\end{question}

\vfill
\begin{question}
 On suppose un ordre total sur les constantes du domaine, et que
    la base de données contient une relation $S$ qui, pour toute base de
    données, contient la relation de \emph{successeur immédiat} pour cet
    ordre total. Montrer que $Q$ peut s'exprimer en FO+$\mu^+$.
\end{question}

\pagebreak[4]

\section{Datalog}

\begin{question}
Prouver que l'évaluation de Datalog est PTIME en complexité
en données.

\emph{Dans la complexité en données, le schéma des règles est fixé et
  donc l'arité des règles est fixé. Le nombre de constantes, lui, est
  borné par la taille de l'entrée.}
\end{question}

\vspace{2em}
\begin{question}
Prouver que l'évaluation de Datalog est EXPTIME-complète en complexité
combinée, en montrant qu'on peut simuler l'exécution d'une machine de
Turing déterministe en $O(n^k)$ pour une certaine constante $k$ par un
programme Datalog.

\emph{Suggestion : vous pouvez partir du problème $\{(M,x,T)~:~M(x)
  \mbox{ s'arrête en moins de } T \mbox{ étapes}\}$ qui est
  EXPTIME-complet et utiliser les règles Datalog suivantes ($t$ et $p$
  représentent des nombres en binaire inférieurs ou égaux à $T$):}
\begin{itemize}
\item $next(t,t')$ vrai quand $t'=t+1$ ;
\item $strictlyLess(t,t')$ vrai quand $t<t'$ 
\item $notEqual(t,t')$ vrai quand $t\neq t'$
\item $state(t,q)$ vrai quand la machine est dans l'état $q$ au temps $t$ ;
\item $position(t,p)$ vrai quand la tête de la machine est à la position $p$ au temps $t$ ;
\item $value(p,t,c)$ vrai quand la bande contient $c$ au temps $t$ à la position $p$.
\end{itemize}
\end{question}

\end{document}

