18 0

Full metadata record

DC FieldValueLanguage
dc.contributor.author손진현-
dc.date.accessioned2019-10-07T01:51:47Z-
dc.date.available2019-10-07T01:51:47Z-
dc.date.issued2005-06-
dc.identifier.citation정보과학회논문지 : 데이타베이스, v. 32, No. 3, Page. 326 - 333en_US
dc.identifier.issn1229-7739-
dc.identifier.urihttp://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE00665211&language=ko_KR-
dc.identifier.urihttp://repository.hanyang.ac.kr/handle/20.500.11754/110876-
dc.description.abstract많은 XML 응용들은 XML 문서에 대한 질의 언어로 XPath 패턴을 사용한다. XPath 패턴들 사이에는 포함 관계가 존재할 수 있으며, 하나의 XPath 패턴이 다른 XPath 패턴을 포함하는지를 결정하는 문제를 포함 문제라고 한다. 포함 문제는 많은 응용들에서 발생하고 있지만 co-NP complete 문제로 알려져 있다. 한편 XPath 패턴들 사이의 준동형 관계는 포함 관계의 충분 조건이면서 다항 시간에 얻을 수 있다. 본 논문에서는 준동형 문제가 포함 문제를 대체하여 유용하게 쓰일 수 있는 응용들에 대해 논의하고, XPath 패턴들 사이의 준동형 정보를 유지하면 많은 이점을 얻을 수 있다는 사실에 대해 논의한다. 그리고 XPath 패턴들 사이의 준동형 관계를 유지하기 위하여 POX(Partially Ordered Set of XPath Patterns)라는 래티스 구조를 제안하고, 그것을 유지할 수 있는 알고리즘을 개발한다. 알고리즘 분석을 보면 알 수 있듯이, 본 논문에서 제안하는 알고리즘은 다항 시간에 POX를 효율적으로 유지할 수 있다. Many XML applications use XPath patterns as a query language for XML documents. Two XPath patterns may have containment relationship, and the containment problem between two XPath patterns is a problem that determines whether one XPath pattern contains another XPath pattern. Although the containment problem occurs in many applications, it is known as a co-NP complete. A homomorphism problem, which is a sufficient condition for the containment problem, is solved in polynomial time. We first discuss applications that replace the containment problem with the homomorphism problem, and maintaining homomorphism information among XPath patterns will benefit those applications. Then, we propose a lattice structure, called POX (Partially Ordered Set of XPath Patterns), and develop algorithms for maintaining it. As our analyses show, the algorithms can efficiently maintain POX in polynomial time.en_US
dc.language.isoko_KRen_US
dc.publisher한국정보과학회en_US
dc.titleXPath 패턴들간의 준동형 정보를 효율적으로 유지하기 위한 래티스 구조en_US
dc.title.alternativeA Lattice Structure for Efficiently Maintaining Homomorphism Information Among XPath Patternsen_US
dc.typeArticleen_US
dc.relation.journal정보과학회논문지-
dc.contributor.googleauthor유상현-
dc.contributor.googleauthor손진현-
dc.contributor.googleauthor김명호-
dc.relation.code2012210811-
dc.sector.campusE-
dc.sector.daehakCOLLEGE OF ENGINEERING SCIENCES[E]-
dc.sector.departmentDIVISION OF ELECTRONIC ENGINEERING & COMPUTER SCIENCE-
dc.identifier.pidjhson-
Appears in Collections:
COLLEGE OF ENGINEERING SCIENCES[E](공학대학) > ETC
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE