  We propose a novel technique for constructing a graph representation of a
code through which we establish a significant connection between the service
rate problem and the well-known fractional matching problem. Using this
connection, we show that the service capacity of a coded storage system equals
the fractional matching number in the graph representation of the code, and
thus is lower bounded and upper bounded by the matching number and the vertex
cover number, respectively. This is of great interest because if the graph
representation of a code is bipartite, then the derived upper and lower bounds
are equal, and we obtain the capacity. Leveraging this result, we characterize
the service capacity of the binary simplex code whose graph representation, as
we show, is bipartite. Moreover, we show that the service rate problem can be
viewed as a generalization of the multiset primitive batch codes problem.
