A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

तकनीकी सारांश: Horn-ALCHI परमाणु प्रश्नों को GQL में पुनलेखन (Rewriting) के लिए एक सामान्य पर्याप्त स्थिति

समस्या विवरण
ISO मानक GQL (ग्राफ क्वेरी लैंग्वेज) का उदय एक शक्तिशाली क्वेरी भाषा पेश करता है जो नियंत्रित नियमित पुनरावृत्ति (regular recursion) के साथ प्रथम-क्रम तर्क (first-order logic - FO) का विस्तार करती है। यह ऑन्टोलॉजी-मीडिएटेड क्वेरी (OMQ) उत्तर देने के संबंध में एक महत्वपूर्ण प्रश्न खड़ा करता है: कौन सी नियम-आधारित क्वेरी, जो अभिव्यंजक डिस्क्रिप्शन लॉजिक्स (DLs) पर परिभाषित हैं, GQL में पुनलिखित की जा सकती है?

लेखक Horn-ALCHI पर ध्यान केंद्रित करते हैं, जो एक अभिव्यंजक DL है और इनवर्स रोल्स (inverse roles) तथा रोल कंस्ट्रक्टर्स (role constructors) का समर्थन करता है। DL-Lite परिवार के विपरीत, Horn-ALCHI आम तौर पर प्रथम-क्रम रूप से पुनलिखित (first-order rewritable) नहीं है, जिसका अर्थ है कि मानक SQL-आधारित मूल्यांकन तकनीकें अपर्याप्त हैं। जबकि GQL आवश्यक अभिव्यक्ति शक्ति (विशेष रूप से, यूनियंस ऑफ कंजंक्टिव टू-वे रेगुलर पाथ क्वेरीज - UC2RPQs के माध्यम से) प्रदान करता है, यह स्पष्ट नहीं है कि कौन सी Horn-ALCHI क्वेरी इस खंड (fragment) में प्रभावी ढंग से अनुवादित की जा सकती है। यह शोध पत्र एक व्यापक, निर्णय योग्य (decidable) Horn-ALCHI OMQ वर्ग की पहचान करने के अंतराल को संबोधित करता है जो ऐसे पुनलेखन को स्वीकार करता है।

कार्यप्रणाली (Methodology)
लेखक एक बहु-चरणीय, समतुल्यता-संरक्षण रूपांतरण पाइपलाइन प्रस्तावित करते हैं:

1. Horn-ALC$\not\exists$ में सामान्यीकरण (Normalization):
   प्रक्रिया एक Horn-ALCHI क्वेरी को एक समतुल्य Horn-ALC$\not\exists$ क्वेरी में बदलने से शुरू होती है। इसमें शामिल है:

   • रोल समावेशन अभिलेखों (role inclusion axioms, जैसे $R \sqsubseteq S$) और इनवर्स रोल अभिलेखों को रोल समावेशन के रिफ्लेक्सिव-ट्रांजिटिव क्लोजर के माध्यम से बाधाओं को प्रसारित करके समाप्त करना।
   • नियम शीर्षों (rule heads) में अस्तित्व संबंधी परिमाणीकरण (existential quantification, जैसे $A \sqsubseteq \exists R.B$) को हटाना, उन्हें Horn-SHIQ के स्थापित तरीकों का पालन करते हुए डैटलॉग (Datalog) नियमों में अनुवादित करना। यह चरण नियम सेट के आकार में घातांकीय वृद्धि (exponential blow-up) का कारण बन सकता है लेकिन अर्थ संबंधी समतुल्यता को बनाए रखता है।

2. DL ऑटोमेटा में अनुवाद:
   सामान्यीकृत Horn-ALC$\not\exists$ क्वेरी को फिर एक DL ऑटोमेटा में मैप किया जाता है, जो एक नवीन परिमित-अवस्था उपकरण (finite-state device) है।

   • संरचना: ऑटोमेटा में स्टेट्स (states) होते हैं जो कॉन्सेप्ट नामों के अनुरूप होते हैं और एक विशेष स्वीकार करने वाली अवस्था ($q_{acc}$) होती है। ट्रांजिशन या तो बाइनरी (क्लासेस या रोल एक्सप्रेशन द्वारा लेबल किए गए, एक अवस्था से दूसरी अवस्था में जाने वाले) होते हैं या मल्टी-आरी ( $\varepsilon$ द्वारा लेबल किए गए, जो एक अवस्था को अवस्थाओं के सेट में विभाजित करते हैं)।
   • अर्थ (Semantics): एक स्वीकार करने वाला रन (accepting run) एक परिमित रूटेड ट्री होता है जहाँ नोड्स को स्टेट-कॉन्स्टेंट पेयर्स के साथ लेबल किया जाता है। ट्री की संरचना "चेज़" (chase) प्रक्रिया के माध्यम से तथ्यों के व्युत्पत्ति को दर्शाती है। ऑटोमेटा एक तथ्य सेट को तब स्वीकार करता है जब प्रारंभिक अवस्था और स्थिरांक (constant) से शुरू होकर और सभी लीव्स (leaves) को स्वीकार करने वाली अवस्था द्वारा लेबल करने वाले रन का अस्तित्व होता है।

3. स्तरीकरण (Stratification) और PQs में पुनलेखन:
   पुनलेखन के लिए एक पर्याप्त स्थिति की पहचान करना मुख्य योगदान है: स्तरीकरण।

   • स्तरीकरण: लेखक ऑटोमेटा के ट्रांजिशन फंक्शन के आधार पर स्टेट्स के बीच एक निर्भरता संबंध ($\succ_A$) को परिभाषित करते हैं। निर्भरता तब होती है जब एक पथ में एक बाइनरी ट्रांजिशन (रोल) के बाद अंततः एक मल्टी-आरी ट्रांजिशन शामिल हो। एक ऑटोमेटा स्तरीकृत है यदि यह निर्भरता संबंध अचक्रीय (acyclic) है।
   • पुनलेखन एल्गोरिदम: स्तरीकृत ऑटोमेटा के लिए, लेखक एक समतुल्य पॉजिटिव टू-वे रेगुलर पाथ क्वेरी (PQ) का निर्माण करते हैं। यह इंडक्टिवली (निगमनात्मक रूप से) स्ट्रैटम (stratum) के अनुसार किया जाता है:
     • सबसे निचले स्ट्रैटम (कोई निर्भरता नहीं) के स्टेट्स के लिए, क्वेरी का निर्माण बाइनरी ट्रांजिशन (NFA द्वारा मॉडल किए गए) से प्राप्त रेगुलर एक्सप्रेशंस का उपयोग करके सीधे किया जाता है।
     • उच्च स्ट्रैटम के लिए, निर्माण पुनरावर्ती रूप से निर्भर निचले स्ट्रैटम के PQs को शामिल करता है, जो मल्टी-आरी ट्रांजिशन के कारण होने वाले ब्रांचिंग को संभालने के लिए अस्तित्व संबंधी क्वांटिफायर (existential quantifiers) पेश करता है।
   • यह निर्माण गारंटी देता है कि एक स्ट्रैटिफिकेशन अचक्रीय प्रकृति के कारण एक परिमित PQ बनेगा।

4. GQL में मैपिंग:
   अंत में, परिणामी PQ को यूनियन ऑफ कंजंक्टिव टू-वे रेगुलर पाथ क्वेरीज (UC2RPQ) में परिवर्तित किया जाता है। चूंकि UC2RPQs, GQL का एक केंद्रीय खंड हैं, यह अंतिम पुनलेखन स्थापित करता है।

मुख्य योगदान

• DL ऑटोमेटा फॉर्मलिज्म: Horn-ALCHI सेमान्टिक्स और पाथ-आधारित क्वेरी भाषाओं के बीच एक सेतु के रूप में DL ऑटोमेटा का परिचय।
• स्तरीकरण स्थिति: GQL-पुनलेखनीयता के लिए एक सामान्य पर्याप्त स्थिति के रूप में स्तरीकरण की पहचान। यह स्थिति उन विशिष्ट चक्रीय निर्भरताओं को खारिज करती है जो जटिलता बढ़ाती हैं, लेकिन पिछले दृष्टिकोणों की तुलना में एक व्यापक वर्ग की अनुमति देती है।
• सामान्य पुनलेखन प्रक्रिया: एक पूर्ण, रचनात्मक एल्गोरिदम जो नॉर्मलाइजेशन, ऑटोमेटा निर्माण और स्तरीकृत PQ जनरेशन के मध्यवर्ती चरणों के माध्यम से Horn-ALCHI क्वेरी को GQL फॉर्मूला में बदलने के लिए उपयोग किया जाता है।
• पूर्व कार्य का समावेशन (Subsumption): लेखक प्रदर्शित करते हैं कि उनका वर्ग स्पष्ट रूप से निम्नलिखित को समाहित करता है:
  • DL-Lite: DL-Lite में क्वेरी स्वाभाविक रूप से स्तरीकृत ऑटोमेटा (एक एकल स्ट्रैटम के साथ) प्रदान करती हैं।
  • Harmless Linear ELHI: प्रस्तावित वर्ग उन क्वेरीज़ को कवर करता है जो ELHI के पूर्व "हारmless" प्रतिबंधों से बाहर हैं।
  • ELH$^{ql}_i$: यह वर्ग उन क्वेरीज़ (जैसे पेपर में Crit और Acc वाला उदाहरण) को शामिल करता है जो ELH$^{ql}_i$ के अर्थ में स्थानीय (local) नहीं हैं लेकिन फिर भी स्तरीकृत हैं और इस प्रकार पुनलिखित योग्य हैं।

परिणाम और महत्व
यह शोध पत्र स्थापित करता है कि Horn-ALCHI OMQs का एक महत्वपूर्ण और व्यावहारिक रूप से प्रासंगिक उपवर्ग (subclass) को GQL में पुनलिखित किया जा सकता है।

• अभिव्यक्ति (Expressiveness): यह दृष्टिकोण उन क्वेरीज़ को संभालता है जिन्हें पहले GQL खंडों में गैर-पुनलिखित माना जाता था, जैसे कि नियम बॉडी में इनवर्स रोल्स और कंजंक्शन्स के बीच जटिल इंटरैक्शन (उदाहरण के लिए, $Sens(x) \land Onl(x) \to Crit(x)$ के साथ $Crit(x) \land Acc(x, y) \to Trust(y)$)।
• पूर्णता (Completeness): लेखक स्वीकार करते हैं कि स्थिति पर्याप्त है लेकिन आवश्यक (necessary) नहीं है। ऐसे Horn-ALCHI क्वेरी मौजूद हैं जो GQL-पुनलिखित योग्य हैं (जैसे कि नेस्टेड रेगुलर पाथ क्वेरीज की आवश्यकता वाले मामले) लेकिन स्तरीकरण स्थिति को पूरा नहीं करते हैं।
• व्यावहारिकता (Practicality): लेखक उल्लेख करते हैं कि हालांकि नॉर्मलाइजेशन चरण घातांकीय वृद्धि का कारण बन सकता है, लेकिन परिणामी स्तरीकरण जांच निर्णय योग्य (decidable) है। वे सुझाव देते हैं कि वास्तविक दुनिया के रिपॉजिटरी (जैसे मैनचेस्टर OWL रिपॉजिटरी) पर अनुभवजन्य मूल्यांकन (empirical evaluation) अगला आवश्यक कदम है ताकि यह निर्धारित किया जा सके कि कितने व्यावहारिक प्रश्न इस वर्ग में आते हैं।

निष्कर्ष
यह शोध पत्र अभिव्यंजक DLs पर ऑन्टोलॉजी-मीडिएटेड क्वेरीज़ का मूल्यांकन करने के लिए GQL का लाभ उठाने के लिए एक सैद्धांतिक आधार प्रदान करता है। DL ऑटोमेटा और स्तरीकरण की अवधारणा को पेश करके, लेखक एक मजबूत विधि प्रदान करते हैं, जो GQL की प्रयोज्यता को सरल DL-Lite परिदृश्यों से आगे बढ़ाकर अधिक जटिल, अभिव्यंजक नॉलेज बेस तक विस्तारित करती है। यह कार्य GQL को OMQs के एक व्यापक स्पेक्ट्रम के लिए एक व्यवहार्य लक्ष्य भाषा के रूप में स्थापित करता है, जो अभिव्यंजक ऑन्टोलॉजिकल रीजनिंग और आधुनिक ग्राफ क्वेरी प्रोसेसिंग के बीच के अंतर को पाटता है।