A heuristic approach for optimization of path expressions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1995

AUTHORS

Cetin Ozkan , Asuman Dogac , Cem Evrendilek

ABSTRACT

The object-oriented database management systems store references to objects (implicit joins, precomputed joins), and use path expressions in query languages. One way of executing path expressions is pointer chasing of precomputed joins. However it has been previously shown that converting implicit joins to explicit joins during the optimization phase may yield better execution plans. A path expression is a linear query, therefore, considering all possible join sequences within a path expression is polynomial in the number of classes involved. Yet, when the implicit joins are converted to explicit joins in a query involving multiple path expressions bound to the same bind variable, the query becomes a star query and thus considering all possible joins is exponential in the number of paths involved. This implies that there is a need for improvement by using heuristic in optimizing queries involving multiple path expressions. A heuristic based approach for optimizing queries involving multiple path expressions is described in this paper. First, given the cost and the selectivities of path expressions by considering a path expression as a unit of processing, we provide an algorithm that gives the optimum execution order of multiple path expressions bound to the same bind variable. For this purpose, we derive the formulas for the selectivities of path expressions. Then by using this ordering as a basis we provide a general heuristic approach for optimizing queries involving multiple path expressions. Two optimizers are developed to compare the performance of the heuristic based approach suggested in this paper with the performance of an optimizer based on an exhaustive search strategy. The exhaustive optimizer is generated through Volcano Optimizer Generator (VOG). The results of the experiments indicate that the heuristic based optimizer has a superior performance with the increasing number of path expressions. More... »

PAGES

522-534

Book

TITLE

Database and Expert Systems Applications

ISBN

978-3-540-60303-0
978-3-540-44790-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0049149

DOI

http://dx.doi.org/10.1007/bfb0049149

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1036330807


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Middle East Technical University", 
          "id": "https://www.grid.ac/institutes/grid.6935.9", 
          "name": [
            "Software Research and Development Center of TUBITAK, Middle East Technical University, 06531\u00a0Ankara, Turkiye"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ozkan", 
        "givenName": "Cetin", 
        "id": "sg:person.011157070231.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011157070231.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Middle East Technical University", 
          "id": "https://www.grid.ac/institutes/grid.6935.9", 
          "name": [
            "Software Research and Development Center of TUBITAK, Middle East Technical University, 06531\u00a0Ankara, Turkiye"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dogac", 
        "givenName": "Asuman", 
        "id": "sg:person.01074167140.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Middle East Technical University", 
          "id": "https://www.grid.ac/institutes/grid.6935.9", 
          "name": [
            "Software Research and Development Center of TUBITAK, Middle East Technical University, 06531\u00a0Ankara, Turkiye"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Evrendilek", 
        "givenName": "Cem", 
        "id": "sg:person.013633220171.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013633220171.70"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/170035.170080", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024013331"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/b978-0-444-88433-6.50020-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028593210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/93597.98740", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053473382"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icde.1993.344061", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094127422"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "The object-oriented database management systems store references to objects (implicit joins, precomputed joins), and use path expressions in query languages. One way of executing path expressions is pointer chasing of precomputed joins. However it has been previously shown that converting implicit joins to explicit joins during the optimization phase may yield better execution plans. A path expression is a linear query, therefore, considering all possible join sequences within a path expression is polynomial in the number of classes involved. Yet, when the implicit joins are converted to explicit joins in a query involving multiple path expressions bound to the same bind variable, the query becomes a star query and thus considering all possible joins is exponential in the number of paths involved. This implies that there is a need for improvement by using heuristic in optimizing queries involving multiple path expressions. A heuristic based approach for optimizing queries involving multiple path expressions is described in this paper. First, given the cost and the selectivities of path expressions by considering a path expression as a unit of processing, we provide an algorithm that gives the optimum execution order of multiple path expressions bound to the same bind variable. For this purpose, we derive the formulas for the selectivities of path expressions. Then by using this ordering as a basis we provide a general heuristic approach for optimizing queries involving multiple path expressions. Two optimizers are developed to compare the performance of the heuristic based approach suggested in this paper with the performance of an optimizer based on an exhaustive search strategy. The exhaustive optimizer is generated through Volcano Optimizer Generator (VOG). The results of the experiments indicate that the heuristic based optimizer has a superior performance with the increasing number of path expressions.", 
    "editor": [
      {
        "familyName": "Revell", 
        "givenName": "Norman", 
        "type": "Person"
      }, 
      {
        "familyName": "Tjoa", 
        "givenName": "A Min", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0049149", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60303-0", 
        "978-3-540-44790-0"
      ], 
      "name": "Database and Expert Systems Applications", 
      "type": "Book"
    }, 
    "name": "A heuristic approach for optimization of path expressions", 
    "pagination": "522-534", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0049149"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ad10cbeba73c4ac3c5e2046667a3c0ca98234190e32113c8148b6a18a0cb3d06"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036330807"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0049149", 
      "https://app.dimensions.ai/details/publication/pub.1036330807"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000062.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0049149"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bfb0049149'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bfb0049149'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0049149'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0049149'


 

This table displays all metadata directly associated to this object as RDF triples.

96 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0049149 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N8631897b6f9c4d2a888a9cf16767fdf5
4 schema:citation https://doi.org/10.1016/b978-0-444-88433-6.50020-4
5 https://doi.org/10.1109/icde.1993.344061
6 https://doi.org/10.1145/170035.170080
7 https://doi.org/10.1145/93597.98740
8 schema:datePublished 1995
9 schema:datePublishedReg 1995-01-01
10 schema:description The object-oriented database management systems store references to objects (implicit joins, precomputed joins), and use path expressions in query languages. One way of executing path expressions is pointer chasing of precomputed joins. However it has been previously shown that converting implicit joins to explicit joins during the optimization phase may yield better execution plans. A path expression is a linear query, therefore, considering all possible join sequences within a path expression is polynomial in the number of classes involved. Yet, when the implicit joins are converted to explicit joins in a query involving multiple path expressions bound to the same bind variable, the query becomes a star query and thus considering all possible joins is exponential in the number of paths involved. This implies that there is a need for improvement by using heuristic in optimizing queries involving multiple path expressions. A heuristic based approach for optimizing queries involving multiple path expressions is described in this paper. First, given the cost and the selectivities of path expressions by considering a path expression as a unit of processing, we provide an algorithm that gives the optimum execution order of multiple path expressions bound to the same bind variable. For this purpose, we derive the formulas for the selectivities of path expressions. Then by using this ordering as a basis we provide a general heuristic approach for optimizing queries involving multiple path expressions. Two optimizers are developed to compare the performance of the heuristic based approach suggested in this paper with the performance of an optimizer based on an exhaustive search strategy. The exhaustive optimizer is generated through Volcano Optimizer Generator (VOG). The results of the experiments indicate that the heuristic based optimizer has a superior performance with the increasing number of path expressions.
11 schema:editor N147b687b29c24ba4a58ec94d222c6e42
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf N885c35189aea4a37a04e0b1efdc8b237
16 schema:name A heuristic approach for optimization of path expressions
17 schema:pagination 522-534
18 schema:productId N26c15fa5738043b19b4343024cf78c3a
19 N382bce851a9c4e7ab975838c771e18ec
20 N46b9531f38354fdb9beb038a4631f2e9
21 schema:publisher N332ab23c5e6546d28941c89f158e9d80
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036330807
23 https://doi.org/10.1007/bfb0049149
24 schema:sdDatePublished 2019-04-15T23:40
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N68383b09dec343bd997d0fe9a6811058
27 schema:url http://link.springer.com/10.1007/BFb0049149
28 sgo:license sg:explorer/license/
29 sgo:sdDataset chapters
30 rdf:type schema:Chapter
31 N147b687b29c24ba4a58ec94d222c6e42 rdf:first Na47afb137dc54c0ca463d23f0c6d2bcd
32 rdf:rest N71da891b77ed4df59820d3dbfe17e918
33 N26c15fa5738043b19b4343024cf78c3a schema:name dimensions_id
34 schema:value pub.1036330807
35 rdf:type schema:PropertyValue
36 N332ab23c5e6546d28941c89f158e9d80 schema:location Berlin, Heidelberg
37 schema:name Springer Berlin Heidelberg
38 rdf:type schema:Organisation
39 N382bce851a9c4e7ab975838c771e18ec schema:name readcube_id
40 schema:value ad10cbeba73c4ac3c5e2046667a3c0ca98234190e32113c8148b6a18a0cb3d06
41 rdf:type schema:PropertyValue
42 N416a594c1a2c498ab4c2f1e8fc3cb4cc rdf:first sg:person.01074167140.73
43 rdf:rest Ned25b1fec8464fbca8acb12941cf25b8
44 N46b9531f38354fdb9beb038a4631f2e9 schema:name doi
45 schema:value 10.1007/bfb0049149
46 rdf:type schema:PropertyValue
47 N68383b09dec343bd997d0fe9a6811058 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N71da891b77ed4df59820d3dbfe17e918 rdf:first Nedc9f7ae4442425ca5f9df4d82c25525
50 rdf:rest rdf:nil
51 N8631897b6f9c4d2a888a9cf16767fdf5 rdf:first sg:person.011157070231.63
52 rdf:rest N416a594c1a2c498ab4c2f1e8fc3cb4cc
53 N885c35189aea4a37a04e0b1efdc8b237 schema:isbn 978-3-540-44790-0
54 978-3-540-60303-0
55 schema:name Database and Expert Systems Applications
56 rdf:type schema:Book
57 Na47afb137dc54c0ca463d23f0c6d2bcd schema:familyName Revell
58 schema:givenName Norman
59 rdf:type schema:Person
60 Ned25b1fec8464fbca8acb12941cf25b8 rdf:first sg:person.013633220171.70
61 rdf:rest rdf:nil
62 Nedc9f7ae4442425ca5f9df4d82c25525 schema:familyName Tjoa
63 schema:givenName A Min
64 rdf:type schema:Person
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information Systems
70 rdf:type schema:DefinedTerm
71 sg:person.01074167140.73 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
72 schema:familyName Dogac
73 schema:givenName Asuman
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73
75 rdf:type schema:Person
76 sg:person.011157070231.63 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
77 schema:familyName Ozkan
78 schema:givenName Cetin
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011157070231.63
80 rdf:type schema:Person
81 sg:person.013633220171.70 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
82 schema:familyName Evrendilek
83 schema:givenName Cem
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013633220171.70
85 rdf:type schema:Person
86 https://doi.org/10.1016/b978-0-444-88433-6.50020-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028593210
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1109/icde.1993.344061 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094127422
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/170035.170080 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024013331
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1145/93597.98740 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053473382
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.6935.9 schema:alternateName Middle East Technical University
95 schema:name Software Research and Development Center of TUBITAK, Middle East Technical University, 06531 Ankara, Turkiye
96 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...