Sparse Matrix Representation
If the size of relation R(X, Y) is ‘small’ compared to the size M*N of the direct product XxY, the relation is called sparse (a small number of matrix elements have a non-zero value).
A sparse matrix can be efficiently represented as a list of ordered pairs of related elements <x, y>.
- Note that this list can be in row-major order or column-major order, but not both at the same time.
If instances of X and/or Y are large in size (I.e. many scalar property values are needed to specify an instance of either type), then R is more efficiently represented as a set of pairs of references <x*, y*> to elements of X and Y.
- Example: the set of all road segments which directly join two towns or road intersections on a map.