1. Introduction and Background
The DNS protocol [RFC1035] defines response code 3 as "Name Error", or "NXDOMAIN" [RFC2308], which means that the queried domain name does not exist in the DNS. Since domain names are represented as a tree of labels ([RFC1034], Section 3.1), nonexistence of a node implies nonexistence of the entire subtree rooted at this node.
The DNS iterative resolution algorithm precisely interprets the NXDOMAIN signal in this manner. If it encounters an NXDOMAIN response code from an authoritative server, it immediately stops iteration and returns the NXDOMAIN response to the querier.
However, in most known existing resolvers today, a cached nonexistence for a domain is not considered "proof" that there can be no child domains underneath. This is due to an ambiguity in [RFC1034] that failed to distinguish Empty Non-Terminal (ENT) names ([RFC7719]) from nonexistent names (Section 3.1). The distinction became especially important for the development of DNSSEC, which provides proof of nonexistence. [RFC4035], Section 3.1.3.2, describes how security-aware authoritative name servers make the distinction, but no existing RFCs describe the behavior for recursive name servers.
This document specifies that an NXDOMAIN response for a domain name means that no child domains underneath the queried name exist either; furthermore, it means that DNS resolvers should interpret cached nonexistence in this manner. Since the domain names are organized in a tree, it is a simple consequence of the tree structure: nonexistence of a node implies nonexistence of the entire subtree rooted at this node.
1.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].
"QNAME": defined in [RFC1034] and in [RFC1035], Section 4.1.2, but, because [RFC2308] provides a different definition, we repeat the original one here: the QNAME is the domain name in the question section.
"Denied name": the domain name whose existence has been denied by a response RCODE of NXDOMAIN. In most cases, it is the QNAME but, because of [RFC6604], it is not always the case.
Other terms are defined in [RFC1034], [RFC1035], and (like NXDOMAIN itself) in the more recent [RFC7719].
The domain name space is conceptually defined in terms of a tree structure. The implementation of a DNS resolver/cache MAY use a tree or other data structures. The cache being a subset of the data in the domain name space, it is much easier to reason about it in terms of that tree structure and to describe things in those terms (names under/above, descendant names, subtrees, etc.). In fact, the DNS algorithm description in [RFC1034] even states an assumption that the cache is a tree structure, so the precedent is already well established: see its Section 4.3.2, which says "The following algorithm assumes that the RRs are organized in several tree structures, one for each zone, and another for the cache..." So, in this document, each time we talk about a tree or tree operations, we're referring to the model, not to the actual implementation.