A Pattern Search Algorithm in Graph Representations of Textual Data for an Ontology Construction System

The article presents the development and formalization of an algorithm for pattern matching in graph representations of textual data as a core component of syntactic-semantic transformations for ontology construction from text documents. The study aims to bridge the gap between natural language processing and formal logic by introducing a universal SPARQL-based approach for executing transf- ormation rules directly on graph database servers. The proposed method integrates RDF data repre- sentation with formal graph transformation techniques, including Double Pushout (DPO), ensuring correctness and mathematical rigor. Through the use of graph indexing schemes such as SPO, POS, and OSP, the proposed approach transforms the computationally expensive subgraph isomorphism task from exponential to practical polynomial complexity. The implementation achieves up to 73% runtime reduction during repeated executions due to server-side caching. The research contributes a flexible, formalized, and scalable mechanism for automatic ontology construction, facilitating deep semantic ana- lysis and causal reasoning from textual sources. The algorithm’s extensibility allows dynamic rule introduction without recompilation, making it suitable for applications in semantic web systems, kno- wledge extraction, and AI-driven natural language understanding.

Within the scope of this research, an algorithm was developed and analyzed for identifying homomorphic and isomorphic matches of pattern subgraphs within syntactic graphs, leveraging RDF representations and SPARQL queries enhanced with filter generation algorithms for shape-based mat- ching. The study demonstrates that the complexity of pattern search can be effectively mitigated through graph database indexing strategies, such as SPO, POS, and OSP indexes, reducing exponential complexity to polynomial levels for practical text block sizes. Experimental evaluation confirmed the scalability and efficiency of the proposed approach, revealing substantial runtime reductions during repeated executions as a result of server-side caching.

The work contributes flexible, formalized, and efficient methods for automatic ontology construction from natural language texts, enabling deep semantic analysis and causal reasoning. The approach supports extensibility and dynamic rule introduction without code recompilation, making it suitable for real-world semantic web and knowledge extraction systems. The results have implications for NLP, ontology engineering, and applications requiring interpretability and scalability in processing complex textual data.