Paraconsistent information is information that is incomplete and/or inconsistent. A data model for representing and manipulating paraconsistent information in relational databases has recently been developed. Algebraic operators on the underlying paraconsistent relations of this model are generalizations of the usual ones on ordinary relations. However, unlike in the ordinary case, a DBMS based on paraconsistent relations must be capable of handling infinite relations. In this paper, we show this necessity and identify classes of infinite paraconsistent relations whose members can be effectively represented and manipulated. We show that the classes of REGULAR and, under different conditions, CONTEXT-SENSITIVE as well as PSPACE paraconsistent relations are such. We also show that the CONTEXT-FREE and R.E. classes do not have the desired properties, while P, NP, LOGSPACE and NLOGSPACE also probably do not. These results help identify the kinds of relational DBMS that can be constructed for handling incomplete and inconsistent information about tuples.