TAX: A Tree Algebra for XML
Lecture notes in computer sciencePublished 1 January 2002
H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava, Keith Thompson
Citations235
SJR quartileQ2
SJR score0.35
SNIP0.55
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.
TL;DR
TAX is complete for relational algebra extended with aggregation, and can express most queries expressible in popular XML query languages, and forms the basis for the Timber XML database system currently under development by the authors.
Abstract
Querying XML has been the subject of much recent investigation. A formal bulk algebra is essential for applying database-style optimization to XML queries. We develop such an algebra, called TAX (Tree Algebra for XML), for manipulating XML data, modeled as forests of labeled ordered trees. Motivated both by aesthetic considerations of intuitiveness, and by efficient computability and amenability to optimization, we develop TAX as a natural extension of relational algebra, with a small set of operators. TAX is complete for relational algebra extended with aggregation, and can express most queries expressible in popular XML query languages. It forms the basis for the Timber XML database system currently under development by us.
Keywords
Computer Science
Communications of the ACMA relational model of data for large shared data banks
5,238 Citations1970E. F. Codd
A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced and certain operations on relations are discussed and applied to the problems of redundancy and consistency in the user's model.
Communications of the ACMA relational model of data for large shared data banks
4,834 Citations1983E. F. Codd
International Journal on Digital LibrariesThe Lorel query language for semistructured data
1,067 Citations1997Serge Abiteboul, Dallan Quass +3 more
The main novelties of the Lorel language are the extensive use of coercion to relieve the user from the strict typing of OQL, which is inappropriate for semistructured data; and powerful path expressions, which permit a flexible form of declarative navigational access and are particularly suitable when the details of the structure are not known to the user.
Relational Databases for Querying XML Documents: Limitations and Opportunities
917 Citations1999Jayavel Shanmugasundaram, Kristin Tufte +4 more
On supporting containment queries in relational database management systems
784 Citations2001Chun Zhang, Jeffrey F. Naughton +3 more
The results suggest that contrary to most expectations, with some modifications, a native implementations in an RDBMS can support this class of query much more efficiently.
Structural joins: a primitive for efficient XML query pattern matching
779 Citations2003Shurug Al-Khalifa, H. V. Jagadish +4 more
It is shown that, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse, and this behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack- tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-MERge algorithms do not have the same guarantee.
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.
Journal of the ACMPattern Matching in Trees
440 Citations1982Christoph M. Hoffmann, Michael J. O’Donnell
Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods.
GraphLog
344 Citations1990Mariano P. Consens, Alberto O. Mendelzon
The expressive power of the GraphLog language is characterized and it is shown that it is equivalent to stratified linear Datalog, first order logic with transitive closure, and non-deterministic logarithmic space (assuming ordering on the domain).
Updating XML
327 Citations2001Igor Tatarinov, Zachary G. Ives +2 more
This paper proposes a set of basic update operations for both ordered and unordered XML data, and describes extensions to the proposed standard XML query language, XQuery, to incorporate the update operations.
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).
ACM SIGMOD RecordOn wrapping query languages and efficient XML integration
134 Citations2000Vassilis Christophides, Sophie Cluet +1 more
A general purpose algebra suitable for semistructured on XML query languages is defined and it is shown how this algebra can be used, with appropriate type information, to also wrap more structured query languages such as OQL or SQL.
Lecture notes in computer scienceXDuce: A Typed XML Processing Language (Preliminary Report)
129 Citations2001Haruo Hosoya, Benjamin C. Pierce
The authors need to go beyond types for documents and exploit type information in static checking of programs for XML processing to make the best use of static typing mechanisms.
Lecture notes in computer scienceAn Algebra for XML Query
73 Citations2000Mary Fernández, Jérǒme Simèon +1 more
A novel feature of the algebra is the use of regular-expression types, similar in power to DTDs or XML Schemas, and closely related to Hasoya, Pierce, and Vouillon's work on Xduce.
SAL: An Algebra for Semistructured Data and XML.
69 Citations1999Catriel Beeri, Yariv Tzaban
Lecture notes in computer scienceNavigation-Driven Evaluation of Virtual Mediated Views
59 Citations2000Bertram Ludäscher, Yannis Papakonstantinou +1 more
The proposed demand-driven approach is inevitable for handling up-to-date mediated views of largeWeb sources or query results and a new buffering technique is presented that can mediate between the fine granularity of DOM navigations and the coarse granular of real world sources.
ACM SIGMOD RecordAn overview of GOOD
38 Citations1992Jan Paredaens, Jan Van den Bussche +7 more
The main thrust behind the project is to indicate general concepts that are fundamental to any graph-oriented database user-interface, and the idea of graph-pattern matching as a uniform object manipulation primitive offers a uniform framework in which this can be accomplished.
ACM SIGMOD RecordA grammar-based approach towards unifying hierarchical data models
33 Citations1989Marc Gyssens, Jan Paredaens +1 more
The AQUA approach to querying lists and trees in object-oriented databases
26 Citations2002Bharathi Subramanian, Theodore W. Leung +2 more
An object-oriented query algebra called AQUA (= A Query Algebra) for lists and trees is described, which preserves the ordering between the elements of a list and tree, even when the result list or tree contains an arbitrary set of nodes from the original tree.