-
Notifications
You must be signed in to change notification settings - Fork 14
/
related-work.tex
68 lines (51 loc) · 5.42 KB
/
related-work.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
\chapter{Related Work}
\label{sec:related-work}
\begin{quote}
\textit{A detailed list of LDBC publications is curated at~\url{https://ldbcouncil.org/publications}.}
\end{quote}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ACID Tests in Other Benchmarks}
% TPC-C
The challenge of verifying ACID-compliance has been addressed before by transactional benchmarks.
For example, TPC-C~\cite{tpcc} provides a suite of ACID tests.
However, the isolation tests are reliant on lock-based concurrency control, hence are not generalizable across systems.
Also, the transactional anomaly test coverage is limited to only four anomalies.
% YCSB+T
The authors of~\cite{DBLP:conf/icde/DeyFNR14} augment the popular YCSB framework for benchmarking transactional NewSQL systems, including a \emph{validation phase} that detects and quantifies consistency anomalies.
They permit the definition of arbitrary integrity constraints, checking they hold before and after a benchmark run.
% Note, there are parallels between this and the TPC-C consistency tests.
Such an approach is not possible within SNB Interactive due to the restrictive nature of transactional updates and the distinct lack of application-level constraints.
% Hermitage
The Hermitage project~\cite{Hermitage} with the goal of improving understanding of weak isolation, developed a range of hand-crafted isolation tests.
This test suite has much higher anomaly coverage but suffers from a problem similar to TPC-C.
Test execution is performed by hand, opening multiple terminals to step through the tests.\footnote{We initially experimented with Hermitage but found it difficult to induce anomalies that relied on fast timings due to some graph databases offering limited client-side control over transactions, with all statements submitted in one batch.}
% Jepsen + Elle
The Jepsen project~\cite{kingsbury} is not a benchmark rather it addresses correctness testing, traditionally focusing on distributed systems under various failure modes.
Most of Jepsen's transactional tests adopt a similar approach to us, executing a suite of transactions with hand-proven invariants.
However recently, the project has spawned Elle~\cite{DBLP:journals/corr/abs-2003-10554} a black-box transactional anomaly checker.
Elle does not rely on hand-crafted tests and can detect every anomaly in \cite{adya1999weak} (except for predicate-based anomalies) from an arbitrary transaction history.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Graph Processing Benchmarks}
Recent graph benchmarking initiatives focus on three key areas:
\begin{enumerate}
\item transactional workloads consisting of interactive read and update queries (OLTP) aiming at graph databases that explore small portions of the graph in each query~\cite{DBLP:conf/cidr/BarahmandG13,DBLP:conf/sigmod/ArmstrongPBC13,DBLP:journals/ase/DayarathnaS14,DBLP:conf/sigmod/ErlingALCGPPB15,DBLP:journals/pvldb/LissandriniBV18},
\item graph analysis algorithms (\eg PageRank) computed in bulk, typically expressed in cluster frameworks with graph APIs, rather than high-level queries~\cite{DBLP:conf/hipc/BaderM05,DBLP:conf/bigdataconf/ElserM13,DBLP:conf/sc/NaiXTKL15,DBLP:journals/pvldb/IosupHNHPMCCSAT16},
\item pattern matching and inferencing on semantic data~\cite{DBLP:journals/ws/GuoPH05,DBLP:books/sp/virgilio09/SchmidtHMPL09,DBLP:conf/semweb/MorseyLAN11,DBLP:conf/semweb/AlucHOD14,DBLP:journals/sosym/SzarnyasIRV18}.
\end{enumerate}
The SIGMOD 2014 Programming Contest defined queries on the Social Network Benchmark schema with a mix of subgraph projection and graph analytics~\cite{DBLP:journals/corr/abs-2010-12243}.
The challenges of using benchmarks correctly are described in~\cite{DBLP:conf/sigmod/RaasveldtHGM18}.
The Interactive queries were used in paper~\cite{DBLP:conf/grades/PacaciZLO17} to compare the performance of Gremlin, Cypher, SQL and SPARQL query engines.
The Labelled Subgraph Query Benchmark (LSQB)~\cite{DBLP:conf/sigmod/MhedhbiLKWS21} uses graphs produced by the LDBC SNB Datagen but simplifies them by omitting all attributes. It defines join-heavy subgraph queries to perform graph pattern matching.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Scalable Graph Generators}
%The \datagen component of SNB is a fork of the generator described in~\cite{DBLP:conf/tpctc/PhamBE12}.
A recent survey~\cite{DBLP:journals/csur/BonifatiHPS20} studied 38 graph generators, finding that only 4 of them supported generating updates and, intriguingly, even these generators only yield insertions and simple deletions at best.
\emph{LinkBench}~\cite{DBLP:conf/sigmod/ArmstrongPBC13} defines primitive delete operations targeting a single node or a single edge.
\emph{XGDBench}~\cite{DBLP:journals/ase/DayarathnaS14} defines an operation that deletes a single node.
The \emph{Social Network Intelligence BenchMark} (SIB)~\cite{SIB} (a precursor to LDBC SNB) requires the deletion of individual nodes (posts/photos).