praca.tex

\documentclass{pracamgr}

\usepackage{amsmath, amsfonts,amssymb,amsthm,epsfig,epstopdf,url,array,bm,color}

%\usepackage{polski}
%\usepackage[english,polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[OT4]{fontenc}

\usepackage{verbatim}
\usepackage{lmodern}
\usepackage[section]{placeins}
\usepackage[font=small]{caption}
\usepackage{color}
\usepackage[section]{placeins}
\usepackage{fancyvrb}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{clrscode3e}
\usepackage[percent]{overpic}
\usepackage{tikz}
\usepackage{varwidth}
\usetikzlibrary{arrows}
\usepackage{xspace}

%\overfullrule=2cm



\fvset{frame=single,framesep=1mm,fontsize=\scriptsize,numbers=left,framerule=.3mm,numbersep=1mm,commandchars=\\\{\}}
\definecolor{vdarkgray}{gray}{0.25}

% kindle page geometry (no page numbers)
%\usepackage[papersize={3.6in,4.8in},hmargin=0.1in,vmargin={0.1in,0.1in}]{geometry}
%\usepackage{microtype}     % microtypography, reduces hyphenation
 

\usepackage{program}
%\usepackage{tikz}
%\usetikzlibrary{arrows}

% Dane magistranta:

\author{Marek Rogala}

\nralbumu{277570}

\title{Declarative queries on large graphs and their distributed evaluation}

\tytulang{Deklaratywne zapytania na dużych grafach i ich rozproszone wyliczanie}

\kierunek{Computer Science}

\opiekun{dr Jacek Sroka\\
  Institute of Informatics\\
  }

\date{December 2014}

\dziedzina{ 
11.3 Computer Science\\ 
}

\klasyfikacja{Information Systems: Query languages}

% Słowa kluczowe:
%\keywords{Przetwarzanie dużych grafów, Deklaratywne języki zapytań, Obliczenia na dużych zbiorach danych, Datalog, SociaLite, Apache Spark, Hadoop.}
\keywords{Large graphs processing, Declarative query languages, Computations on large datasets, Datalog, SociaLite, Apache Spark, RDD, Hadoop, Pregel}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem*{cor}{Corollary}

\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{exmp}{Example}[section]

\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newtheorem*{note}{Note}
\newtheorem*{prof}{Proof}

\renewcommand\qedsymbol{$\blacksquare$}

\newcommand{\todo}[1]{\textcolor{red}{\fbox{TODO} #1}}
\newcommand{\pomysl}[1]{\textcolor{cyan}{\fbox{DO ROZWAŻENIA} #1}}

\newcommand{\datalogra}{Datalog$^{RA}$\xspace}
\newcommand{\datalogneg}{Datalog$^{\neg}$\xspace}
\newcommand{\aggfun}{\textit{aggfun}\xspace}
\newcommand{\aggcol}{\textit{aggcol}\xspace}
\newcommand{\assign}{:-}
\newcommand{\margp}[2]{{{\color{magenta} \emph{#1} \color{blue} #2}}}
\newcommand{\ps}{\mathcal{P} }

\def\changemargin#1#2{\list{}{\rightmargin#2\leftmargin#1}\item[]}
\let\endchangemargin=\endlist 

\newenvironment{centab}[1]{\begin{center}\begin{tabular}{#1}}{\end{tabular}\end{center}}

\newcommand*{\QEDA}{\hfill\ensuremath{\blacksquare}}

\newcommand{\edb}{\textit{edb}\xspace}
\newcommand{\idb}{\textit{idb}\xspace}
\newcommand{\inst}{\textit{inst}\xspace}
\newcommand{\sch}{\textit{sch}\xspace}
\newcommand{\adom}{\textit{adom}\xspace}

\newcommand{\narrow}[1]{\begin{changemargin}{2cm}{2cm} #1 \end{changemargin}}
\newcommand{\relat}[2]{$\textsc{#1}#2$}
\newcommand{\rdprog}[2]{
  \narrow{
      #1
      \begin{flalign*}
      #2
      \end{flalign*}
    }
}
\newcommand{\dprog}[4]{
  \begin{figure}[!htbp]
    \narrow{
      #1
      \begin{flalign*}
      #2
      \end{flalign*}
      \caption{#3}
      \label{#4}
    }
\end{figure}

}

% koniec definicji

\begin{document}
\maketitle

\begin{abstract}
Distributed computations on graphs are becoming increasingly important with the emergence of large graphs such as social networks and the Web that contain huge amounts of useful information.
Currently existing solutions, such as iterated MapReduce, Pregel and GraphLab are relatively difficult and require a significant level of fluency in programming.
This thesis presents an implementation of a tool which extends a distributed computations platform, Apache Spark, with the capability of executing queries written in a variant of a declarative query language, Datalog, especially extended to better support graph algorithms.
This approach makes it possible to express graph algorithms in a declarative query language, accessible to a broader group of users than typical programming languages, and execute them on an existing infrastructure for distributed computations.
\end{abstract}

\tableofcontents
%\listoffigures
%\listoftables

\input{0introduction.tex}

\input{1datalog.tex}

\input{2pregel.tex}

\input{3socialite.tex}

\input{5implementation.tex}

\input{6summary.tex}

\appendix

\input{appendix.tex}

\input{7bibliography.tex}

\end{document}