Efficient representation and algebraic manipulation of infinite relations in paraconsistent databases

Paraconsistent information is information that is incomplete and/or inconsistent. A data model for handling paraconsistent information in relational databases has recently been developed. In this paper, we show that a DBMS based on paraconsistent relations must be capable of handling infinite relations. We also 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. We finally show that all operations for the aforementioned PSPACE and CONTEXT-SENSITIVE cases can be carried out efficiently in polynomial time.