Semistructured Data and XML
Massive computingPublished 1 January 2002
Dan Suciu
Citations71
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The distinguishing feature of semistructured data is that the schema is embedded with the data. The main challenge is to cope with the additional flexibility without sacrificing efficiency. We introduce semistructured data by presenting a syntax and describing the datamodel. We discuss some query languages designed for semistructured data and address some systems issues, such as storage and XML compression.
Keywords
Computer Science
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
Building a Large Annotated Corpus of English: The Penn Treebank
7,528 Citations1993Mitchell P. Marcus
IEEE Transactions on Information TheoryA universal algorithm for sequential data compression
5,467 Citations1977J. Ziv, A. Lempel
The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable- to-block codes designed to match a completely specified source.
DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases
1,147 Citations1997Roy Goldman, Jennifer Widom
The theoretical foundations of DataGuides are presented along with an algorithm for their creation and an overview of incremental maintenance, and performance results based on the implementation of dataGuides in the Lore DBMS for semistructured data are provided.
Data on the Web: From Relations to Semistructured Data and XML
1,064 Citations1999Serge Abiteboul, Peter Buneman +1 more
A Syntax for Data: Typing semistructured data and the Lore system and database products supporting XML are explained.
Relational Databases for Querying XML Documents: Limitations and Opportunities
917 Citations1999Jayavel Shanmugasundaram, Kristin Tufte +4 more
Journal of Intelligent Information SystemsThe TSIMMIS Approach to Mediation: Data Models and Languages
832 Citations1997Héctor García-Molina, Yannis Papakonstantinou +6 more
TSIMMIS—The Stanford-IBM Manager of Multiple Information sources offers a datamodel and a common query language that are designed to support the combining of information from many different sources.
Object exchange across heterogeneous information sources
756 Citations2002Yannis Papakonstantinou, Héctor García-Molina +1 more
An object-based information exchange model and a corresponding query language are defined that are well suited for integration of diverse information sources and used to integrate heterogeneous bibliographic information sources.
Lecture notes in computer scienceIndex Structures for Path Expressions
602 Citations1999Tova Milo, Dan Suciu
In recent years there has been an increased interest in managing data that does not conform to traditional data models, like the relational or object oriented model, and the term semistructured data has been used to refer to such data.
ACM SIGMOD RecordDatabase techniques for the World-Wide Web
560 Citations1998Daniela Florescu, Alon Y. Levy +1 more
The primary goal of this survey is to classify the different tasks to which database concepts have been applied, and to emphasize the technical innovations that were required to do so.
SIAM Journal on ComputingLanguages that Capture Complexity Classes
545 Citations1987Neil Immerman
It is shown that projection translations are a uniform version of Valiant’s projections, and that the usual complete problems remain complete via these very restrictive reductions.
Computer NetworksA query language for XML
544 Citations1999Alin Deutsch, Mary Fernández +3 more
This work presents a query language for XML, called XML-QL, which is argued to be suitable for performing the above tasks, and can extract data from existing XML documents and construct new XML documents.
A query language and optimization techniques for unstructured data
535 Citations1996Peter Buneman, Susan B. Davidson +2 more
Here a simple language UnQL is proposed for querying data organized as a rooted, edge-labeled graph and it is shown that known optimization techniques for operators on flat relations apply to the "horizontal" dimension of UnQL.
ACM SIGMOD RecordStoring semistructured data with STORED
455 Citations1999Alin Deutsch, Mary Fernández +1 more
Semistructured data
443 Citations1997Peter Buneman
A number of issues surrounding semi-structured data are covered: finding a concise formulation, building a sufficiently expressive language for querying and transformation, and opti-mizat,ion problems.
Lecture notes in computer scienceAdding structure to unstructured data
431 Citations1997Peter Buneman, Susan B. Davidson +2 more
It is proposed that both data and schema be represented as edge-labeled graphs and notions of conformance between a graph database and a graph schema are developed and it is shown that there is a natural and efficiently computable ordering on graph schemas.
Medical Entomology and ZoologyXML-QL: A Query Language for XML
417 Citations1998Alin Deutsch
An amendment to this paper has been published and can be accessed via the original article.
Using Schema Matching to Simplify Heterogeneous Data Translation
394 Citations1998Tova Milo, Sagit Zohar
This paper presents a new translation system, based on schema-matching, aimed at simplifying the intricate task of data conversion, and shows that it allows a convenient specification and customization of data conversions, and can be easily combined with the traditional data-based translation languages.
On the decidability of query containment under constraints
378 Citations1998Diego Calvanese, Giuseppe De Giacomo +1 more
The VLDB JournalEfficiently publishing relational data as XML documents
310 Citations2001Jayavel Shanmugasundaram, Eugene J. Shekita +5 more
The results of an experimental study show that constructing XML documents inside the relational engine can have a significant performance benefit and show the superiority of having the relational engines use what is called an “outer union plan” to generate the content of an XML document.
Your mediators need data conversion!
308 Citations1998Sophie Cluet, Claude Delobel +2 more
This paper presents the YAT system for data conversion, a declarative, rule-based and features enhanced pattern matching facilities and powerful restructuring primitives, which provides tools for the specification and the implementation of data conversions among heterogeneous data sources.
International Journal on Digital LibrariesQuerying documents in object databases
260 Citations1997Serge Abiteboul, Sophie Cluet +4 more
It is shown that almost standard database optimization techniques can be used to answer queries without having to load the entire document into the database, and the interaction of full-text indexes with standard database collection indexes that provide important speed-up are considered.
The VLDB JournalUnQL: a query language and algebra for semistructured data based on structural recursion
255 Citations2000Peter Buneman, Mary Fernández +1 more
This paper describes a simple and powerful query language based on pattern matching and shows that it can be expressed using structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees.
Optimizing regular path expressions using graph schemas
242 Citations2002Mary Fernández, Dan Suciu
This work describes two optimization techniques for queries with regular path expressions that rely on graph schemas for specifying partial knowledge about the data's structure and gives an efficient algorithm for rewriting any regular path expression query into a pruned one.
From structured documents to novel query facilities
226 Citations1994V. Christophides, Serge Abiteboul +2 more
A natural mapping from SGML documents into OODB's and a formal extension of two OodB query languages in order to deal with SGML document retrieval and a key element is the introduction of paths as first class citizens.
DTD inference for views of XML data
220 Citations2000Yannis Papakonstantinou, Victor Vianu
It is shown that one can always infer tight D TDs, that precisely characterize a selection view on sources satisfying given DTDs, and important special cases where one can infer a tight DTD without requiring extension (ii).
Object Fusion in Mediator Systems
220 Citations1996Yannis Papakonstantinou, Serge Abiteboul +1 more
This paper shows how many common fusion operations can be specified non-procedurally and succinctly and presents key optimization techniques that significantly reduce the processing costs associated with information fusion.
ACM SIGMOD RecordComprehension syntax
213 Citations1994Peter Buneman, Leonid Libkin +3 more
An informal account of a language based on comprehension syntax that deals uniformly with a variety of collection types and shows how comprehension syntax is a natural fragment of structural recursion, a much more powerful programming paradigm for collection types.
Querying the World Wide Web
198 Citations2002Alberto O. Mendelzon, George A. Mihaila +1 more
ACM SIGMOD RecordComparative analysis of five XML query languages
193 Citations2000Angela Bonifati, Stefano Ceri
A comparison of five, representative query languages for XML, highlighting their common features and differences is presented.
Information Integration and Web-based Applications & ServicesStoring And Querying XML Data Using RDBMS.
193 Citations2004Yesi Novaria Kunang, Ahmad Ashari
The results unambiguously locate the torque-generating stator complexes and show that diverse high-torque motors use variants of an ancestrally related family of structures to scaffold incorporation of additional stator complex at wider radii from the axial driveshaft than in the model enteric motor.
Query containment for conjunctive queries with regular expressions
170 Citations1998Daniela Florescu, Alon Y. Levy +1 more
It is shown that containment of STRUQLO queries is decidable, and a syntactic criteria for query containment is given, based on a notion of query mappings, which extends containment mappings for conjunctive queries.
Representative objects: concise representations of semistructured, hierarchical data
155 Citations2002Svetlozar Nestorov, Jeffrey D. Ullman +2 more
The concept of representative objects is introduced, which uncover the inherent schema(s) in semi-structured, hierarchical data sources and provide a concise description of the structure of the data.
ILOG: declarative creation and manipulation of object identifiers
154 Citations1990Richard Hull, Masatoshi Yoshikawa
The VLDB JournalDeclarative specification of Web sites with S
129 Citations2000Mary Fernández, Daniela Florescu +2 more
This paper contains a comprehensive description of the Strudel system and details the benefits of declarative site specification and describes three different, but complementary, systems that extend and improve uponStrudel's original ideas.
ACM SIGMOD RecordInferring structure in semistructured data
119 Citations1997Svetlozer Nestorov, Serge Abiteboul +1 more
A notion of a type hierarchy for such data is proposed, and a method for deriving the type hierarchy is outlined, and rules for assigning types to data elements are outlined.
Schemas for integration and translation of structured and semi-structured data
98 Citations1999Catriel Beeri, T. Milo
Indexing Semistructured Data
95 Citations1998Jason McHugh, Jennifer Widom +3 more
This paper presents a general framework for indexing values in the presence of automatic type coercion, and based on Lore, a DBMS for semistructured data, introduces four types of indexes and illustrates how they are used during query processing.
On wrapping query languages and efficient XML integration
74 Citations2000Vassilis Christophides, Sophie Cluet +1 more
Theoretical Computer ScienceCorrespondence and translation for heterogeneous data
70 Citations2002Serge Abiteboul, Sophie Cluet +1 more
It is claimed that the framework and restrictions are acceptable in practice, and in particular one can show that all the document-OODB correspondences/translations of [2, 3] are covered.
The Computer JournalA Query Language for Retrieving Information from Hierarchic Text Structures
50 Citations1991I. A. Macleod
Lecture notes in computer scienceSchemas for Integration and Translation of Structured and Semi-structured Data
48 Citations1999Catriel Beeri, Tova Milo
This paper elaborate on the theoretical foundations of a middleware schema model, and presents expressive and flexible schema definition languages, and investigates properties such as expressive power and the complexity of decision problems that are significant in the context of data translation and integration.
Nucleic Acids ResearchThe EMBL Data Library
40 Citations1992Desmond G. Higgins, Rainer Fuchs +2 more
The principal role of the EMBL Data Library has been to maintain and distribute a database of nucleotide sequences (the EMBL Nucleotide Sequence Database), which also supports and maintains the protein sequence database SWISS-PROT and distributes other databases of interest to molecular biologists.
Query Optimization for Semistructured Data
19 Citations1997Jason McHugh, Jennifer Widom
This paper describes the query processor of Lore, a DBMS for XML-based data supporting an expressive query language and focuses primarily on Lore's cost-based query optimizer, which defines appropriate logical and physical query plans, database statistics, and a cost model.
Semistructured Data and XML
18 Citations2000Dan Suciu
XML poses a new set of challenges for semistructured data research, and creates problems which the research on semistructure data has not yet addressed, as argued in this paper.
Managing Web data
4 Citations1999Dan Suciu
The focus of the Web shifts from document management to data management, and topics like queries, views, data warehouses, mediators, which were the domain of databases, become of interest to the Web, but the new data differs from traditional relational or object-oriented data.