In XML databases, the indexing process is based on a labelling or numbering scheme and generally used to label an XML document to perform an XML query using the path node information. Moreover, a labelling scheme helps to capture the structural relationships during the processing of queries without the need to access the physical document. Two of the main problems for labelling XML schemes are duplicated labels and the cost efficiency of labelling time and size. This research presents a novel dynamic XML labelling scheme, called the Pentagonal labelling scheme, in which data are represented as ordered XML nodes with relationships between them. The update of these nodes from large scale XML documents has been widely investigated and represents a challenging research problem as it means relabelling a whole tree. Our algorithms provide an efficient dynamic XML labelling scheme that supports data updates without duplicating labels or relabelling old nodes. Our work evaluates the labelling process in terms of size and time, and evaluates the labelling scheme’s ability to handle several insertions in XML documents. The findings indicate that the Pentagonal scheme shows a better initial labelling time performance than the compared schemes, particularly when using large XML datasets. Moreover, it efficiently supports random skewed updates, has fast calculations and uncomplicated implementations so efficiently handles updates. Also, it proved its capability in terms of the query performance and in determining the relationships. / Libyan government