시멘틱 웹(semantic web)과 함께 등장한 RDF는 웹 상의 메타데이타 및 데이타를 나타내는 표준으로 자리매김 하고 있다. 이에 따라 RDF에 대한 저장 및 질의 처리에 대한 연구가 많이 이루어졌으며, 대표적인 시스템으로 Sesame, Jena 등이 있다. 그러나 아직 갱신 방법에 대한 연구는 부족하다. RDF 데이타가 지속적으로 갱신이 이루어지는 경우에는 저장된 RDF를 갱신해야 하는 상황이 발생한다. 현존하는 RDF 저장소에서 데이타를 갱신하기 위해서는 기존의 데이타를 모두 삭제한 후 새로운 데이타를 처음부터 다시 저장해야 하는데, 이러한 상황에서는 매우 비효율적이다. 또한 한 RDF 저장소에 여러 RDF가 저장되어 있는 경우에는 갱신 문제가 더욱 복잡해진다. 이에 본 논문에서는 RDF 데이타를 점진적으로 갱신하는 기법을 제안하고자 한다. 제안한 기법은 텍스트 비교 알고리즘을 통해 얻은 결과를 보완하여 기존 RDF 데이타에서 변화된 트리플 문장만을 추출하여 갱신한다. 실제 RDF 데이터를 이용한 실험을 통해 제안한 방법을 사용하여 갱신을 효율적으로 할 수 있음을 보였다.
시멘틱 웹(semantic web)과 함께 등장한 RDF는 웹 상의 메타데이타 및 데이타를 나타내는 표준으로 자리매김 하고 있다. 이에 따라 RDF에 대한 저장 및 질의 처리에 대한 연구가 많이 이루어졌으며, 대표적인 시스템으로 Sesame, Jena 등이 있다. 그러나 아직 갱신 방법에 대한 연구는 부족하다. RDF 데이타가 지속적으로 갱신이 이루어지는 경우에는 저장된 RDF를 갱신해야 하는 상황이 발생한다. 현존하는 RDF 저장소에서 데이타를 갱신하기 위해서는 기존의 데이타를 모두 삭제한 후 새로운 데이타를 처음부터 다시 저장해야 하는데, 이러한 상황에서는 매우 비효율적이다. 또한 한 RDF 저장소에 여러 RDF가 저장되어 있는 경우에는 갱신 문제가 더욱 복잡해진다. 이에 본 논문에서는 RDF 데이타를 점진적으로 갱신하는 기법을 제안하고자 한다. 제안한 기법은 텍스트 비교 알고리즘을 통해 얻은 결과를 보완하여 기존 RDF 데이타에서 변화된 트리플 문장만을 추출하여 갱신한다. 실제 RDF 데이터를 이용한 실험을 통해 제안한 방법을 사용하여 갱신을 효율적으로 할 수 있음을 보였다.
The Resource Description Framework(RDF), which emerged with the semantic web, is settling down as a standard for representing information about the resources in the World Wide Web Hence, a lot of research on storing and query processing RDF documents has been done and several RDF storage systems, su...
The Resource Description Framework(RDF), which emerged with the semantic web, is settling down as a standard for representing information about the resources in the World Wide Web Hence, a lot of research on storing and query processing RDF documents has been done and several RDF storage systems, such as Sesame and Jena, have been developed. But the research on updating RDF documents is still insufficient. When a RDF document is changed, data in the RDF triple store also needs to be updated. However, current RDF triple stores don't support incremental update. So updating can be peformed only by deleting the old version and then storing the new document. This updating method is very inefficient because RDF documents are steadily updated. Furthermore, it makes worse when several RDF documents are stored in the same database. In this paper, we propose an incremental update algorithm on RDF, documents in triple stores. We use a text matching technique for two versions of a RDF document and compensate for the text matching result to find the right target triples to be updated. We show that our approach efficiently update RDF documents through experiments with real-life RDF datasets.
The Resource Description Framework(RDF), which emerged with the semantic web, is settling down as a standard for representing information about the resources in the World Wide Web Hence, a lot of research on storing and query processing RDF documents has been done and several RDF storage systems, such as Sesame and Jena, have been developed. But the research on updating RDF documents is still insufficient. When a RDF document is changed, data in the RDF triple store also needs to be updated. However, current RDF triple stores don't support incremental update. So updating can be peformed only by deleting the old version and then storing the new document. This updating method is very inefficient because RDF documents are steadily updated. Furthermore, it makes worse when several RDF documents are stored in the same database. In this paper, we propose an incremental update algorithm on RDF, documents in triple stores. We use a text matching technique for two versions of a RDF document and compensate for the text matching result to find the right target triples to be updated. We show that our approach efficiently update RDF documents through experiments with real-life RDF datasets.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
RDF 문서를 저장소에 저장하여 사용하고 있는데 이 RDF 문서가 갱신이 되었을 경우를 생각해보자. 본 논문의 목적은 이러한 경우에 갱신된 문서를 새로 저장하지 않고 기존에 저장해서 사용하고 있는 RDF 문서와 새 버전의 RDF 문서를 비교하여 그 변화된 부분을 얻어낸 뒤, 이를 이용하여 갱신을 효과적으로 수행하겠다는 것이다.
마지막으로, 역러 RDF 문서가 하나의 데이타베이스에 저장되어 있는 경우를 생각해보자. 이러한 경우 어떤 문장이 어떤 문서로부터 온 것인지 알 수 없다.
문서가 갱신이 되었을 경우를 생각해보자. 본 논문의 목적은 이러한 경우에 갱신된 문서를 새로 저장하지 않고 기존에 저장해서 사용하고 있는 RDF 문서와 새 버전의 RDF 문서를 비교하여 그 변화된 부분을 얻어낸 뒤, 이를 이용하여 갱신을 효과적으로 수행하겠다는 것이다. 이 목적은 서론에서 살펴본 것과 같이 RDF 문서의 크기에 비해 그 변화량이 매우 작다는 사실에 기인한 것이다.
실험을 통해 저장 시간의 단축과 갱신의 정확성을 보였고, 갱신된 문장의 수에 따라 수행시간이 어떻게 변하는지 확인하였다.
본 논문의 목적은 이러한 경우에 갱신된 문서를 새로 저장하지 않고 기존에 저장해서 사용하고 있는 RDF 문서와 새 버전의 RDF 문서를 비교하여 그 변화된 부분을 얻어낸 뒤, 이를 이용하여 갱신을 효과적으로 수행하겠다는 것이다. 이 목적은 서론에서 살펴본 것과 같이 RDF 문서의 크기에 비해 그 변화량이 매우 작다는 사실에 기인한 것이다. 전체 시나리오는 그림 3과 같다.
하는 연구가 [기에서 이루어졌다. 이 연구에서는 온톨로지의 버전이 다르더라도 최대한 호환되어 사용이 가능하도록 그래프 매칭을 통해 두 버전이 어떻게 다른지 사용자에게 보여주고 변화한 개념들간의 관계를 사용자가 지정할 수 있도록 하였다.
제안하였다. 이 온톨로지를 이용하여 어떤 트리플이 추가, 삭제, 변경되었는지를 배포하자는 것이다. 그러나 delta 온톨로지는 제안에 그치고 있으며 현재 실제로 사용되지는 않는다.
2절의 예에서 알 수 있듯이 diff의 결과(그림 7)만으로는 그림 6의 갱신 연산을 알아내기가 어렵다. 이 절에서는 왜 diff 결과만으로 갱신해야 할 RDF 문장을 알 수 없는지 그 이유를 살펴본다.
가설 설정
. 공 노드(blank node)를 사용할 때 rdf:nodeID는 사용하지 않는다.
.RDF 문서를 표현하는 방법이 동일하다.
.갱신할 때 RDF 문서에 있던 엘리먼트들의 순서는 변하지 않는다.
・ 공 노드를 사용할 때 rdfmodelD는 사용하지 않는다.
.RDF 문서를 표현하는 방법이 동일하다.
.갱신할 때 RDF 문서에 있던 엘리먼트들의 순서는 변하지 않는다.
이 가정이 지켜지지 않았을 경우에는 적절한 문서 변환 과정을 통해 지켜지도록 할 수 있다. 둘째 가정은 RDF 문서에서는 원래 순서의 변화가 영향을 미치지 않아 기존에 있던 엘리먼트들의 순서가 바뀌어도 그 내용은 동일한데, 갱신 과정에서 엘리먼트들의 순서가 변하지 않는다고 가정한 것이다. 부가적으로, 동일한 트리플을 여러 형대의 RDF 구문으로 汀타낼 수 있는데 이것 역시 갱신 과정에서 변하지 않는다고 가정한다.
이 가정이 지켜지지 않았을 경우에도 갱신은 가능하나, 텍스트 비교 결과가 커져 갱신 시간이 오래 걸리게 된다. 마지막 가정은 RDF에서 공 노드를 사용할 때, 특정 공 노드를 가리킬 수 있도록 문서 내에서만 사용될 수 있는 식별자를 기술하여 사용할 수 있는데 이를 배제한 것이다. rdf:nodeID를 사용하지 않고도 동일한 내용을 기술할 수 있기 때문에 이 가정도 지켜질 수 있다.
둘째 가정은 RDF 문서에서는 원래 순서의 변화가 영향을 미치지 않아 기존에 있던 엘리먼트들의 순서가 바뀌어도 그 내용은 동일한데, 갱신 과정에서 엘리먼트들의 순서가 변하지 않는다고 가정한 것이다. 부가적으로, 동일한 트리플을 여러 형대의 RDF 구문으로 汀타낼 수 있는데 이것 역시 갱신 과정에서 변하지 않는다고 가정한다. 이 가정이 지켜지지 않았을 경우에도 갱신은 가능하나, 텍스트 비교 결과가 커져 갱신 시간이 오래 걸리게 된다.
이루어진다. 세번째 가정의 rdf:nodeID는 고려하지 않았다. 그러나 rdf:nodeID< 사용하지 않고 동일한 의미의 RDF 문서를 작성할 수 있다.
우선, 첫째 가정은 문서의 띄어쓰기와 같은 작성 방법이 동일하다는 것이다. 한 RDF 문서는 보통 특정 기관과 같이 일정한 배포자가 주관하여 배포하기 때문에 표현 규칙이 동일하게 유지되며, 따라서 이 가정은 실제 세계에서도 일반적으로 성립한다.
첫번째 가정과 두번째 가정은 효율성을 위한 가정으로, 이 가정들이 없더라도 동작은 제대로 이루어진다. 세번째 가정의 rdf:nodeID는 고려하지 않았다.
제안 방법
2GHz, 2GB RAM 사양의 컴퓨터에서 수행하였으며 OS는 Linux(Fedora Core 3) 를 사용하였다. TripleDiff 알고리즘의 구현은 대표적인 RDF 저장소인 Sesame 122를 수정하여 구현하였으며, RdfRepository SAIL을 이용하여 저장하였다. Java SDK 150으로 구현하였으며, 하부 데이타베이스로는 MySQL 419를 사용하였다.
제안하였다. 그래프를 공 노드가 트리플의 어느 부분에 있느냐에 따라 트리플을 여러 클래스로 분류하고 같은 클래스에 속한 트리플간에만 비교하도록 하여 그래프를 매칭할 때 그 비교 공간을 줄였다. 또한 전자 서명(digital , signature)을 목적으로 한 후속 연구에서 공 노드의 식별자를 무시한 채 트리플들을 정렬한 후 이를 토대로 비교하는 기법을 제시하였는데, 이 연구의 단점은 문서가 극히 일부만 변하는 경우에도 많은 양의 텍스트 비교, 결과를 초래함 수 있다는 점이다.
그리고 [1 이은 RDF 문서가 갱신되었을 때 어떻게 갱신되었는지 그 갱신 정보를 표현하는데 사용되는 delta 온톨로지를 제안하였다. 이 온톨로지를 이용하여 어떤 트리플이 추가, 삭제, 변경되었는지를 배포하자는 것이다.
데이타베이스에서 문장을 삭제하는데 걸리는 시간이 추가하는 데 걸리는 시간보다 더 길다는 점을 감안하여 두 연산을 완전히 분리시켜 실험을 해 보았다. 데이타는 삭제 연산 실험의 경우 Gene Ontology TermDB의 2005년 11월 23일자 파일(23MB, 294, 650문장)의 문장을 점차적으로 삭제하여 만들었으며, 추가 연산 실험에서는 삭제 실험에서 만든 데이타를 역으로 이용하였다.
두 RDF 문서의 변화 부분을 알아내기 위해서는 효율성을 위해 텍스트 비교를 이용한다. 그러나 텍스트 비교 결과를 갱신에 그대로 사용할 수는 없기 때문에 이를 보완하는 형태를 취하는데, 이를 위해서는 다음과 같은 몇 가지 가정이 필요하다.
그래프를 공 노드가 트리플의 어느 부분에 있느냐에 따라 트리플을 여러 클래스로 분류하고 같은 클래스에 속한 트리플간에만 비교하도록 하여 그래프를 매칭할 때 그 비교 공간을 줄였다. 또한 전자 서명(digital , signature)을 목적으로 한 후속 연구에서 공 노드의 식별자를 무시한 채 트리플들을 정렬한 후 이를 토대로 비교하는 기법을 제시하였는데, 이 연구의 단점은 문서가 극히 일부만 변하는 경우에도 많은 양의 텍스트 비교, 결과를 초래함 수 있다는 점이다.
먼저 실험 데이타를 대상으로 하여 새 버전의 RDF 문서를 새로 저장하는데 걸리는 시간과 TripieDiff 기법을 사용하여 갱신하였을 때 걸리는 시간을 비교해 보았다. 결과는 그림 12와 같다.
우리는 본 연구에서 RDF 문서가 지속적으로 갱신되는 경우 이를 데이타베이스에 효과적으로 반영하는 TripieDiff라는 점진적인 갱신 알고리즘을 제안하였다. 이 기법은 텍스트 비교를 이용하여 이전 버전의 RDF 문서와 새 버전의 rdf 문서의 차이를 알아낸 후, 이에 텍스트 비교의 문제점을 보완하여 갱신의 대상이 되는 트리플들을 알아내어 새 버전의 RDF 문서 전체를 새로 저장하지 않고 효율적으로 갱신할 수 있게 해준다.
텍스트 비교가 RDF의 반구조(semi-structured) 적인 특징을 이해하지 못하여 비교 결과에서 RDF 문서의 구조가 어긋나는 경우가 발생하기 때문이다 따라서 diff 결과에서 갱신의 대상이 되는 트리플 문장을 알아내는 방법이 필요하다. 이를 위해 본 논문에서는 RDF 데이타에 대해 몇 가지 가정을 한 뒤, diff 결과를 보정하여 갱신 대상이 되는 트리플들을 알아내어 이를 갱신한다. 세운 가정은 다음과 같다.
대상 데이터
데이타베이스에서 문장을 삭제하는데 걸리는 시간이 추가하는 데 걸리는 시간보다 더 길다는 점을 감안하여 두 연산을 완전히 분리시켜 실험을 해 보았다. 데이타는 삭제 연산 실험의 경우 Gene Ontology TermDB의 2005년 11월 23일자 파일(23MB, 294, 650문장)의 문장을 점차적으로 삭제하여 만들었으며, 추가 연산 실험에서는 삭제 실험에서 만든 데이타를 역으로 이용하였다.
Java SDK 150으로 구현하였으며, 하부 데이타베이스로는 MySQL 419를 사용하였다. 실험 데이타는 실제 데이타인 Gene Ontology TermDB 의 2005년 11월 22일과 11월 23일 자 RDF 문서(약 23MB, diff 결과 33KB), UniProt Taxonomy의 2005년 11월 23일과 12월 7일자 RDF 문서(약 96MB, diff 결과 567KBX 이용하였다.
실험은 실제 데이타인 Gene Ontology TermDB RDF 문서와 UniProt taxonomy RDF 문서를 가지고 수행하였다. 실험을 통해 저장 시간의 단축과 갱신의 정확성을 보였고, 갱신된 문장의 수에 따라 수행시간이 어떻게 변하는지 확인하였다.
이론/모형
필요하다. 점친적 갱신을 위해 본 논문에서는 텍스트 비교 알고리즘을 사용한다. 가장 널리 사용되고 있는 방법은 GNU diff[기로, 텍스트 파일의 바뀐 부분을 줄 단위로 효과적으로 찾아준다.
성능/효과
확인하기 위한 것이다. 갱신된 RDF 문서를 새로 저장했을 경우와 이전 버전의 RDF 문서를 TripieDiff# 사용하여 갱신한 경우의 총 문장 개수가 일치함을 확인하였으며, SQL 질의를 통하여 두 데이타 베이스가 완전히 동일함을 확인하였다.
이 기법은 텍스트 비교를 이용하여 이전 버전의 RDF 문서와 새 버전의 rdf 문서의 차이를 알아낸 후, 이에 텍스트 비교의 문제점을 보완하여 갱신의 대상이 되는 트리플들을 알아내어 새 버전의 RDF 문서 전체를 새로 저장하지 않고 효율적으로 갱신할 수 있게 해준다. 그리고 실험을 통해 갱신功 크기가 약 25%를 넘지 않는 경우 새 버전의 RDF 문서를 저장하는 것보다 TripleDiff 를 이용하는 것이 더 효율적임을 확인하였다.
실험결과를 보면, 문장 삭제의 경우 약 75, 000개(전체 문서의 약 25%)의 문장을 삭제할 때 전체 문서를 새로 저장하는 것과 TripieDiff의 수행 시간이 같아지는 것을 볼 수 있다. 반면 문장 추가의 경우에는 10만 개 (전체 문서의 약 35%)가 넘어도 전체 문서를 새로 저장하는 것보다 TripieDiff의 성능이 좋음을 알 수 있다.
종합해 볼 때, TripieDiff는 지속적으로 갱신되는 RDF 데이타를 효율적으로 갱신할 수 있다. 그 효과는 문서의 변화한 양이 적고 삭제되는 문장의 수가 적을수록 더 커진다.
그 효과는 문서의 변화한 양이 적고 삭제되는 문장의 수가 적을수록 더 커진다. 최악의 경우를 가정해 보면, 전체 문서의 25% 이상이 갱신되었을 경우에는 TripieDiff를 사용하는 것보다 문서를 새로 저장하는 것이 오히려 더 효과적이다. 그러나 실제 데이타에서 이러한 경우는 드물고, 서론에 기술한 것과 같이 여러 RDF 문서가 하나의 데이타베이스에 저장될 수도 있기 때문에 이러한 점진적 갱신 알고리즘은 꼭 필요하다.
후속연구
또한 이 데이타들은 조금씩 계속해서 갱신된다. 본 연구는 이러한 목적에 부합되기 때문에 시스템에 효과적으로 사용될 것으로 기대하고 있다.
본 연구는 향후에 연구실에서 계획하고 있는 OASIS (Omics AnalySIS for microbial organisms) 시스템에 사용될 예정이다. OASIS 시스템은 여러 생물학 데이타베이스와 분석 도구들을 통합하여 연구자에게 좀 더 정확한 예측이나 새로운 시각을 제공하기 위한 시스템이다.
참고문헌 (13)
Graham Klyne, Jeremy J. Carroll, and Brian McBride. Resource Description Framework (RDF): Concepts and Abstract Syntax, W3C Recommendation, 2004
Jeen Broekstra, et. al. Sesame: A Generic Architec-ture for Storing and Querying RDF and RDF Schema, In Proceedings of the International Semantic Web Conference, 2002
Kevin Wilkinson, et. al. Efficient RDF Storage and Retrieval in Jena2. In Proceedings of the first International Workshop on Semantic Web and Databases, 2003
김기성，유상원, 이태휘，김형주 RDFS 함의 규칙적용 순서를 고려한 전방향 RDFS 추론 엔진의 최적화. 정보과학회논문지:데이타베이스，33(2)，2006
Michael Klein, et. al. Ontology Versioning and Change Detection on the Web. In Proceedings of the 13th International Conference on Knowledge Engineering and Knowledge Management, 2002
Jeremy J. Carroll. Matching RDF Graphs. In Proceedings of the International Semantic Web Conference, 2002
Jeremy J. Carroll. Signing RDF Graphs. In Proceedings of the International Semantic Web Conference, 2003
Tim Berners-Lee and Dan Connolly. Delta: An Ontology for the Distribution of Differences Between RDF Graphs. httpv/www.wd.org/DesignIssues/Diff
GNU diff, http://www.gnu.org/software/diffutils/diffutils.html
Sudarshan S. Chawathe, et. al. Change Detection in Hierarchically Structured Information. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1996
David MacKenzie, Paul Eggert and Richard Stallman. Comparing and Merging Files. http://www. fnal.gov/docs/products/diffutils/diff_toc.html
※ AI-Helper는 부적절한 답변을 할 수 있습니다.