We study models of incomplete information for XML, their computational properties, and query answering. While our approach is motivated by the study of relational incompleteness, incomplete information inXMLdocumentsmay appear not only as null values but also as missing structural information. Our goal is to provide a classification of incomplete descriptions of XML documents, and separate features - or groups of features - that lead to hard computational problems from those that admit efficient algorithms. Our classification of incomplete information is based on the combination of null values with partial structural descriptions of documents. The key computational problems we consider are consistency of partial descriptions, representability of complete documents by incomplete ones, and query answering. We showhowfactors such as schema information, the presence of node ids, and missing structural information affect the complexity of these main computational problems, and find robust classes of incomplete XML descriptions that permit tractable query evaluation.
XML with incomplete information: Models, properties, and query answering / Pablo, Barcelo; Leonid, Libkin; Poggi, Antonella; Cristina, Sirangelo. - (2009), pp. 237-246. (Intervento presentato al convegno 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '09 tenutosi a Providence, Rhode Island, USA nel 29 June 2009 through 1 July 2009) [10.1145/1559795.1559832].
XML with incomplete information: Models, properties, and query answering
POGGI, Antonella;
2009
Abstract
We study models of incomplete information for XML, their computational properties, and query answering. While our approach is motivated by the study of relational incompleteness, incomplete information inXMLdocumentsmay appear not only as null values but also as missing structural information. Our goal is to provide a classification of incomplete descriptions of XML documents, and separate features - or groups of features - that lead to hard computational problems from those that admit efficient algorithms. Our classification of incomplete information is based on the combination of null values with partial structural descriptions of documents. The key computational problems we consider are consistency of partial descriptions, representability of complete documents by incomplete ones, and query answering. We showhowfactors such as schema information, the presence of node ids, and missing structural information affect the complexity of these main computational problems, and find robust classes of incomplete XML descriptions that permit tractable query evaluation.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.