The present invention relates to a data processing apparatus, a data processing method, a program, a program recording medium, a data recording medium, and a data structure that enable reading of coded video data in access units without analyzing the coded video data. In step S211, a private_stream—2 packet is searched for, which is used for decoding coded video data, and which is located immediately prior to each of one or more decode startable points in coded video data in the access units. In addition, in step S216, based on an AU_length which is included in the private_stream—2 packet, and which represents the size of each of access units located from the private_stream—2 packet to the next private_stream—2 packet, the coded video data is read in the access units. The present invention can be applied to, for example, game machine using DVDs, etc.