ACM Transactions on Database Systems · 2006 · 30 citations · 22 references
ComputingComputer ScienceDatabasesInformation RetrievalNatural Language ProcessingInformation ExtractionParsingQuery ProcessingSequence LabelingSequence MiningXml DatabasesPattern Matching AlgorithmsPattern SearchingPatternsRefinementSequence Database IndexingXml IndexingXml ParsingXml Query Processing
We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by prüfer's method that constructs a one-to-one correspondence between trees and sequences. During query processing, a twig pattern is also transformed into its Prüfer sequence. By performing subsequence matching on the set of sequences in the database and performing a series of refinement phases that we have developed, we can find all the occurrences of a twig pattern in the database. Our approach allows holistic processing of a twig pattern without breaking the twig into root-to-leaf paths and processing these paths individually. Furthermore, we show in the article that all correct answers are found without any false dismissals or false alarms. Experimental results demonstrate the performance benefits of our proposed techniques.
22
Tim Bray, Jean Paoli, C. M. Sperberg‐McQueen · World Wide Web · 1997 · 1.7K citations
Nicolas Bruno, Nick Koudas, Divesh Srivastava · 2002 · 876 citations
On supporting containment queries in relational database management systems
Chun Zhang, Jeffrey F. Naughton, David J. DeWitt et al. · 2001 · 785 citations
Structural joins: a primitive for efficient XML query pattern matching
Shurug Al-Khalifa, H. V. Jagadish, Nick Koudas et al. · 2003 · 780 citations