- SOAR Home
- →
- Graduate School
- →
- ETD: Electronic Theses and Dissertations
- →
- Master's Theses
- →
- View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
| dc.contributor.advisor | Ramanan, Prakash | en_US |
| dc.contributor.author | Gobbert, Barbara Jane | |
| dc.date.accessioned | 2007-12-04T16:30:30Z | |
| dc.date.available | 2007-12-04T16:30:30Z | |
| dc.date.copyright | 2007 | en |
| dc.date.issued | 2007-05 | |
| dc.identifier.other | t07017 | |
| dc.identifier.uri | http://hdl.handle.net/10057/1134 | |
| dc.description | Thesis (M.S.)--Wichita State University, College of Liberal Arts and Sciences, Dept. of Computer Science | en |
| dc.description.abstract | This research deals with testing the satisfiability of a subclass of XQuery and XPath expressions that contain node identity constraints. This subclass of expressions is called Conjunctive XPath. A query is satisfiable if there exists a database of XML documents that will result in a non-empty answer to the query, whereas a query that is not satisfiable will result in an empty answer when run against any database. Determining that a query is unsatisfiable prior to execution will result in savings in computer run-time by not executing unsatisfiable queries. Although the general problem is undecidable, we examine a subclass of queries called Conjunctive XPath where satisfiability is decidable. Previous researchers have presented algorithms for determining satisfiability based on predicate logic and also using non-deterministic finite automata. We present an algorithm for XPath queries with a single node identity constraint, based on topological sorting. This algorithm has faster run-time compared to previously known algorithms. | en |
| dc.format.extent | x, 66 leaves, ill. | en |
| dc.format.extent | 494682 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | en_US | en |
| dc.rights | Copyright Barbara Jane Gobbert, 2007. All rights reserved. | en |
| dc.subject.lcsh | Electronic dissertations | en |
| dc.title | Testing the satisfiability of tree pattern queries with node identity constraints | en |
| dc.type | Thesis | en |
Files in this item
This item appears in the following Collection(s)
-
Master's Theses [823]
This collection includes Master's theses completed at the Wichita State University Graduate School (Fall 2005 --) -
CS Theses [2]
-
LAS Theses and Dissertations [379]
Theses and dissertations completed at the College of Liberal Arts and Sciences (Fall 2005 -)