정규경로조회

Regular path query

데이터베이스, 특히 그래프 데이터베이스에서 정규 경로 쿼리[1] 또는 RPQ는 특정 정규식을 만족하는 경로로 연결된 데이터베이스의 엔드포인트 쌍을 요청하는 쿼리입니다. SPARQL 쿼리 언어에 "속성 경로"와 유사한 기능이 있습니다.

정의.

그래프 데이터베이스는 가장자리에 레이블이 있는 지시된 그래프로 구성됩니다. 정규 경로 쿼리는 레이블 집합에 대한 정규식일 뿐입니다. 예를 들어, 정점이 사용자를 나타내고 부모에서 자식까지의 에지에 대한 에지 레이블 "부모"가 있는 그래프 데이터베이스에서 경로 쿼리 ∗ {\{\parent}^{*}}는 노드 x와 x의 자손 y의 쌍을 선택합니다. 길이가 1 이상인 "부모" 모서리의 x에서 y까지의 경로를 사용합니다.

의미론

RPQ에 대한 답은 엔드포인트 쌍, 즉 정규식을 만족하는 일부 경로에 의해 연결된 노드 x 및 y 쌍으로 구성될 수 있고, 정규식을 만족하는 모든 경로의 목록으로 구성될 수도 있습니다. 그러나 이 경로 집합은 일반적으로 무한합니다.

결과의 수가 무한하지 않도록 하기 위해 RPQ의 의미론은 단순한 경로, 즉 동일한 정점을 두 번 통과하지 않는 경로 또는 동일한 에지를 두 번 통과하지 않는 경로만을 반환하도록 정의되기도 합니다.[2]

복잡성

모든 엔드포인트 쌍을 반환한다는 의미에서 정규 경로 쿼리(RPQ)의 평가는 다항식 시간 내에 수행될 수 있습니다. 이를 위해 모든 엔드포인트 쌍에 대해 그래프 데이터베이스를 유한 오토마톤으로 보고 정규 경로 쿼리를 유한 오토마톤으로 표현할 수 있으며, 예를 들어 제품 오토마톤 구성을 통해 두 언어의 교차점이 비어 있지 않은지 확인하여 적합한 경로가 있는지 확인할 수 있습니다.

기타문제

쿼리 포함[3] 및 쿼리 다시 쓰기와 같은 일반 경로 쿼리에 대해 쿼리에 대한 몇 가지 고전적인 문제가 연구되었습니다.[4]

확장

데이터베이스 이론 연구는 RPQ의 더 발현적인 변형을 조사했습니다.

  • 양방향 RPQ는 2RPQ라고도 하며, 역방향으로 에지를 통과할 수도 있습니다. 더 정확하게 말하면, 2RPQ는 그래프의 레이블을 역모서리에 해당하는 레이블과 함께 사용하는 정규식입니다. 예를 들어, RPQ - {\{\는 부모 에지에서 먼저 뒤로 가고 부모 에지에서 앞으로 가는 경로를 가진 노드 x와 y 쌍을 선택합니다. 즉, x와 y는 형제자매입니다.
  • 결합형 정규 경로 쿼리는 원자가 RPQ인 결합형 쿼리인 CRPQ입니다. 이러한 쿼리를 사용하면 경로보다 더 복잡한 패턴을 테스트할 수 있지만 평가하기가 어렵습니다.
  • UC2RPQ는 결합 쿼리의 결합과 같은 분리와 양방향 표현을 모두 허용하는 추가 확장입니다.[5]

참고문헌

  1. ^ "Answering regular path queries using views IEEE Conference Publication IEEE Xplore". ieeexplore.ieee.org. Retrieved 2024-01-18.
  2. ^ Martens, Wim; Trautner, Tina (2019-10-15). "Dichotomies for Evaluating Simple Regular Path Queries". ACM Transactions on Database Systems. 44 (4): 16:1–16:46. doi:10.1145/3331446. ISSN 0362-5915.
  3. ^ Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Vardi, M. Y. (2003-12-01). "Reasoning on regular path queries". ACM SIGMOD Record. 32 (4): 83–92. doi:10.1145/959060.959076. ISSN 0163-5808.
  4. ^ Calvanese, Diego; De Giacomo, Giuseppe; Lenzerini, Maurizio; Vardi, Moshe Y. (1999-05-01). "Rewriting of regular expressions and regular path queries". Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '99. New York, NY, USA: Association for Computing Machinery: 194–204. doi:10.1145/303976.303996. ISBN 978-1-58113-062-1.
  5. ^ Figueira, Diego; Morvan, Rémi (November 2023). Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries.