  We introduce new data structures for answering connectivity queries in graphs
subject to batched vertex failures. A deterministic structure processes a batch
of $d\leq d_{\star}$ failed vertices in $\tilde{O}(d^3)$ time and thereafter
answers connectivity queries in $O(d)$ time. It occupies space $O(d_{\star}
m\log n)$. We develop a randomized Monte Carlo version of our data structure
with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$
for any failure bound $d\le n$. This is the first connectivity oracle for
general graphs that can efficiently deal with an unbounded number of vertex
failures.
  We also develop a more efficient Monte Carlo edge-failure connectivity
oracle. Using space $O(n\log^2 n)$, $d$ edge failures are processed in $O(d\log
d\log\log n)$ time and thereafter, connectivity queries are answered in
$O(\log\log n)$ time, which are correct w.h.p.
  Our data structures are based on a new decomposition theorem for an
undirected graph $G=(V,E)$, which is of independent interest. It states that
for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$
vertices such that the remaining graph contains a Steiner forest for $U-B$ with
maximum degree $s$.
