Diego Calvanese, Giuseppe De Giacomo and Maurizio Lenzerini
Recent proposals to improve the quality of interaction with the World Wide Web suggest considering the Web as a huge semistructured database, so that retrieving information can be supported by the task of database querying. Under this view, it is important to represent the form of both the network, and the documents placed in the nodes of the network. However, the current proposals do not pay sufficient attention to represent document structures and reasoning about them. In this paper, we address these problems by providing a framework where Document Type Definitions (DTDs) expressed the Standard Generalized Markup Language are formalized in an expressive Description Logic equipped with sound and complete inference algorithms. We provide a method for verifying structural equivalence of DTDs, which works in worst case deterministic exponential time, in contrast to the known algorithms for this problem which are double exponential. We also deal with parametric versions of structural equivalence, and investigate other forms of reasoning on DTDs. The reasoning services studied in this paper can be seen as the fundamental building blocks for devising more complex inference systems supporting the task of querying the World Wide Web.