What is provided is an enhanced dynamic address translation facility. In one embodiment, a virtual address to be translated and an initial origin address of a translation table of the hierarchy of translation tables are obtained. Based on the origin address, a segment table entry is obtained which contains a format control field and an access validity field. If the format control and access validity are enabled, the segment table entry further contains an access control and fetch protection fields, and a segment-frame absolute address. Store operations to the block of data are permitted only if the access control field matches a program access key provided by either a Program Status Word or an operand of a program instruction being executed. Fetch operations from the desired block of data are permitted only if the program access key associated with the virtual address is equal to the segment access control field.