File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Constraint satisfaction in semi-structured data graphs

TitleConstraint satisfaction in semi-structured data graphs
Authors
Issue Date2004
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3258, p. 393-407 How to Cite?
AbstractXML data can be modeled as node-labeled graphs and XML queries can be expressed by structural relationships between labeled elements. XML query evaluation has been addressed using mainly database, and in some cases graph search, techniques. We propose an alternative method that models and solves such queries as constraint satisfaction problems (CSPs). We describe common constraint types occurring in XML queries and show how query evaluation can benefit from methods for preprocessing and solving CSPs. We identify an important non-binary constraint that is a common module of XML queries and describe a generalized arc consistency algorithm with low cost that can ensure polynomial query evaluation. Finally, we demonstrate that maintaining the consistency of such non-binary constraints can greatly accelerate search in intractable queries that include referential relationships. © Springer-Verlag Berlin Heidelberg 2004.
Persistent Identifierhttp://hdl.handle.net/10722/93309
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorStergiou, Ken_HK
dc.date.accessioned2010-09-25T14:57:12Z-
dc.date.available2010-09-25T14:57:12Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3258, p. 393-407en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93309-
dc.description.abstractXML data can be modeled as node-labeled graphs and XML queries can be expressed by structural relationships between labeled elements. XML query evaluation has been addressed using mainly database, and in some cases graph search, techniques. We propose an alternative method that models and solves such queries as constraint satisfaction problems (CSPs). We describe common constraint types occurring in XML queries and show how query evaluation can benefit from methods for preprocessing and solving CSPs. We identify an important non-binary constraint that is a common module of XML queries and describe a generalized arc consistency algorithm with low cost that can ensure polynomial query evaluation. Finally, we demonstrate that maintaining the consistency of such non-binary constraints can greatly accelerate search in intractable queries that include referential relationships. © Springer-Verlag Berlin Heidelberg 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleConstraint satisfaction in semi-structured data graphsen_HK
dc.typeArticleen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35048892552en_HK
dc.identifier.hkuros103366en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048892552&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3258en_HK
dc.identifier.spage393en_HK
dc.identifier.epage407en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridStergiou, K=35575234700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats